Mavzu: b daraxtlar b daraxtlarda amallar

Mavzu:B daraxtlar. B daraxtlarda amallar.

1. 
   B daraxtlarning strukturasini tushuntiring.
   

B daraxt mukammal muvozanatlashgan , yani uning hamma uchlarining chuqurligi bir hilda . B daraxt ildizdan tashqari har bir tugun t-1 ta kalitni o’z ichiga oladi va har bir ichki tugun t avlodli tugun bo’ladi. Har bir tugun ildizdan tashqari 2t-1 kalitni o’z ichiga oladi va ko’pi bilan 2t avlodi bo’ladi.Har bir tugunning kalitlari kamaymaydigan tartibda joylashtirilgan. Barcha barglar bir hil darajada. Yuqorida aytilgan t bu darxtning parametirlari u B darxtni minimal darajasi deyiladi , u 2 dan kam emas. B daraxtlar disklarda yoki to’g’ridan to’g’ri saqlash mumkin bo’lmagan muhitlarda ,shuningdek , malimotlar bazasidan foydalanish uchun mo’ljallangan.

2. 
   B daraxtda izlash algoritmini tushuntiring.
   

B daraxtlarda ham huddi boshqa daraxlarga o’xshab ammallar bajarish mumkin . B daraxtda izlash amali xuddi binar daraxtga o’xshab ketadi. B daraxtda izlash , avval ildiz kalitlar orasidan qidirayotgan sonimiz qaysi oraliqda ekanligini qidirib ko’ramiz . Ildiz kalitlar ichidan oraliqni topganimizdan so’ng , o’sha oraliq bo’yicha pastga tushamiz va kalitlar ichidan chapdan o’nga qarab qidiramiz. Izlash amali O(t*logtn) vaqtda bajariladi. t –minimal daraja.

3. 
   B daraxtlarda element qo’shish algoritmini tushuntiring.
   

B daraxtga element qo’shish binar daraxtdan murakkab hisoblanadi, sababi B daraxtda binar daraxtga o’xshab elementdi barga ko’shib ketib bo’lmaydi. B daraxtda tugun to’lgan bo’lsa tugundi ikkiga bo’lish amali ishlatiladi. Agar barg to’lgan bo’lsa unda 2t-1 ta kalit bor, uni ikkiga bo’lganda yangi ikkita tugunda t-1 bo’lamiz unda elament kam kalitga o’tkaziladi.Elament qo’shish amali O(tlogtn)vaqtda bajariladi.

4. 
   B daraxtlarda element o’chirish algoritmini tushuntiring
   

B daraxtda elament o’chirish , elament qo’shishdan ham murakkab hisoblanadi. Buning sababi shundaki , ichki tugundi olib tashlash daraxtni butunlay tiklash degani.Elament o’chirganimizda B daraxt hususiyatini ko’rib chiqishimiz kerak bu holda biz kalitni t-1 bo’lishini kuzatamiz. Agarda daraxtdagi barglarning kalitlari soni t-1 tadan ortiq bo’lsa , elamentni to’g’ridan to’g’ri o’chirib yuborsak bo’ladi. Ammo t-1 dan kam bo’lsa bunday qilib bo’lmaydi. Unda qo’shni barglardagi kalitlar soni t-1 tadan ortiq bo’lsa undagi kalitlardan birini ildiz kalitlar oldiga chiqaib ildiz kalitdagi kalitni t-1 da kalitdan kam bo’lgan barga tushiramiz va elamentni o’chirib yuborsak bo’ladi.

5. 
   B-daraxtni hosil qilish dasturini tahlil qiling.
   

struct btree *btree_create()

{
struct btree *node;
node = malloc(sizeof(*node));
node->leaf = 1;
node->nkeys = 0;
node->key = malloc(sizeof(*node->key) *
2 * T - 1);
node->value = malloc(sizeof(*node->value)
2 * T - 1);
node->child = malloc(sizeof(*node->child)
2 * T);
return node;
}

6.