DSA ikkilik qidiruv daraxtlari

Ikkilik qidiruv daraxtlari

Ikkilik qidiruv daraxti (BST) — ikkilik daraxt ma’lumotlar tuzilmasining bir turi bo‘lib, unda daraxtdagi har qanday "X" tugun uchun quyidagi xususiyatlar bajarilishi kerak:

• X tugunining chap bolasi va uning barcha avlodlari (bolalari, bolalarining bolalari va hokazo) X’ning qiymatidan kichikroq qiymatlarga ega.
• O‘ng bola va uning barcha avlodlari X’ning qiymatidan kattaroq qiymatlarga ega.
• Chap va o‘ng qism daraxtlar ham ikkilik qidiruv daraxtlari bo‘lishi kerak.

Bu xususiyatlar oddiy ikkilik daraxtga qaraganda qiymatlarni qidirish, qo‘shish va o‘chirishni tezroq qiladi.

Buni imkon qadar oson tushunish va amalga oshirish uchun ikkilik qidiruv daraxtidagi barcha qiymatlar noyob deb ham faraz qilaylik.

Ushbu tushunchalar va tegishli terminologiyani yaxshiroq tushunish uchun quyidagi ikkilik qidiruv daraxtidan foydalaning.

Daraxtning o‘lchami — undagi tugunlar soni (\(n\)).

Qism daraxt daraxtdagi tugunlardan biri bilan lokal ildiz sifatida boshlanadi va shu tugun hamda uning barcha avlodlaridan iborat bo‘ladi.

Tugunning avlodlari — shu tugunning barcha bola tugunlari, ularning barcha bola tugunlari va hokazo. Shunchaki biror tugundan boshlang, uning avlodlari shu tugun ostida bog‘langan barcha tugunlar bo‘ladi.

Tugun balandligi — shu tugun va barg tugun orasidagi qirralarning maksimal soni.

Tugunning in-order vorisi — agar in-order o‘tishni bajarsak, undan keyin keladigan tugun. Yuqoridagi BST’ni in-order o‘tish natijasida 13 tuguni 14 tugunidan oldin keladi, shuning uchun 13 tugunining vorisi 14 tuguni bo‘ladi.

Ikkilik qidiruv daraxtini aylanib chiqish

Oldimizda haqiqatan ham ikkilik qidiruv daraxti ma’lumotlar tuzilmasi turganini tasdiqlash uchun ushbu sahifa boshidagi xususiyatlar bajarilishini tekshirishimiz mumkin. Ya’ni yuqoridagi rasmdagi har bir tugun uchun tugundan chapdagi barcha qiymatlar kichikroq, o‘ngdagi barcha qiymatlar esa kattaroq ekanini tekshiring.

Ikkilik daraxt BST ekanini tekshirishning yana bir usuli — in-order o‘tishni bajarish (oldingi sahifada qilganimiz kabi) va hosil bo‘lgan qiymatlar ro‘yxati o‘sish tartibida ekanini tekshirish.

Quyidagi kod yuqoridagi rasmdagi ikkilik qidiruv daraxtining aylanib chiqish bilan birga amalga oshirilishidir.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)

root.left = node7
root.right = node15

node7.left = node3
node7.right = node8

node15.left = node14
node15.right = node19

node19.left = node18

# Traverse
inOrderTraversal(root)

Yuqoridagi kod misolini ishga tushirib ko‘rganimizdek, in-order o‘tish o‘sish tartibidagi sonlar ro‘yxatini hosil qiladi, bu esa ushbu ikkilik daraxt ikkilik qidiruv daraxti ekanini bildiradi.

BST’da qiymatni qidirish

BST’da qiymatni qidirish massivda Binary Search yordamida qiymat topganimizga juda o‘xshaydi.

Binary Search ishlashi uchun massiv oldindan saralangan bo‘lishi kerak, shunda massivda qiymatni qidirish juda tez bajarilishi mumkin.

Xuddi shunday, tugunlarning joylashuvi tufayli BST’da qiymatni qidirish ham juda tez bajarilishi mumkin.

Ikkilik qidiruv daraxtida qiymatni qanday qidirishimizni ko‘rish uchun quyidagi animatsiyadan foydalaning.

Yuqoridagi algoritmni quyidagicha amalga oshirish mumkin:

def search(node, target):
    if node is None:
        return None 
    elif node.data == target:
        return node
    elif target < node.data:
        return search(node.left, target)
    else:
        return search(node.right, target)

BST’da qiymatni qidirishning vaqt murakkabligi \(O(h)\), bu yerda \(h\) — daraxtning balandligi.

