Algoritm tushunchasi

AVL daraxt. AVL-daraxt (inglizcha AVL-Tree) bu
muvozanatlashgan ikkilik qidiruv daraxti boʻlib, unda quyidagi
xususiyat qoʻllab-quvvatlanadi: uning har bir uchlari uchun uning ikkita
ostki daraxtining balandligi 1 dan koʻp boʻlmagan qiymatga farq qiladi.
AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan
foydalanishni taklif qilgan G. M. Adelson-Velskiy va E. M. Landisning
ismlarining birinchi harflari bilan nomlangan.

34 AVL daraxti
AVL daraxt. AVL-daraxt (inglizcha AVL-Tree) bu
muvozanatlashgan ikkilik qidiruv daraxti boʻlib, unda quyidagi
xususiyat qoʻllab-quvvatlanadi: uning har bir uchlari uchun uning ikkita
ostki daraxtining balandligi 1 dan koʻp boʻlmagan qiymatga farq qiladi.
AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan
foydalanishni taklif qilgan G. M. Adelson-Velskiy va E. M. Landisning
ismlarining birinchi harflari bilan nomlangan.
AVL daraxtiga yangi tugun kiritilganda paydo boʻladigan
variantlarni koʻrib chiqaylik:
• hl=hR. Yoqilgandan soʻng, L va R har xil balandliklarga aylanadi,
ammo muvozanat mezonlari buzilmaydi;
• hLmuvozanat mezonlari yanada yaxshilanadi;
• hL>hR. Yoqilgandan soʻng muvozanat mezonlari buziladi va
daraxtni qayta qurish kerak.
Shunday qilib, biz AVL daraxtiga yangi tugunni kiritish uchun
umumiy algoritmni tuzamiz:
1. Kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun
daraxtni aylanib oʻtish;
2. Yangi uchni kiritish va natijada balans koʻrsatkichini aniqlash;
3. Qidiruv yoʻli boʻylab "orqaga chekinish" va har bir uchda balans
koʻrsatkichini tekshirish. Agar kerak boʻlsa, muvozanatni saqlash.


35 AVL daraxtlarining samaradorligini tahlil qilish
AVL daraxt. AVL-daraxt (inglizcha AVL-Tree) bu
muvozanatlashgan ikkilik qidiruv daraxti boʻlib, unda quyidagi
xususiyat qoʻllab-quvvatlanadi: uning har bir uchlari uchun uning ikkita
ostki daraxtining balandligi 1 dan koʻp boʻlmagan qiymatga farq qiladi.
AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan
foydalanishni taklif qilgan G. M. Adelson-Velskiy va E. M. Landisning
ismlarining birinchi harflari bilan nomlangan.
AVL daraxtiga yangi tugun kiritilganda paydo boʻladigan
variantlarni koʻrib chiqaylik:
• hl=hR. Yoqilgandan soʻng, L va R har xil balandliklarga aylanadi,
ammo muvozanat mezonlari buzilmaydi;
• hLmuvozanat mezonlari yanada yaxshilanadi;
• hL>hR. Yoqilgandan soʻng muvozanat mezonlari buziladi va
daraxtni qayta qurish kerak.
Shunday qilib, biz AVL daraxtiga yangi tugunni kiritish uchun
umumiy algoritmni tuzamiz:
1. Kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun
daraxtni aylanib oʻtish;
2. Yangi uchni kiritish va natijada balans koʻrsatkichini aniqlash;
3. Qidiruv yoʻli boʻylab "orqaga chekinish" va har bir uchda balans
koʻrsatkichini tekshirish. Agar kerak boʻlsa, muvozanatni saqlash.


36 B-daraxtlar
B daraxti (inglizcha B-tree) – izlash, qo'shish va o'chirish imkonini
beradigan, juda koʻpshoxli muvozanatlashgan qidiruv daraxti. Tugunlari
n bo'lgan B daraxti O(logn) balandlikka ega bo‘ladi. Tugun shoxlari soni
bittadan bir necha minggacha bo'lishi mumkin (odatda, B-daraxtining
shoxlanish darajasi daraxt ishlaydigan qurilma (disklar) xususiyatlari
bilan belgilanadi). B-daraxtlar O(logn) ko'p dinamik to'plam amallarini
o'z vaqtida bajarish uchun ham ishlatilishi mumkin.
B daraxti birinchi marta 1970-yilda R. Bayer va E. Makkreyt
tomonidan taklif qilingan.