Ikkilik qidiruv daraxti

class BSTTugun:
    def __init__(self, qiymat):
        self.qiymat = qiymat
        self.chap = None
        self.ong = None


class IkkilikQidiruvDaraxti:
    """Ikkilik qidiruv daraxti."""

    def __init__(self):
        self.ildiz = None
        self._soni = 0

    # ---------- qo'shish ----------

    def qosh(self, qiymat):
        """Yangi qiymat qo'shadi. O'rtacha O(log n)."""
        self.ildiz = self._qosh(self.ildiz, qiymat)

    def _qosh(self, tugun, qiymat):
        if tugun is None:
            self._soni += 1
            return BSTTugun(qiymat)

        if qiymat < tugun.qiymat:
            tugun.chap = self._qosh(tugun.chap, qiymat)
        elif qiymat > tugun.qiymat:
            tugun.ong = self._qosh(tugun.ong, qiymat)
        # teng bo'lsa - hech narsa qilmaymiz (takror qabul qilinmaydi)

        return tugun

    # ---------- qidirish ----------

    def bormi(self, qiymat):
        """Qiymat mavjudligini tekshiradi. O'rtacha O(log n)."""
        joriy = self.ildiz
        while joriy is not None:
            if qiymat == joriy.qiymat:
                return True
            joriy = joriy.chap if qiymat < joriy.qiymat else joriy.ong
        return False

    # ---------- eng kichik / eng katta ----------

    def eng_kichik(self):
        """Eng chapdagi tugun. O(log n)."""
        if self.ildiz is None:
            return None
        joriy = self.ildiz
        while joriy.chap is not None:
            joriy = joriy.chap
        return joriy.qiymat

    def eng_katta(self):
        """Eng o'ngdagi tugun. O(log n)."""
        if self.ildiz is None:
            return None
        joriy = self.ildiz
        while joriy.ong is not None:
            joriy = joriy.ong
        return joriy.qiymat

    # ---------- o'chirish ----------

    def ochir(self, qiymat):
        """Qiymatni o'chiradi. O'rtacha O(log n)."""
        self.ildiz, ochirildi = self._ochir(self.ildiz, qiymat)
        if ochirildi:
            self._soni -= 1
        return ochirildi

    def _ochir(self, tugun, qiymat):
        if tugun is None:
            return None, False

        if qiymat < tugun.qiymat:
            tugun.chap, ochirildi = self._ochir(tugun.chap, qiymat)
            return tugun, ochirildi

        if qiymat > tugun.qiymat:
            tugun.ong, ochirildi = self._ochir(tugun.ong, qiymat)
            return tugun, ochirildi

        # topildi - uchta holat
        if tugun.chap is None:                    # 1) bolasi yo'q yoki faqat o'ng
            return tugun.ong, True
        if tugun.ong is None:                     # 2) faqat chap bola
            return tugun.chap, True

        # 3) ikkala bolasi bor: o'ng qism daraxtdagi eng kichigini olamiz
        vorislovchi = tugun.ong
        while vorislovchi.chap is not None:
            vorislovchi = vorislovchi.chap

        tugun.qiymat = vorislovchi.qiymat
        tugun.ong, _ = self._ochir(tugun.ong, vorislovchi.qiymat)
        return tugun, True

    # ---------- yordamchi ----------

    def tartiblangan(self):
        """Inorder aylanish - tartiblangan ro'yxat."""
        natija = []

        def yur(tugun):
            if tugun is None:
                return
            yur(tugun.chap)
            natija.append(tugun.qiymat)
            yur(tugun.ong)

        yur(self.ildiz)
        return natija

    def balandlik(self):
        def olcha(tugun):
            if tugun is None:
                return -1
            return 1 + max(olcha(tugun.chap), olcha(tugun.ong))
        return olcha(self.ildiz)

    def __len__(self):
        return self._soni

    def __contains__(self, qiymat):
        return self.bormi(qiymat)

daraxt = IkkilikQidiruvDaraxti()

for son in [50, 30, 70, 20, 40, 80, 60]:
    daraxt.qosh(son)

print("Tartiblangan:", daraxt.tartiblangan())
print("Balandlik:   ", daraxt.balandlik())
print("Eng kichik:  ", daraxt.eng_kichik())
print("Eng katta:   ", daraxt.eng_katta())
print("40 bormi:    ", 40 in daraxt)
print("45 bormi:    ", 45 in daraxt)

daraxt.ochir(30)
print("30 o'chirildi:", daraxt.tartiblangan())

yaxshi = IkkilikQidiruvDaraxti()
for son in [50, 30, 70, 20, 40, 60, 80]:
    yaxshi.qosh(son)

yomon = IkkilikQidiruvDaraxti()
for son in [20, 30, 40, 50, 60, 70, 80]:      # tartiblangan!
    yomon.qosh(son)

print(f"Aralash tartibda: balandlik = {yaxshi.balandlik()}")
print(f"Tartiblangan:     balandlik = {yomon.balandlik()}")

def prefiks_boyicha(daraxt, prefiks):
    """Berilgan prefiks bilan boshlanadigan barcha so'zlarni topadi."""
    natija = []

    def yur(tugun):
        if tugun is None:
            return

        # Chapga borish mantiqiymi?
        if tugun.qiymat >= prefiks:
            yur(tugun.chap)

        if tugun.qiymat.startswith(prefiks):
            natija.append(tugun.qiymat)

        # O'ngga borish mantiqiymi?
        if tugun.qiymat <= prefiks + "￿":
            yur(tugun.ong)

    yur(daraxt.ildiz)
    return natija


lugat = IkkilikQidiruvDaraxti()
for soz in ["dastur", "dasturchi", "dasturlash", "daftar", "daraxt", "kitob", "kalit"]:
    lugat.qosh(soz)

print("'dastur' bilan boshlanuvchilar:")
for soz in prefiks_boyicha(lugat, "dastur"):
    print("  -", soz)