Masalan, tugunlarining aksariyati o‘ng tomonda joylashgan BST uchun daraxt balandligi kerak bo‘lganidan kattaroq bo‘lib qoladi va eng yomon holatdagi qidiruv ko‘proq vaqt oladi. Bunday daraxtlar muvozanatlanmagan daraxtlar deb ataladi.

Yuqoridagi ikkala ikkilik qidiruv daraxti bir xil tugunlarga ega va ikkala daraxtni in-order o‘tish bir xil natija beradi, lekin balandliklari juda farq qiladi. Yuqoridagi muvozanatlanmagan daraxtda qidirish ko‘proq vaqt oladi, chunki u balandroq.

Keyingi sahifada AVL daraxtlari deb ataladigan ikkilik daraxt turini tasvirlaymiz. AVL daraxtlari o‘zini o‘zi muvozanatlaydi, ya’ni daraxt balandligi minimal darajada saqlanadi, shuning uchun qidirish, qo‘shish va o‘chirish kabi amallar kamroq vaqt oladi.

BST’ga tugun qo‘shish

BST’ga tugun qo‘shish qiymatni qidirishga o‘xshaydi.

Tugunlarni yuqorida tasvirlanganidek qo‘shish qo‘shilgan tugun har doim yangi barg tugunga aylanishini anglatadi.

Yangi tugunlar qanday qo‘shilishini ko‘rish uchun quyidagi simulyatsiyadan foydalaning.

BST’dagi barcha tugunlar noyob, shuning uchun qo‘shmoqchi bo‘lgan qiymatimiz bilan bir xil qiymatni topsak, hech narsa qilmaymiz.

BST’ga tugun qo‘shishni quyidagicha amalga oshirish mumkin:

def insert(node, data):
    if node is None:
        return TreeNode(data)
    else:
        if data < node.data:
            node.left = insert(node.left, data)
        elif data > node.data:
            node.right = insert(node.right, data)
    return node

BST qism daraxtidagi eng kichik qiymatni topish

Keyingi bo‘limda BST’dan tugunni qanday o‘chirish mumkinligi tushuntiriladi, ammo buning uchun bizga tugunning qism daraxtidagi eng kichik qiymatni topadigan funksiya kerak.

Quyidagi rasmda, agar 13 tugunidan boshlab chapga yurishda davom etsak, eng kichik qiymat bo‘lgan 3 tuguniga yetib kelamiz, to‘g‘rimi?

Agar 15 tugunidan boshlab chapga yurishda davom etsak, 15 tugunining qism daraxtidagi eng kichik qiymat bo‘lgan 14 tuguniga yetib kelamiz.

BST tugunining qism daraxtidagi eng kichik qiymatni topish funksiyasi quyidagicha ko‘rinadi:

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

Quyidagi bo‘limda tugunning in-order vorisini topish va undan foydalanib tugunni o‘chirish uchun ushbu minValueNode() funksiyasidan foydalanamiz.

BST’dan tugunni o‘chirish

Tugunni o‘chirish uchun funksiyamiz avval uni BST’dan qidirib topishi kerak.

Tugun topilgandan so‘ng uni o‘chirish turlicha bajarilishi kerak bo‘lgan uchta holat mavjud.

Yuqoridagi 3-qadamda biz topadigan voris har doim barg tugun bo‘ladi va u biz o‘chirmoqchi bo‘lgan tugundan darhol keyin keladigan tugun bo‘lgani uchun u bilan qiymatlarni almashtirib, uni o‘chirishimiz mumkin.

Turli tugunlar qanday o‘chirilishini ko‘rish uchun quyidagi animatsiyadan foydalaning.

8 tuguni barg tugun (1-holat), shuning uchun uni topganimizdan so‘ng shunchaki o‘chirib tashlashimiz mumkin.

19 tugunining faqat bitta bola tuguni bor (2-holat). 19 tugunini o‘chirish uchun ota tugun 15 to‘g‘ridan-to‘g‘ri 18 tuguniga ulanadi, so‘ngra 19 tugunini olib tashlash mumkin.

13 tugunining ikkita bola tuguni bor (3-holat). Vorisni, ya’ni in-order o‘tishda undan darhol keyin keladigan tugunni 13 tugunining o‘ng qism daraxtidagi eng kichik tugunni topish orqali topamiz, bu 14 tuguni. 14 qiymati 13 tuguniga qo‘yiladi, so‘ngra 14 tugunini o‘chirishimiz mumkin.

Tugunni o‘chirish funksiyasiga ega BST’ni quyidagicha amalga oshirish mumkin:

def delete(node, data):
    if not node:
        return None

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        # Node with only one child or no child
        if not node.left:
            temp = node.right
            node = None
            return temp
        elif not node.right:
            temp = node.left
            node = None
            return temp

        # Node with two children, get the in-order successor
        node.data = minValueNode(node.right).data
        node.right = delete(node.right, node.data)

    return node

