Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

133 

Bu kalitning chap tomonidagi avlodga tushamiz. 

27 dan kichik boʻlgunga qadar yangi tugunni kalit boʻyicha 
izlaymiz. Bunday holda, biz 27 ni topdik va to'xtadik. 
46-rasm. a) B daraxtda izlash algoritmining bajarilishi 
Izlash amali O(t*logt n) vaqtida bajariladi, bu yerda 
t
- minimal 
daraja. Bu yerda disk amallarini faqat O (logt n) da bajarishimiz muhim 
qismidir. 
B daraxtlarda element qoʻshish. 
Izlashdan farqli o'laroq, qo'shish 
usuli ikkilik daraxtga qaraganda ancha murakkab, chunki yangi barg 
yaratish va unga kalit qo'yish mumkin emas, chunki B daraxtining 
xususiyatlari buziladi. Kalitni allaqachon to'ldirilgan bargga kiritish 
mumkin emas. Tugunni ikkiga bo'lish amali kerak, agar barg to'ldirilgan 
bo'lsa, unda 
2t-1
kalit bor edi. 2 ga 
t-1
ga bo'lamiz undan kam kalitlar va 
oxirgi t-1 ajdod tuguniga o'tkaziladi. Shunga ko'ra, agar avlod-ajdod 
tuguni ham to'lgan bo'lsa, yana bo'lishimiz kerak va shunga o'xshash 
ildizgacha (agar ildiz ajralgan bo'lsa, unda yangi ildiz paydo bo'ladi va 
daraxt chuqurligi oshadi). Oddiy ikkilik daraxtlar singari, joylashtirish 
ham ildizdan barggacha bir o'tishda amalga oshiriladi.Har bir 
iteratsiyada (yangi kalit uchun pozitsiyani qidirishda - ildizdan 
barggacha) o'tadigan barcha to'ldirilgan tugunlarni ajratamiz (bargni 
ham o'z ichiga olgan holda). Shunday qilib, agar natijada tugunni 
ajratish zarur bo'lsa, uning avlod-ajdodi to'ldirilmaganligiga koʻrishimiz 
mumkin. 

134 
Quyidagi 47-rasmda xuddi o'sha daraxt qidirilmoqda (t = 3). Faqat 
hozir biz "15" kalitini qo'shamiz. Yangi kalitning o'rnini qidirib,
a) 
b)

Download 4,61 Mb.