Tugundan kalit boʻyicha izlash funksiyasi

129 
Daraxtni ekranda chiqarish funksiyasi
void avltree_print_dfs(struct avltree *tree, int level) 
{ 
int i; 
if (tree == NULL) 
return; 
for (i = 0; i < level; i++) 
printf(" "); 
printf("%d\n", tree->key); 
avltree_print_dfs(tree->left, level + 1); 
avltree_print_dfs(tree->right, level + 1); 
} 
int main() 
{ 
struct avltree *tree = NULL; 
tree = avltree_add(tree, 5, "5"); 
tree = avltree_add(tree, 3, "3"); 
/* Code */ 
avltree_free(tree); 
return 0; 
}

130 
Mavzu yuzasidan savollar: 
1. AVL daraxti nima? 
2. Uchlarni muvozanatlash deganda nimani tushunasiz. 
3. Tugundan kalit boʻyicha izlash funksiyasini tushuntirib bering. 
4. Muvozanatlashgan daraxt tushunchasi nima? 
5. Daraxt ma‘lumotlar strukturasi qoʻllaniladigan sohalarga qaysilar 
kiradi? 
Mustaqil ishlash uchun masalalar: 
1. AVL daraxtida tugun olib tashlash funksiyasini yozing va uni 
daraxtda qoʻllang. 
2. Kalit boʻyicha izlash funksiyasini optimallashtiring. 
 
 

131 
10-§. B daraxtlar 
10.1. B daraxt ta‟rifi 
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. 
B daraxt strukturasi. 
B daraxti mukammal muvozanatlashgan, 
ya'ni uning barcha barglarining chuqurligi bir xil. B daraxti quyidagi 
xususiyatlarga ega ( t – bu daraxt parametrlari, B daraxtining 
minimal 
darajasi
deyiladi, 2 dan 
kam
emas ): 

Ildizdan tashqari har bir tugun hech bo'lmaganda 
t-1 
kalitni o'z 
ichiga oladi va har bir ichki tugun kamida avlodli
t
tugunlarga ega. Agar 
daraxt bo'sh bo'lmasa, ildizda kamida bitta kalit bo'lishi kerak. 

Har bir tugun, ildizdan tashqari, ichki tugunlarda ko'pi bilan 
2t - 1
kalitni va ko'pi bilan 
2t
avlodni o'z ichiga oladi 

Ildizda daraxt bo'sh bo'lmasa bittadan 
2t-1
gacha kalit va 
balandligi 0 dan katta bo'lsa 2 dan 2t gacha avlodni o'z ichiga oladi. 

Daraxtning har bir tugunida k
1
, ..., k
n
kalitlari bo'lgan barglardan 
tashqari n + 1 avlodlari bor. i-avlodda [k
i-1
; k
i
], k
0
= -∞, k
n+1
=∞ 
kesmaning kalitlari mavjud. 

Har bir tugunning kalitlari kamaymaydigan tartibda tartiblangan. 

Barcha barglar bir xil darajada. 
B daraxtlar disklarda (fayl tizimlarida) yoki boshqa to'gʻridan-to'gʻri 
kiruvchi bo'lmagan saqlash muhitlarida, shuningdek, ma'lumotlar 
bazalarida foydalanish uchun mo'ljallangan. B daraxtlar qizil-qora 
daraxtlarga o'xshaydi, lekin ular diskni o'qish/yozish amallarini 
minimallashtirishda yaxshiroq hisoblanadi. 

132 
Daraxtlar - bu dinamik to'plam amallarni bajaradigan ma'lumotlar 
tuzilmalari. Bunday amallar sifatida elementni qidirish, minimal 
(maksimal) elementni qidirish, kiritish, o'chirish, avlod-ajdodga o'tish, 
avlodga o'tish kabilarni keltirish mumkin. Shunday qilib, daraxt oddiy 
lugʻat sifatida ham, ustivor navbat sifatida ham ishlatilishi mumkin. 
Daraxtlardagi asosiy amallar uning balandligiga mutanosib vaqtda 
bajariladi. 
Muvozanatlashgan 
daraxtlar 
ularning 
balandligini 
kamaytiradi (masalan, tugunlari bo'lgan ikkilik muvozanatli daraxtning 
balandligi 
logn
).
Bu standart qidiruv daraxtlarida qanday muammo bor? Oldingi 
mavzularda aytib o'tilgan daraxtlardan biri tasvirlangan ulkan 
ma'lumotlar bazasini ko'rib chiqaylik. Shubhasiz, bu daraxtlarning 
barchasini tezkor xotirada saqlay olmaymiz – ma'lumotlarning faqat bir 
qismini saqlaymiz, qolganlari uchinchi tomon vositasida saqlanadi 
(masalan, kirish tezligi ancha past bo'lgan qattiq diskda). Qizil-qora yoki 
Dekart kabi daraxtlar uchinchi tomon vositalariga kirishni talab qiladi. 
Katta 
n
lar uchun bu juda ko'p. Aynan mana shu muammo B daraxtlar 
hal qilish imkonini beradi. 
B daraxtlari ham muvozanatlashgan daraxtlardir, shuning uchun 
standart amallarni bajarish uchun vaqt balandlikka mutanosib. Ammo, 
boshqa daraxtlardan farqli o'laroq, ular maxsus disk xotirasi bilan ishlash 
uchun yaratilgan (oldingi misolda - uchinchi tomon tarqatuvchi), 
aniqrogʻi ular kirish -chiqish turidagi murojaatlarni kamaytiradi. 

Download 4,61 Mb.