Daraxtlar va ikkilik qidiruv daraxtlari: amaliy qo‘llanma

Daraxt va BST nima

Daraxt — tugunlardan iborat tuzilma: ildizdan tashqari har bir tugunning bitta ota tuguni va nol yoki undan ko‘p bolalari bor, sikllar yo‘q. Fayl tizimi, brauzerdagi DOM, sayt menyusi — bularning barchasi daraxt.

Ikkilik qidiruv daraxti (BST) — har bir tugunda ko‘pi bilan ikkita bola bo‘lgan va quyidagi qoida bajariladigan daraxt:

• chap qism daraxtdagi barcha kalitlar tugun kalitidan kichik;
• o‘ng qism daraxtdagi barcha kalitlar undan katta.

Shu qoida tufayli qidiruvning har bir qadamida qolgan daraxtning yarmini tashlab yuborasiz — saralangan massivdagi ikkilik qidiruv kabi. Farqi shundaki, qo‘shish va o‘chirishda elementlarni surish kerak emas.

Amalga oshirish: qo‘shish va qidirish

Python’dagi minimal variant. Bu yerda dublikatlar e’tiborsiz qoldiriladi — bu qarorni oldindan qabul qiling.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    while root is not None and root.key != key:
        root = root.left if key < root.key else root.right
    return root

Qo‘shishda yangi tugun doim barg sifatida qo‘shiladi: «kichigi chapga, kattasi o‘ngga» qoidasi bo‘yicha bo‘sh joy topilguncha pastga tushamiz.

O‘chirish: uchta holat

O‘chirish — eng murakkab amal. Uchta vaziyat bo‘lishi mumkin:

1. Tugunning bolalari yo‘q — shunchaki olib tashlaymiz.
2. Bitta bola — tugun o‘rniga bolasini qo‘yamiz.
3. Ikkita bola — in-order vorisni (o‘ng qism daraxtdagi eng kichik kalit) topamiz, uning kalitini tugunga ko‘chiramiz va vorisni o‘ng qism daraxtdan o‘chiramiz.

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left is not None:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root

Vorisning hech qachon chap bolasi bo‘lmaydi, shuning uchun uni o‘chirish 1- yoki 2-holatga keladi.

Daraxtni aylanib chiqish

def inorder(root):
    if root is not None:
        yield from inorder(root.left)
        yield root.key
        yield from inorder(root.right)

Agar in-order aylanib chiqish saralanmagan ketma-ketlik bersa, kodda xato bor. Bu testlar uchun qulay tekshiruv.

Muvozanat nega muhim

BST tezligi daraxtning balandligiga bog‘liq. Muvozanatli daraxtda balandlik log n kabi o‘sadi, qidirish, qo‘shish va o‘chirish O(log n) vaqtda ishlaydi.

Ammo allaqachon saralangan ma’lumotlarni (1, 2, 3, 4…) qo‘shsangiz, har bir yangi tugun o‘ngga ketadi va daraxt bog‘langan ro‘yxatga aylanadi. Amallar O(n) bo‘lib qoladi, rekursiv funksiyalar esa stek chuqurligi limitiga urilishi mumkin.

Amalda ma’lumotlar ko‘pincha saralangan holda keladi: bazadagi id’lar, sanalar, jadvaldan import. Shuning uchun «oddiy» BST prodakshnda kam ishlatiladi.

AVL va qizil-qora daraxtlar

O‘z-o‘zini muvozanatlovchi daraxtlar har bir qo‘shish va o‘chirishdan keyin burilishlar yordamida muvozanatni tiklaydi. Burilish — kalitlar tartibini saqlagan holda bir nechta tugunning joyini mahalliy almashtirish.

• AVL daraxti har bir tugunda balandlikni saqlaydi va chap hamda o‘ng qism daraxtlar balandligi 1 dan ortiq farq qilmasligini kuzatadi. Muvozanat qat’iy, shuning uchun qidiruv tez, lekin o‘zgarishlarda burilishlar ko‘proq bo‘lishi mumkin.
• Qizil-qora daraxt tugunlarni ikki rangga bo‘yaydi va ildizdan barggacha eng uzun yo‘l eng qisqasidan ko‘pi bilan ikki baravar uzun bo‘lishini ta’minlovchi qoidalarga amal qiladi. Muvozanat yumshoqroq, ammo qo‘shish va o‘chirish odatda arzonroq.

Qizil-qora daraxtlar ko‘plab standart kutubxonalar asosida turadi — masalan, Java’dagi TreeMap. Uni o‘zingiz yozish o‘rganish uchun foydali; ishchi kodda tayyor implementatsiyadan foydalaning.

Ko‘p uchraydigan xatolar

• BST qoidasini butun qism daraxt uchun emas, faqat bevosita bolalar uchun tekshirish.
• Dublikatlar bilan nima qilishni oldindan hal qilmaslik.
• Rekursiv o‘chirish funksiyasidan yangi ildizni qaytarishni unutish.
• Xesh-jadval yetarli bo‘lgan joyda BST ishlatish: kalitlar tartibi va diapazon bo‘yicha qidiruv kerak bo‘lmasa, lug‘at soddaroq va tezroq.