DSA AVL daraxtlari

AVL daraxtlari

Oddiy ikkilik qidiruv daraxti va AVL daraxti o‘rtasidagi yagona farq shundaki, AVL daraxtlari daraxt muvozanatini saqlash uchun qo‘shimcha ravishda aylantirish (rotation) amallarini bajaradi.

Ikkilik qidiruv daraxti chap va o‘ng qism daraxtlar balandliklari orasidagi farq 2 dan kichik bo‘lganda muvozanatda bo‘ladi.

Muvozanatni saqlash orqali AVL daraxti daraxt balandligining minimal bo‘lishini ta’minlaydi, bu esa qidirish, qo‘shish va o‘chirish amallarini juda tez bajarish mumkinligini anglatadi.

Yuqoridagi ikkala daraxt ham ikkilik qidiruv daraxtlari, ular bir xil tugunlarga va bir xil in-order o‘tish natijasiga (alifbo tartibida) ega, ammo balandliklari juda farq qiladi, chunki AVL daraxti o‘zini o‘zi muvozanatlagan.

Muvozanat koeffitsiyentlari qanday yangilanishini va muvozanatni tiklash uchun kerak bo‘lganda aylantirish amallari qanday bajarilishini ko‘rish uchun quyidagi animatsiyada AVL daraxtini qurishni qadamma-qadam kuzating.

Muvozanat koeffitsiyenti qanday hisoblanishi, aylantirish amallari qanday bajarilishi va AVL daraxtlarini qanday amalga oshirish mumkinligi haqida ko‘proq bilish uchun o‘qishda davom eting.

Chapga va o‘ngga aylantirishlar

AVL daraxtida muvozanatni tiklash uchun chapga yoki o‘ngga aylantirishlar yoki chapga va o‘ngga aylantirishlarning kombinatsiyasi bajariladi.

Oldingi animatsiyada bitta aniq chapga aylantirish va bitta aniq o‘ngga aylantirish ko‘rsatilgan.

Ammo umuman olganda, chapga va o‘ngga aylantirishlar quyidagi animatsiyadagi kabi bajariladi.

Qism daraxt o‘z ota tugunini qanday o‘zgartirishiga e’tibor bering. Aylantirish paytida qism daraxtlar to‘g‘ri in-order o‘tish tartibini saqlash hamda daraxtdagi barcha tugunlar uchun chap bola o‘ng boladan kichik bo‘lishi haqidagi BST xususiyatini saqlash maqsadida ota tugunni shu tarzda almashtiradi.

Shuni ham yodda tutingki, muvozanati buziladigan va aylantirishni talab qiladigan tugun har doim ham ildiz tugun bo‘lavermaydi.

Muvozanat koeffitsiyenti

Tugunning muvozanat koeffitsiyenti — uning qism daraxtlari balandliklari orasidagi farq.

AVL daraxtidagi barcha tugunlar uchun qism daraxt balandliklari har bir tugunda saqlanadi va daraxt muvozanatdan chiqqan-chiqmaganini tekshirish uchun muvozanat koeffitsiyenti tugunning qism daraxt balandliklari asosida hisoblanadi.

Qism daraxt balandligi — qism daraxtning ildiz tuguni va shu qism daraxtdagi eng pastda joylashgan barg tugun orasidagi qirralar soni.

AVL daraxti muvozanatni qayta tiklash uchun bajarishi mumkin bo‘lgan turli aylantirish amallarini batafsilroq ko‘rib chiqaylik.

To‘rtta "muvozanatsizlik" holati

Hatto bitta tugunning muvozanat koeffitsiyenti -1 dan kichik yoki 1 dan katta bo‘lsa, daraxt muvozanatdan chiqqan deb hisoblanadi va muvozanatni tiklash uchun aylantirish kerak bo‘ladi.

AVL daraxti muvozanatdan chiqishining to‘rt xil holati bor va bu holatlarning har biri turli aylantirish amalini talab qiladi.

Bu holatlarning animatsiyalari va tushuntirishlarini quyida ko‘ring.

Chap-Chap (LL) holati

Muvozanatsizlik aniqlangan tugun chapga og‘ir, tugunning chap bola tuguni ham chapga og‘ir.

Bu LL holati yuz berganda muvozanatni tiklash uchun muvozanatsiz tugunda bitta o‘ngga aylantirish yetarli.

LL holatini va muvozanat bitta o‘ngga aylantirish orqali qanday tiklanishini ko‘rish uchun quyidagi animatsiyani qadamma-qadam kuzating.

Yuqoridagi animatsiyani qadamma-qadam kuzatganingizda ikkita LL holati yuz beradi:

