B daraxtiga kirish algoritmi , b daraxtida element qo‘shish va o‘chirish algoritmi
![Biroq, B-daraxt ko'plab kalitlarni bitta tugunda saqlashi va bir nechta tugunlarga
ega bo'lishi mumkin. Bu balandlikni sezilarli darajada pasaytiradi, diskka tezroq
kirish imkonini beradi.
Asosiy qismi
1-BOB
B daraxt tarifi
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 boladi. 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 k1, ..., kn kalitlari bo'lgan barglardan tashqari n +
1 avlodlari
bor. i-avlodda [ki-1; ki], k0 = -∞, kn+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
3](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_3.png?v=1)
![Elementni qidirish algoritmi
BtreeSearch(x, k)
i = 1
while i ≤ n[x] and k ≥ keyi[x]
do i = i + 1
if i n[x] and k = keyi[x]
then return (x, i)
if leaf [x]
then return NIL
else
return BtreeSearch(ci[x], k)
Turli xil B-daraxt operatsiyalari haqida ko'proq ma'lumot olish uchun tashrif
buyuring. Yuqorida aytib o'tilganidek, B daraxti barcha standart qidirish, qo'shish,
o'chirish va hokazo amallarni bajaradi.
B daraxtida izlash binar daraxtni qidirishga juda o'xshaydi, faqat bu yerda biz
avlodga yo'lni 2 variantdan emas, balki bir nechta variantdan tanlashimiz kerak.
Aks holda, farqi bo'lmay qoladi. Quyidagi 1-rasmda 27-kalitni qidirish ko'rsatilgan.
Tasvirni koʻrib chiqaylik (va shunga mos ravishda standart qidirish algoritmi):
Biz ildiz kalitlarini kerak bo'lguncha o'tamiz. Bu holda 31 ga yetdik.
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.
1-rasm. B daraxtda izlash algoritmining bajarilishi
74 17 31
1 2 3 7 9 11 13 16
19 26 27
96 97 99](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_7.png?v=1)
![{
struct btree *node;
node = malloc(sizeof(*node));
node->leaf = 1;
node->nkeys = 0;
node->key = malloc(sizeof(*node->key) * 137 2 * T - 1); node->value =
malloc(sizeof(*node->value) 2 * T - 1); node->child = malloc(sizeof(*node->child)
2 * T);
return node;
}
B daraxtda element izlash
void btree_lookup(struct btree *tree, int key, struct btree **node, int *index)
{
int i;
for (i = 0; i < tree->nkeys && key > tree->key[i]; )
{
i++;
}
if (i < tree->nkeys && key == tree->key[i])
{
*node = tree;
index = I;
return;
}
if (!tree->leaf) {
/* Disk read tree->child[i] */
btree_lookup(tree, key, node, index);
}
11](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_11.png?v=1)
![else {
*node = NULL;
}
B daraxtda element qoʻshish
struct btree *btree_insert(struct btree *tree, int key, int value)
{
struct btree *newroot;
if (tree == NULL)
{
tree = btree_create();
tree->nkeys = 1;
tree->key[0] = key;
tree->value[0] = value; return tree;
}
if (tree->nkeys == 2 * T - 1)
{
newroot = btree_create(); /* Create empty root */
newroot->leaf = 0;
newroot->child[0] = tree;
btree_split_node(tree, newroot, 0);
return btree_insert_nonfull(newroot, key, value);
}
return btree_insert_nonfull(tree, key, value);
}
B-daraxtda tugunni ajratish
void btree_split_node(struct btree *node, struct btree *parent, int index)
{
12](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_12.png?v=1)
![struct btree *z;
int i;
z = btree_create();
z->leaf = node->leaf;
z->nkeys = T - 1;
for (i = 0; i < T - 1; i++)
{
z->key[i] = node->key[T + i];
z->value[i] = node->value[T + i];
}
if (!node->leaf)
{
for (i=0; i<T; i++;)
z->ichild[i] = node->child[i + T]j
}
node->nkeys = T - 1;
/* Ajdod tugunga mediana kalitni kiritish */
for (i = parent->nkeys; i >= 0 && i <= index + lj i--)
parent->child[i + 1] = parent->child[i];
parent->child[index + 1] = z;
for (i = parent->nkeys - 1; i >= 0 && i <= index; i--)
parent->key[i + 1] = parent->key[i];
parent->value[i + 1] = parent->value[i];
}
parent->key[index] = node->key[T - 1];
parent->value[index] = node->value[T - 1];
parent->nkeys++;
13](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_13.png?v=1)
![struct btree *btree_insert_nonfull( struct btree *node, int key, int value)
{
int i;
i = node->nkeys;
if (node->leaf)
{ for (i = node->nkeys - 1; i > 0 && key < node->key[i]; i--) {
node->key[i + 1] = node->key[i]
}
node->key[i + 1] = key;
node->nkeys++;
}
Else
{
for (i = node->nkeys - 1; i > 0 && key < node->key[i];
{
i--;
}
i++;
if (node->child[i]->nkeys == 2 * T - 1)
{
btree_split_node(node->child[i], node, i);
if (key > node->key[i])
i++J }
node = btree_insert_nonfull(node->child[i], key, value);
}
return node;
}
14](https://docx.uz/documents/1b6b9c05-0362-44d7-8067-c6d34b3bb34c/page_14.png?v=1)
B daraxtiga kirish algoritmi , b daraxtida element qo‘shish va o‘chirish algoritmi