1-qator: Bu yerdagi node argumenti funksiyaga biz o‘chirmoqchi bo‘lgan dataga ega tugunni qidirishda o‘zini tobora kichikroq qism daraxtlarda rekursiv chaqirish imkonini beradi.

2–8-qatorlar: Bu yerda biz o‘chirmoqchi bo‘lgan, to‘g‘ri dataga ega tugun qidiriladi.

9–22-qatorlar: O‘chirmoqchi bo‘lgan tugunimiz topildi. Bunday holatlar uchta:

1. 1-holat: Bola tugunlari yo‘q tugun (barg tugun). None qaytariladi va u rekursiya orqali ota tugunning yangi chap yoki o‘ng qiymatiga aylanadi (6 yoki 8-qator).
2. 2-holat: Chap yoki o‘ng bola tuguniga ega tugun. O‘sha chap yoki o‘ng bola tugun rekursiya orqali ota tugunning yangi chap yoki o‘ng bolasiga aylanadi (7 yoki 9-qator).
3. 3-holat: Tugunning ham chap, ham o‘ng bola tugunlari bor. In-order voris minValueNode() funksiyasi yordamida topiladi. Vorisning qiymatini o‘chirmoqchi bo‘lgan tugunimizning qiymati sifatida o‘rnatib saqlab qolamiz, so‘ngra voris tugunni o‘chirishimiz mumkin.

24-qator: Rekursiv ishlashni saqlab qolish uchun node qaytariladi.

BST’ni boshqa ma’lumotlar tuzilmalari bilan taqqoslash

Ikkilik qidiruv daraxtlari boshqa ikki ma’lumotlar tuzilmasi — massivlar va bog‘langan ro‘yxatlarning eng yaxshi jihatlarini o‘zida jamlaydi.

BST’da qidirish massivdagi Binary Search kabi tez, vaqt murakkabligi ham xuddi shunday — \(O(\log n)\).

Qiymatlarni o‘chirish va yangi qiymatlarni qo‘shish esa xuddi bog‘langan ro‘yxatlardagi kabi xotiradagi elementlarni siljitmasdan bajarilishi mumkin.

BST muvozanati va vaqt murakkabligi

Ikkilik qidiruv daraxtida yangi tugun qo‘shish, tugunni o‘chirish yoki tugunni qidirish kabi amallar aslida \(O(h)\) ga teng. Bu daraxt qanchalik baland bo‘lsa (\(h\)), amal shunchalik ko‘p vaqt olishini anglatadi.

Yuqoridagi jadvalda qiymatni qidirish \(O(\log n)\) deb yozganimizning sababi shundaki, bu daraxt quyidagi rasmdagi kabi "muvozanatlangan" bo‘lsa to‘g‘ri bo‘ladi.

Biz bu daraxtni muvozanatlangan deymiz, chunki daraxtning chap va o‘ng tomonida taxminan bir xil sondagi tugunlar bor.

Ikkilik daraxt muvozanatlangan ekanini aniq bilish usuli — istalgan tugunning chap va o‘ng qism daraxtlari balandliklari ko‘pi bilan bittaga farq qilishidir. Yuqoridagi rasmda ildiz tugunning chap qism daraxti balandligi \(h=2\), o‘ng qism daraxti balandligi esa \(h=3\).

Ko‘p sonli tugunlarga (katta \(n\)) ega muvozanatlangan BST uchun balandlik \(h \approx \log_2 n\) bo‘ladi, shuning uchun tugunni qidirish, o‘chirish yoki qo‘shishning vaqt murakkabligini \(O(h) = O(\log n)\) deb yozish mumkin.

Ammo agar BST quyidagi rasmdagi kabi butunlay muvozanatlanmagan bo‘lsa, daraxt balandligi taxminan tugunlar soniga teng bo‘ladi, \(h \approx n\), va tugunni qidirish, o‘chirish yoki qo‘shish uchun \(O(h) = O(n)\) vaqt murakkabligini olamiz.

Demak, BST’dagi amallarni optimallashtirish uchun balandlikni minimallashtirish kerak, buning uchun esa daraxt muvozanatlangan bo‘lishi kerak.

Ikkilik qidiruv daraxtini muvozanatda saqlash esa aynan AVL daraxtlari bajaradigan vazifa bo‘lib, bu ma’lumotlar tuzilmasi keyingi sahifada tushuntiriladi.

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Ushbu ikkilik qidiruv daraxtiga qiymati 6 bo‘lgan tugun qo‘shilmoqda:

Yangi tugun qayerga qo‘shiladi?

The node with value 6 
becomes the right child node
of the node with value .

Javobni yuborish »

Mashqni boshlash