1. D qo‘shilganda Q’ning muvozanat koeffitsiyenti -2 ga teng bo‘ladi, bu daraxt muvozanatsiz ekanini bildiradi. Bu LL holati, chunki muvozanatsiz Q tuguni ham, uning chap bola tuguni P ham chapga og‘ir (manfiy muvozanat koeffitsiyentlari). Q tugunida bitta o‘ngga aylantirish daraxt muvozanatini tiklaydi.
2. L, C va B tugunlari qo‘shilgandan so‘ng P’ning muvozanat koeffitsiyenti -2 bo‘ladi, bu daraxt muvozanatdan chiqqanini bildiradi. Bu ham LL holati, chunki muvozanatsiz P tuguni ham, uning chap bola tuguni D ham chapga og‘ir. Bitta o‘ngga aylantirish muvozanatni tiklaydi.

O‘ng-O‘ng (RR) holati

O‘ng-O‘ng holati tugun muvozanatsiz va o‘ngga og‘ir bo‘lib, uning o‘ng bola tuguni ham o‘ngga og‘ir bo‘lganda yuz beradi.

RR holatida muvozanatni tiklash uchun muvozanatsiz tugunda bitta chapga aylantirish yetarli.

Yuqoridagi animatsiyada RR holati ikki marta yuz beradi:

1. D tuguni qo‘shilganda A muvozanatsiz bo‘lib qoladi, A ham, B ham o‘ngga og‘ir. A tugunida chapga aylantirish daraxt muvozanatini tiklaydi.
2. E, C va F tugunlari qo‘shilgandan so‘ng B tuguni muvozanatsiz bo‘lib qoladi. Bu RR holati, chunki B tuguni ham, uning o‘ng bola tuguni D ham o‘ngga og‘ir. Chapga aylantirish daraxt muvozanatini tiklaydi.

Chap-O‘ng (LR) holati

Chap-O‘ng holati — muvozanatsiz tugun chapga og‘ir, lekin uning chap bola tuguni o‘ngga og‘ir bo‘lgan holat.

Bu LR holatida avval chap bola tugunda chapga aylantirish, so‘ngra dastlabki muvozanatsiz tugunda o‘ngga aylantirish bajariladi.

Chap-O‘ng holati qanday yuz berishi mumkinligini va muvozanatni tiklash uchun aylantirish amallari qanday bajarilishini ko‘rish uchun quyidagi animatsiyani qadamma-qadam kuzating.

Yuqoridagi animatsiyada AVL daraxtini qurayotganingizda Chap-O‘ng holati 2 marta yuz beradi va muvozanatni tiklash uchun aylantirish amallari talab qilinadi hamda bajariladi:

1. K qo‘shilganda Q tuguni -2 muvozanat koeffitsiyenti bilan muvozanatsiz bo‘lib qoladi, ya’ni u chapga og‘ir, uning chap bolasi E esa o‘ngga og‘ir, demak bu Chap-O‘ng holati.
2. C, F va G tugunlari qo‘shilgandan so‘ng K tuguni muvozanatsiz va chapga og‘ir bo‘lib qoladi, uning chap bola tuguni E esa o‘ngga og‘ir, demak bu Chap-O‘ng holati.

O‘ng-Chap (RL) holati

O‘ng-Chap holati — muvozanatsiz tugun o‘ngga og‘ir, uning o‘ng bola tuguni esa chapga og‘ir bo‘lgan holat.

Bu holatda avval muvozanatsiz tugunning o‘ng bolasida o‘ngga aylantirish, so‘ngra muvozanatsiz tugunning o‘zida chapga aylantirish bajaramiz.

O‘ng-Chap holati qanday yuz berishi mumkinligini va muvozanatni tiklash uchun aylantirishlar qanday bajarilishini ko‘rish uchun quyidagi animatsiyani qadamma-qadam kuzating.

B tugunini qo‘shgandan so‘ng O‘ng-Chap holatiga ega bo‘lamiz, chunki A tuguni muvozanatsiz va o‘ngga og‘ir bo‘lib qoladi, uning o‘ng bolasi esa chapga og‘ir. Muvozanatni tiklash uchun avval F tugunida o‘ngga aylantirish, so‘ngra A tugunida chapga aylantirish bajariladi.

Keyingi O‘ng-Chap holati G, E va D tugunlari qo‘shilgandan so‘ng yuz beradi. Bu O‘ng-Chap holati, chunki B muvozanatsiz va o‘ngga og‘ir, uning o‘ng bolasi F esa chapga og‘ir. Muvozanatni tiklash uchun avval F tugunida o‘ngga aylantirish, so‘ngra B tugunida chapga aylantirish bajariladi.

AVL daraxtlarida orqaga qaytib tekshirish (retracing)

AVL daraxtiga tugun qo‘shilgandan yoki undan tugun o‘chirilgandan so‘ng daraxt muvozanatsiz bo‘lib qolishi mumkin. Daraxt muvozanatsiz ekanini aniqlash uchun barcha ajdod tugunlarning balandliklarini yangilashimiz va muvozanat koeffitsiyentlarini qayta hisoblashimiz kerak.

