Mavzu: b daraxtlar b daraxtlarda amallar

B daraxtda element izlash dasturini tahlil qiling.

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);
} else {
*node = NULL;
}

7. 
   Quyidagi daraxt strukturasini tushuntiring.
   

Bu daraxt B daraxt hisoblanadi, bunda elementlar har bir kalitdan kichik bo’lsa chap tomonga , agar katta bo’lsa o’ng tomonga yozilayabdi. Har bir bargada B daraxt hususiyatini yoqatmayabdi. Yani har bir bargdagi ildizlari sonidan bitta ortiq barg chiqmoqda. Masalan Ildiz kalitlarimiz ikkita undan chiqgan kalitlar soni uchta , 10 kalitimizda o’zi turubdi bunda ikkita barg chiqgan, yani bu daraxt to’liqligicha B daraxt xuxusiyatini saqlagan.

8. 
   Quyidagi B daraxtlarda element qo’shish strukturasini tushuntiring.
   

B daraxtda elament qo’shishni tahlil qilamiz. Avval 8 sonini qo’shilgan yani o’zi yoziladi, undan so’ng 9 kiritilgan bunda uni 8 yoniga yozamiz sababi ildiz kalit bitta undan 2 ta barg chiqadi bizning elament esa bitta demak 8 va 9 yonmayon yoziladi. 10 raqamini kiritamiz bunda demak elamentlar 2 ta bo’ldi barg chiqsa bo’ladi buyerdagi sonlardan o’rtasidagi qiymat ildiz kalit bo’ladi va unda kichigi chap tomonga ildiz kalit dan kattasi esa o’ng tomonga yoziladi. Demak 9 ildiz kalit ,8 soni 9 ning chap tomoniga 10 soni esa 9 ning o’ng tomoniga yoziladi.
11 ni qo’shamiz , 11 soni 9 katta demak o’ng tomonga o’ng tomondagi kalit bitta bo’lganligi uchun shu kalit yoniga yozilad i yani 10 ning yoniga. 15 sonini qo’shganimizda 9 o’ng tomonidagi barglar uchta bo’ladi bunda o’ng tomondagi kalitlardan o’rtadagisi ildiz kalitga chiqadi yani 11 soni natija 9 va 11 ildiz kalit bo’ladi, va barglarda chapda 8 soni o’rtada 10 va o’ngda 15 kalitlar bo’ladi.. 20 sonini qo’shsak u 11 katta dema o’ng tomoniga tushadi. 15 yoniga tushadi. 17 soni qo’shganimizda u ham 15 va 20 yoniga tushadi ammo bunda kalitlar soni ortib ketadi shuning uchun ikkiga bo’linadi va o’rtadagi son ildiz kalitga chiqadi. Bundan ildiz kalitlar 9 , 11 va 17 bo’ladi barglar 8,10,15 va 20 bo’ladi. Bunda ildiz kalitlar soni ortgani uchun ularning o’rtadagi soni yagona ildiz kalit qilinadi yani 11 soni yuqoriga chiqadi. Demak elament qo’shganimizdan so’ng daraxt o’z xususiyatini yoqatmadi.

9. 
   Quyidagi elementlarni tartiblangan B daraxt ko’rinishida daraxtni hosil qiling. 7, 8, 10, 12, 15, 20, 22,100
   

10. 
    C++ da B daraxtlarga element qo’shish.
    

#include
usingnamespacestd;
classNode {
int *keys;
int t;
Node **C;
int n;
boolleaf;
public:
Node(int _t, bool _leaf);
voidinsertNonFull(int k);
void splitChild(int i, Node *y);
voidtraverse();
friendclassBTree;
};
classBTree {
Node *root;
int t;
public:
BTree(int _t) {
root = NULL;
t = _t;
}

voidtraverse() {

if (root != NULL)
root->traverse();
}

voidinsert(int k);

};

Node::Node(int t1, bool leaf1) {

t = t1;
leaf = leaf1;

keys = newint[2 * t - 1];

C = newNode *[2 * t];

n = 0;
}

// Traversethenodes
voidNode::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout<< " " <}

if (leaf == false)

C[i]->traverse();
}

// Insertthenode

void BTree::insert(int k) {
if (root == NULL) {
root = new Node(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
Node *s = new Node(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;

if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);

root = s;

} else
root->insertNonFull(k);
}
}

// Insertnonfullcondition

void Node::insertNonFull(int k) {
int i = n - 1;

if (leaf == true) {

while (i>= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;

n = n + 1;
} else {
while (i>= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1) {

splitChild(i + 1, C[i + 1]);

if (keys[i + 1] < k)

i++;
}
C[i + 1]->insertNonFull(k);
}
}

// splitthechild

void Node::splitChild(int i, Node *y) {
Node *z = new Node(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)

z->keys[j] = y->keys[j + t];

if (y->leaf == false) {

for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;

for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];

n = n + 1;
}

intmain() {

BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);

cout<< "The B-tree is: ";

t.traverse();
}