|
-rasm. B daraxtda element oʻchirish algoritmining bajarilishiBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI48-rasm. B daraxtda element oʻchirish algoritmining bajarilishi
2) Endi x ichki tugunidan k kalitini olib tashlashni ko'rib chiqaylik.
Agar k kalitidan oldingi avlod tugunida t -1 dan ortiq kalitlar bo'lsa, biz
k
1
ni topamiz - bu tugunning pastki daraxtida k. Uni o'chirib tashlaymiz
(Algoritmni rekursiv tarzda ishga tushiramiz). Manba tugundagi k ni k
1
bilan almashtiramiz. Agar k kalitidan keyingi avlod tugunida t-1 dan
ortiq kalit bo'lsa, biz ham xuddi shunday ishni bajaramiz. Agar
ikkalasida ham (keyingi va oldingi avlod tugunlarida) t-1 kalitlari bo'lsa,
biz bu avlodlarni birlashtiramiz, k-ni ularga o'tkazamiz, so'ngra k-ni
yangi tugundan olib tashlaymiz (biz algoritmimizni rekursiv tarzda ishga
136
tushiramiz). Agar ildizning oxirgi 2 avlodi birlashsa, ular ildizga
aylanadi va oldingi ildiz olib tashlanadi. Rasm quyida koʻrsatilgan (49-
rasm), bu yerda "11" ildizdan chiqariladi (keyingi tugunda t-1 avlodlari
ko'p bo'lgan holat).
O'chirish jarayoni O (t logt n) qo'shilishi bilan bir xil vaqtni oladi va
disk operatsiyalari faqat O (h) talab qilinadi, bu yerda h - daraxt
balandligi.
49-rasm. B daraxtda element oʻchirish algoritmining bajarilishi
10.3. B-daraxtni realizatsiya qilish
/* B-daraxtning minimum darajasi*/
#define T 2
/* 2-3-4 B-tree */
struct btree {
int leaf;
int nkeys;
int *key;
int *value;
struct btree **childj
};
B-daraxtni hosil qilish
struct btree *btree_create()
{
struct btree *node;
node = malloc(sizeof(*node));
node->leaf = 1;
node->nkeys = 0;
node->key = malloc(sizeof(*node->key) *
|
| |