Orqaga qaytib tekshirish (retracing) deb nomlanuvchi bu jarayon rekursiya orqali amalga oshiriladi. Qo‘shish yoki o‘chirishdan so‘ng rekursiv chaqiruvlar ildizga qarab orqaga qaytar ekan, har bir ajdod tugunning balandligi yangilanadi va muvozanat koeffitsiyenti qayta hisoblanadi. Agar biror ajdod tugunning muvozanat koeffitsiyenti -1 dan 1 gacha bo‘lgan oraliqdan tashqarida ekani aniqlansa, daraxt muvozanatini tiklash uchun o‘sha tugunda aylantirish bajariladi.

Quyidagi simulyatsiyada F tuguni qo‘shilgandan so‘ng C, E va H tugunlarining barchasi muvozanatsiz bo‘ladi, ammo orqaga qaytib tekshirish rekursiya orqali ishlagani sababli H tugunidagi muvozanatsizlik birinchi bo‘lib aniqlanadi va tuzatiladi, bu holatda esa bu E va C tugunlaridagi muvozanatsizlikni ham tuzatadi.

F tuguni qo‘shilgandan so‘ng kod ildiz tuguniga qarab orqaga qaytar ekan, muvozanat koeffitsiyentlarini hisoblab, orqaga qaytib tekshirishni bajaradi. H tuguniga yetib kelinib, -2 muvozanat koeffitsiyenti hisoblanganda o‘ngga aylantirish bajariladi. Faqat shu aylantirish bajarilgandan keyingina kod yuqoridagi E va C ajdod tugunlari uchun muvozanat koeffitsiyentlarini hisoblab, orqaga qaytib tekshirishni davom ettiradi.

Aylantirish tufayli E va C tugunlarining muvozanat koeffitsiyentlari F tuguni qo‘shilishidan oldingidek qoladi.

AVL daraxtiga tugun qo‘shishni amalga oshirish

Bu kod oldingi sahifadagi tugun qo‘shish uchun BST’ni amalga oshirishga asoslangan.

AVL daraxtidagi har bir tugun uchun BST’ga nisbatan faqat bitta yangi atribut bor, u ham bo‘lsa balandlik, ammo AVL daraxti o‘zini qanday qayta muvozanatlashi sababli AVL daraxtini amalga oshirish uchun ko‘plab yangi funksiyalar va qo‘shimcha kod qatorlari kerak bo‘ladi.

Quyidagi amalga oshirish yuqoridagi simulyatsiyadagi AVL daraxtini yaratish uchun belgilar ro‘yxati asosida AVL daraxtini quradi. Oxirgi qo‘shiladigan 'F' tuguni ham xuddi yuqoridagi simulyatsiyadagi kabi o‘ngga aylantirishni ishga tushiradi.

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

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    print('Rotate right on node',y.data)
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    return x

def leftRotate(x):
    print('Rotate left on node',x.data)
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

    if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

    # Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

    # Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

    # Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

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

# Inserting nodes
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)

AVL daraxtidan tugunni o‘chirishni amalga oshirish

Barg tugun bo‘lmagan tugunni o‘chirishda AVL daraxti in-order o‘tishda tugundan keyingi tugunni topish uchun minValueNode() funksiyasini talab qiladi. Bu oldingi sahifada tushuntirilganidek, ikkilik qidiruv daraxtidan tugunni o‘chirishdagi bilan bir xil.

AVL daraxtidan tugunni o‘chirish uchun tugun qo‘shish kodidagi kabi muvozanatni tiklovchi kod kerak bo‘ladi.

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

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

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        if node.left is None:
            temp = node.right
            node = None
            return temp
        elif node.right is None:
            temp = node.left
            node = None
            return temp

        temp = minValueNode(node.right)
        node.data = temp.data
        node.right = delete(node.right, temp.data)

    if node is None:
        return node

    # Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

    # Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

    # Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

    # Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

    # Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

AVL daraxtlarining vaqt murakkabligi

Quyidagi muvozanatlanmagan ikkilik qidiruv daraxtiga qarang. "M"ni qidirish 1 tasidan tashqari barcha tugunlarni solishtirish kerakligini anglatadi. Ammo quyidagi AVL daraxtida "M"ni qidirish uchun faqat 4 ta tugunga tashrif buyurishimiz kifoya.

Demak, eng yomon holatda qidirish, qo‘shish va o‘chirish kabi algoritmlar daraxtning butun balandligi bo‘ylab o‘tishi kerak. Bu shuni anglatadiki, AVL daraxtlaridagi kabi daraxt balandligini (\(h \)) past saqlash bizga kamroq bajarilish vaqtini beradi.

