AVL daraxtlar
AVL daraxti ikki sovet ixtirochi Georgiy Adelson-Velskiy va 1962 yilda AVL daraxtini ixtiro qilgan Evgeniy Landis nomi bilan atalgan Ikkilik qidiruv daraxtining bir turi.
AVL daraxtlari o‘z-o‘zini muvozanatlashtiradi, ya’ni daraxt balandligi minimal darajada saqlanadi, shuning uchun tugunlarni qidirish, kiritish va o‘chirish uchun juda tez ish vaqti kafolatlanadi, vaqt murakkabligi \(O( \log n)\).
AVL daraxtlari
Oddiy ikkilik qidiruv daraxti bilan AVL daraxti orasidagi yagona farq shundaki, AVL daraxtlari daraxt muvozanatini saqlash uchun qo‘shimcha ravishda aylantirish (rotation) amallarini bajaradi.
Chap va o‘ng pastki daraxtlar orasidagi balandlik farqi 2 dan kam bo‘lsa, Ikkilik qidiruv daraxti muvozanatda bo‘ladi.
Balansni saqlab, AVL daraxti minimal daraxt balandligini ta’minlaydi, ya’ni qidirish, kiritish va o‘chirish operatsiyalari juda tez bajarilishi mumkin.
(unbalanced)
Height: 6
(self-balancing)
Height: 3
Yuqoridagi ikkita daraxt ikkilik qidiruv daraxtlari bo‘lib, ular bir xil tugunlarga ega va bir xil tartib bo‘yicha o‘tish (alifbo bo‘yicha), lekin balandligi juda farq qiladi, chunki AVL daraxti o‘zini muvozanatlashtirgan.
Balans omillari qanday yangilanishini va muvozanatni tiklash uchun kerak bo‘lganda aylanish operatsiyalari qanday bajarilishini ko‘rish uchun quyidagi animatsiyada AVL daraxti qurilishi bo‘ylab qadam qo‘ying.
Balans omili qanday hisoblanganligi, aylanish operatsiyalari qanday amalga oshirilishi va AVL daraxtlarini qanday amalga oshirish mumkinligi haqida ko‘proq ma’lumot olish uchun o‘qishni davom eting.
Chapga va o‘ngga aylanish
AVL daraxtida muvozanatni tiklash uchun chap yoki o‘ng aylanishlar yoki chap va o‘ng aylanishlarning kombinatsiyasi amalga oshiriladi.
Oldingi animatsiya bitta aniq chap aylanishni va bitta o‘ngga aylantirishni ko‘rsatadi.
Ammo umuman olganda, chap va o‘ng aylanishlar quyidagi animatsiyadagi kabi amalga oshiriladi.
Pastki daraxt ota-onasini qanday o‘zgartirganiga e’tibor bering. To‘g‘ri tartibli o‘tishni ta’minlash va daraxtdagi barcha tugunlar uchun chap bola o‘ng bo‘lakdan kamroq bo‘lgan BST xususiyatini saqlab qolish uchun pastki daraxtlar aylanish jarayonida ota-onani shu tarzda o‘zgartiradi.
Shuni ham yodda tutingki, bu har doim ham ildiz tugunlari muvozanatsiz bo‘lib qolmaydi va aylanishni talab qiladi.
Balans omili
Tugunning muvozanat omili pastki daraxt balandligidagi farqdir.
AVL daraxtidagi barcha tugunlar uchun pastki daraxt balandliklari har bir tugunda saqlanadi va muvozanat koeffitsienti daraxtning muvozanatdan chiqib ketganligini tekshirish uchun uning pastki daraxt balandliklari asosida hisoblanadi.
Pastki daraxtning balandligi pastki daraxtning ildiz tuguni va shu pastki daraxtdagi eng pastdagi barg tugunlari orasidagi qirralarning soni.
Tugun (\(X\)) uchun Balans omili (\(BF\)) uning o‘ng va chap pastki daraxtlari orasidagi balandlikdagi farqdir.
\[ BF(X) = height(rightSubtree(X)) - height(leftSubtree(X)) \]
Balans omil qiymatlari
- 0: tugun muvozanatda.
- 0 dan ortiq: tugun "o‘ng og‘ir".
- 0 dan kam: tugun "chap og‘ir".
Agar daraxtning bir yoki bir nechta tugunlari uchun muvozanat koeffitsienti -1 dan kam yoki 1 dan ortiq bo‘lsa, daraxt muvozanatda emas deb hisoblanadi va muvozanatni tiklash uchun aylanish operatsiyasi kerak.
Keling, AVL daraxti muvozanatni tiklash uchun qila oladigan turli aylanish operatsiyalarini batafsil ko‘rib chiqaylik.
To‘rtta "muvozanatdan tashqari" holat
Bitta tugunning muvozanat koeffitsienti -1 dan kam yoki 1 dan ortiq bo‘lsa, daraxt muvozanatsiz deb hisoblanadi va muvozanatni tiklash uchun aylanish kerak.
AVL daraxti muvozanatdan chiqib ketishining to‘rt xil usuli mavjud va bu holatlarning har biri boshqa aylanish jarayonini talab qiladi.
| Case | Tavsif | Muvozanatni tiklash uchun aylantirish |
|---|---|---|
| Left-Left (LL) | Balanssiz tugun va uning chap tugunlari ikkalasi ham chapdan og‘irroqdir. | Bitta o‘ngga aylantirish. |
| Right-Right (RR) | Balanssiz tugun va uning o‘ng tugunlari ikkalasi ham o‘ng va og‘irdir. | Bitta chapga aylantirish. |
| Left-Right (LR) | Balanssiz tugun og‘ir, chap tugun esa o‘ngda og‘ir. | Avval chap bola tugunida chap aylanishni bajaring, so‘ngra muvozanatsiz tugunni o‘ngga aylantiring. |
| Right-Left (RL) | Balanssiz tugun o‘ng og‘ir va uning o‘ng bola tugun chap og‘ir. | Avval o‘ng bola tugunida o‘ng aylanishni bajaring, so‘ngra muvozanatsiz tugunni chapga aylantiring. |
Quyida ushbu holatlarning animatsiyalari va tushuntirishlarini ko‘ring.
Chap-chap (LL) ishi
Nomutanosiblik aniqlangan tugun og‘ir, chap tugun tugunida ham og‘ir qoladi.
Ushbu LL holati sodir bo‘lganda, muvozanatni tiklash uchun muvozanatsiz tugunni bitta o‘ngga aylantirish kifoya qiladi.
LL holatini va bir marta o‘ngga aylanish orqali balans qanday tiklanganini ko‘rish uchun quyidagi animatsiyani ko‘ring.
Yuqoridagi animatsiyadan o‘tayotganingizda ikkita LL holatlari sodir bo‘ladi:
- D qo‘shilganda, Q ning muvozanat koeffitsienti -2 ga aylanadi, ya’ni daraxt muvozanatsizdir. Bu LL holati, chunki Q muvozanatsiz tuguni ham, uning chap tugun P tugunlari ham og‘ir bo‘lib qolgan (salbiy balans omillari). Q tugunida bitta o‘ngga aylanish daraxt muvozanatini tiklaydi.
- L, C va B tugunlari qo‘shilgandan so‘ng, P ning muvozanat koeffitsienti -2 ga teng, ya’ni daraxt muvozanatdan chiqib ketgan. Bu ham LL holatidir, chunki muvozanatsiz P tugun va uning chap tugun D tugunlari og‘ir bo‘lib qolgan. Bitta o‘ng aylanish muvozanatni tiklaydi.
Eslatma: Yuqoridagi animatsiyada ikkinchi marta LL holi sodir bo‘lganda, o‘ngga aylantirish amalga oshiriladi va L D ning o‘ng bolasidan P ning chap bolasi bo‘lishiga o‘tadi. To‘g‘ri ketma-ket o‘tishni (yuqoridagi animatsiyada “B, C, D, L, P, Q”) saqlash uchun aylanishlar shunday amalga oshiriladi. Aylanish amalga oshirilganda ota-onani o‘zgartirishning yana bir sababi BST xususiyatini saqlab qolishdir, chap bola har doim tugundan past bo‘ladi va o‘ng bola har doim yuqori bo‘ladi.
O‘ng-o‘ng (RR) ishi
O‘ng-o‘ng holati tugun muvozanatsiz va o‘ng og‘ir bo‘lsa va o‘ng bola tugun ham o‘ng og‘ir bo‘lsa sodir bo‘ladi.
Balanssiz tugundagi bitta chap aylanish RR holatida muvozanatni tiklash uchun yetarli.
RR hodisasi yuqoridagi animatsiyada ikki marta sodir bo‘ladi:
- D tugunlari kiritilganda, A muvozanatsiz bo‘ladi va A va B botlari juda og‘ir. A tugunidagi chap burilish daraxt muvozanatini tiklaydi.
- E, C va F tugunlari kiritilgandan so‘ng, B tugunida muvozanat buziladi. Bu RR holati, chunki B tugunlari ham, uning o‘ngdagi D tugunlari ham og‘ir. Chapga aylanish daraxt muvozanatini tiklaydi.
Chap-o‘ng (LR) holati
Chap-o‘ng holati muvozanatsiz tugun og‘ir bo‘lsa, lekin uning chap tugun tugunlari o‘ngda og‘ir bo‘ladi.
Ushbu LR holatida chapga aylanish birinchi navbatda chap bola tugunida amalga oshiriladi, so‘ngra o‘ngga aylanish asl muvozanatsiz tugunda amalga oshiriladi.
Chap-o‘ng holati qanday sodir bo‘lishi mumkinligini va muvozanatni tiklash uchun aylanish operatsiyalari qanday bajarilishini ko‘rish uchun quyidagi animatsiyani ko‘ring.
Yuqoridagi animatsiyada AVL daraxtini qurayotganingizda, chap-o‘ng holati 2 marta sodir bo‘ladi va aylanish operatsiyalari talab qilinadi va muvozanatni tiklash uchun amalga oshiriladi:
- K kiritilsa, Q tugunining muvozanat koeffitsienti -2 bo‘lganligi sababli muvozanat buziladi, shuning uchun u og‘ir qoldiriladi va uning chap bolasi E o‘ng og‘ir, shuning uchun bu Chap-O‘ng holatidir.
- C, F va G tugunlari kiritilgandan so‘ng, K tugun muvozanatsiz bo‘lib, chapda og‘irlashadi, chap asosiy tugun E o‘ngga og‘ir bo‘ladi, shuning uchun u Chap-O‘ng holatidir.
O‘ng-chap (RL) ishi
O‘ng-chap holati muvozanatsiz tugun o‘ngga og‘ir bo‘lsa va uning o‘ng asosiy tugunlari og‘ir bo‘lsa.
Bunday holda, biz birinchi navbatda muvozanatsiz tugunning o‘ng bolasida o‘ngga, keyin esa muvozanatsiz tugunning o‘zida chapga aylanishni amalga oshiramiz.
O‘ng-chap holati qanday paydo bo‘lishi va muvozanatni tiklash uchun aylanishlar qanday amalga oshirilishini ko‘rish uchun quyidagi animatsiyani ko‘ring.
B tugunini kiritgandan so‘ng, biz o‘ng-chap holatini olamiz, chunki A tugun muvozanatsiz va o‘ngga og‘ir bo‘lib qoladi va uning o‘ng qismi og‘ir bo‘lib qoladi. Muvozanatni tiklash uchun avval F tugunida o‘ngga, keyin esa A tugunida chapga aylanish amalga oshiriladi.
Keyingi o‘ng-chap holati G, E va D tugunlari qo‘shilgandan keyin sodir bo‘ladi. Bu O‘ng-Chap holati, chunki B muvozanatsiz va o‘ng og‘ir, va uning o‘ng bolasi F chap og‘ir. Muvozanatni tiklash uchun avval F tugunida o‘ngga, so‘ngra B tugunida chapga aylanish amalga oshiriladi.
AVL daraxtlarida qayta izlash
AVL daraxtiga tugun qo‘shgandan yoki o‘chirilgandan so‘ng, daraxt muvozanatsiz bo‘lishi mumkin. Daraxtning muvozanatsiz yoki yo‘qligini bilish uchun biz balandliklarni yangilashimiz va barcha ajdod tugunlarining muvozanat omillarini qayta hisoblashimiz kerak.
Retracing deb nomlanuvchi bu jarayon rekursiya orqali amalga oshiriladi. Qo‘shish yoki o‘chirishdan so‘ng rekursiv chaqiruvlar ildizga qarab qaytganda, har bir ajdod tugunining balandligi yangilanadi va balans omili qayta hisoblab chiqiladi. Agar biron bir ajdod tugunida -1 dan 1 gacha bo‘lgan diapazondan tashqarida muvozanat omili borligi aniqlansa, daraxtning muvozanatini tiklash uchun bu tugunda aylanish amalga oshiriladi.
Quyidagi simulyatsiyada, F tugunini kiritgandan so‘ng, C, E va H tugunlari muvozanatsiz bo‘ladi, lekin rekursiya yo‘li bilan ishlayotganligi sababli, birinchi navbatda H tugunidagi nomutanosiblik topiladi va tuzatiladi, bu holda E va C tugunlaridagi nomutanosiblik ham tuzatiladi.
F tugunini kiritgandan so‘ng, kod ildiz tuguniga yo‘naltirilganda muvozanatlash omillarini hisoblab, orqaga qaytadi. H tuguniga erishilganda va muvozanatlash omili -2 hisoblanganda, to‘g‘ri aylanish amalga oshiriladi. Faqatgina bu aylanish amalga oshirilgandan so‘ng, kod E va C ajdodlari tugunlarida muvozanatlash omillarini hisoblab, orqaga qaytishni davom ettiradi.
Aylanish tufayli E va C tugunlari uchun muvozanatlash omillari F tugunining kiritilishidan oldingi kabi qoladi.
Pythonda AVL daraxtini amalga oshirish
Ushbu kod tugunlarni qo‘shish bo‘yicha oldingi sahifadagi BST realizatsiyasiga asoslangan.
BST bilan solishtirganda AVL daraxtidagi har bir tugun uchun faqat bitta yangi atribut mavjud va bu balandlikdir, lekin AVL daraxti o‘zini qanday muvozanatlashtirgani uchun AVL daraxtini amalga oshirish uchun ko‘plab yangi funksiyalar va qo‘shimcha kod qatorlari kerak.
Quyidagi dastur yuqoridagi simulyatsiyada AVL daraxtini yaratish uchun belgilar ro‘yxati asosida AVL daraxtini yaratadi. "F" qo‘shiladigan oxirgi tugun ham xuddi yuqoridagi simulyatsiyadagi kabi o‘ngga aylanishni ishga tushiradi.
Misol
Pythonda AVL daraxtini amalga oshirish:
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)
Misolni ishga tushirish »
AVL o‘chirish tugunini amalga oshirish
Barg tugunlari bo‘lmagan tugunni o‘chirishda AVL daraxti navbatdagi o‘tishda tugunning keyingi tugunini topish uchun minValueNode() funksiyasini talab qiladi. Bu avvalgi sahifada tushuntirilganidek, Ikkilik qidiruv daraxtidagi tugunni o‘chirish bilan bir xil.
AVL daraxtidagi tugunni o‘chirish uchun balansni tiklash uchun bir xil kod tugunni kiritish kodiga kerak bo‘ladi.
Misol
Tugunni o‘chirish:
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)
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)
Misolni ishga tushirish »
AVL daraxtlari uchun vaqt murakkabligi
Quyidagi muvozanatsiz Ikkilik qidiruv daraxtiga qarang. "M" ni qidirish 1 dan tashqari barcha tugunlarni solishtirish kerakligini anglatadi. Ammo quyidagi AVL daraxtida "M" ni qidirish bizdan faqat 4 ta tugunga tashrif buyurishimizni talab qiladi.
Shunday qilib, eng yomon holatda, qidirish, kiritish va o‘chirish kabi algoritmlar daraxtning butun balandligi bo‘ylab ishlashi kerak. Bu shuni anglatadiki, daraxtning balandligini (h) past darajada ushlab turish, xuddi AVL Trees-dan foydalanganimiz kabi, bizga kamroq ishlash vaqtini beradi.
(unbalanced)
(self-balancing)
Quyida Ikkilik qidiruv daraxtlari va AVL daraxtlari o‘rtasidagi vaqt murakkabliklarining taqqoslanishi va vaqt murakkabligi daraxtning balandligi (\(h\)) va daraxtdagi tugunlar soni (\(n\)) bilan qanday bog‘liqligini ko‘ring.
- BST o‘z-o‘zini muvozanatlashtirmaydi. Bu shuni anglatadiki, BST juda muvozanatsiz bo‘lishi mumkin, deyarli uzun zanjir kabi, balandligi tugunlar soni bilan deyarli bir xil. Bu vaqt murakkabligi \(O(h) = O(n)\) bilan, qidiruv, o‘chirish va tugunlarni kiritish kabi operatsiyalarni sekinlashtiradi.
- Biroq, AVL daraxti o‘z-o‘zini muvozanatlashtiradi. Bu shuni anglatadiki, daraxtning balandligi minimal bo‘lib qoladi, shuning uchun tugunlarni qidirish, o‘chirish va kiritish kabi operatsiyalar vaqt murakkabligi \(O(h) = O( \log n)\) bilan tezroq amalga oshiriladi.
\(O( \log n)\) izohi
Vaqt murakkabligi \(O(h) = O( \log n)\) balandligi \(h\) va tugunlari \(n\) bo‘lgan AVL daraxtida qidirish, qo‘shish va o‘chirish uchun ekanligini quyidagicha izohlash mumkin:
Mukammal Ikkilik daraxtni tasavvur qiling-a, bu yerda barcha tugunlarda ikkita asosiy tugun mavjud, masalan, quyida joylashgan AVL daraxti kabi.
Bunday AVL daraxtidagi har bir darajadagi tugunlar soni:
\[1, 2, 4, 8, 16, 32, ..\]
Bu bir xil:
\[2^0, 2^1, 2^2, 2^3, 2^4, 2^5, ..\]
Balandligi \(h=3\) bo‘lgan mukammal Ikkilik daraxtda \(n\) tugunlar sonini olish uchun har bir darajadagi tugunlar sonini qo‘shishimiz mumkin:
\[n_3=2^0 + 2^1 + 2^2 + 2^3 = 15\]
Bu aslida bir xil:
\[n_3=2^4 - 1 = 15\]
Va bu aslida katta daraxtlar uchun ham shundaydir! Masalan, balandligi \(h=5\) bo‘lgan daraxtdagi \(n \) tugunlar sonini olishni istasak, quyidagi tugunlar sonini topamiz:
\[n_5=2^6 - 1 = 63\]
Umuman olganda, mukammal Ikkilik daraxtning balandligi \(h \) va undagi tugunlar soni \(n \) o‘rtasidagi munosabatni quyidagicha ifodalash mumkin:
\[n_h = 2^{h+1} - 1\]
Eslatma: Yuqoridagi formulani geometrik qatorlar yig‘indisini hisoblash yo‘li bilan ham topish mumkin \(2^0 + 2^1 + 2^2+ 2^3 + ... + 2^n \)
Biz bilamizki, AVL daraxtiga tugunni qidirish, o‘chirish yoki kiritish uchun vaqt murakkabligi \(O(h) \), lekin biz vaqt murakkabligi aslida \(O(\log(n)) \), shuning uchun \(n\) tugunlar soni bilan tavsiflangan \(h\) balandligini topishimiz kerak, deb bahslashmoqchimiz:
\[ \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 string qanday olinganligi aniq bo‘lmasligi mumkin, lekin juda ko‘p tugunlari (katta \(n\)) bo‘lgan Ikkilik daraxt uchun "+1" va "-1" atamalar vaqt murakkabligini hisobga olgan holda muhim emas. Big O notation yordamida vaqt murakkabligini qanday hisoblash haqida ko‘proq ma’lumot olish uchun ushbu sahifaga qarang.
Yuqoridagi matematika shuni ko‘rsatadiki, AVL daraxtida qidirish, o‘chirish va qo‘shish operatsiyalari \(O(h) \), aslida \(O(\log{n}) \) shaklida ifodalanishi mumkin, bu tez va BSTlar uchun vaqt murakkabligi \(O(n) \) dan ancha tezdir.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!