Quyida ikkilik qidiruv daraxtlari va AVL daraxtlarining vaqt murakkabliklari taqqoslanishini hamda vaqt murakkabliklari daraxt balandligi (\(h\)) va daraxtdagi tugunlar soni (\(n\)) bilan qanday bog‘liqligini ko‘ring.

• BST o‘zini o‘zi muvozanatlamaydi. Bu BST juda muvozanatsiz, deyarli uzun zanjirga o‘xshash bo‘lishi mumkinligini anglatadi, bunda balandlik tugunlar soniga deyarli teng bo‘ladi. Bu tugunlarni qidirish, o‘chirish va qo‘shish kabi amallarni sekinlashtiradi, vaqt murakkabligi \(O(h) = O(n)\) bo‘ladi.
• AVL daraxti esa o‘zini o‘zi muvozanatlaydi. Bu daraxt balandligi minimal darajada saqlanishini anglatadi, shuning uchun tugunlarni qidirish, o‘chirish va qo‘shish kabi amallar ancha tezroq bajariladi, vaqt murakkabligi \(O(h) = O( \log n)\) bo‘ladi.

\(O( \log n)\) haqida tushuntirish

Balandligi \(h\) va tugunlari soni \(n\) bo‘lgan AVL daraxtida qidirish, qo‘shish va o‘chirish uchun vaqt murakkabligi \(O(h) = O( \log n)\) ekanini quyidagicha tushuntirish mumkin:

Eng pastki darajadan tashqari barcha tugunlari ikkitadan bola tugunga ega bo‘lgan mukammal ikkilik daraxtni tasavvur qiling, masalan, quyidagi AVL daraxti kabi.

Bunday AVL daraxtidagi har bir darajadagi tugunlar soni:

\[1, 2, 4, 8, 16, 32, ..\]

Bu quyidagiga teng:

\[2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ..\]

Balandligi \(h=3\) bo‘lgan mukammal ikkilik daraxtdagi tugunlar soni \(n\) ni olish uchun har bir darajadagi tugunlar sonini qo‘shishimiz mumkin:

\[n_3=2^0 + 2^1 + 2^2 + 2^3 = 15\]

Bu aslida quyidagiga teng:

\[n_3=2^4 - 1 = 15\]

Va bu aslida kattaroq daraxtlar uchun ham to‘g‘ri! Masalan, balandligi \(h=5 \) bo‘lgan daraxtdagi tugunlar soni \(n \) ni olmoqchi bo‘lsak, tugunlar sonini quyidagicha topamiz:

\[n_5=2^6 - 1 = 63\]

Demak, umumiy holda mukammal ikkilik daraxtning balandligi \(h \) va undagi tugunlar soni \(n \) orasidagi bog‘liqlikni quyidagicha ifodalash mumkin:

\[n_h = 2^{h+1} - 1\]

AVL daraxtida tugunni qidirish, o‘chirish yoki qo‘shishning vaqt murakkabligi \(O(h) \) ekanini bilamiz, ammo vaqt murakkabligi aslida \(O(\log(n)) \) ekanini asoslamoqchimiz, shuning uchun tugunlar soni \(n\) orqali ifodalangan balandlik \(h\) ni topishimiz kerak:

\[ \begin{equation} \begin{aligned} n & = 2^{h+1}-1 \\ n+1 & = 2^{h+1} \\ \log_2(n+1) & = \log_2(2^{h+1}) \\ h & = \log_2(n+1) - 1 \\ \\ O(h) & = O(\log{n}) \end{aligned} \end{equation} \]

Yuqoridagi oxirgi qator qanday keltirib chiqarilgani yaqqol bo‘lmasligi mumkin, ammo ko‘p tugunli (katta \(n\)) ikkilik daraxt uchun vaqt murakkabligini ko‘rib chiqayotganimizda "+1" va "-1" hadlari muhim emas. Big O notatsiyasi yordamida vaqt murakkabligini hisoblash haqida batafsilroq ma’lumot uchun ushbu sahifaga qarang.

Yuqoridagi hisob-kitoblar AVL daraxtidagi qidirish, o‘chirish va qo‘shish amallari uchun vaqt murakkabligi \(O(h) \) ni aslida \(O(\log{n}) \) ko‘rinishida ifodalash mumkinligini ko‘rsatadi, bu tez, BST’larning \(O(n) \) vaqt murakkabligidan ancha tez.

DSA mashqlari

Mashqlar yordamida o‘zingizni sinang

Mashq:

Quyidagi AVL daraxtidagi har bir tugun o‘zining muvozanat koeffitsiyenti bilan birga ko‘rsatilgan:

Muvozanat koeffitsiyenti nima?

The balance factor is the 
difference between each node's 
left and right subtree .

Javobni yuborish »

Mashqni boshlash