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);
} 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;
138
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)
{
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
z->child[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];
139
}
parent->key[index] = node->key[T - 1];
parent->value[index] = node->value[T - 1];
parent->nkeys++;
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;
}
int main()
{
struct btree *tree;
tree = btree_insert(NULL,
3, 0);
140
tree = btree_insert(tree, 12, 0);
tree = btree_insert(tree, 9, 0);
tree = btree_insert(tree, 18, 0);
return 0;
}
Mavzu yuzasidan savollar:
1. B daraxt nima
2. B daraxtda izlash qanday amalga oshiriladi?
3. B daraxtda element oʻchirish qanday amalga oshiriladi?
4. B daraxtda element qoʻshish qanday amalga oshiriladi?
5. B-daraxt ma‘lumotlar strukturasi qoʻllaniladigan sohalarga
qaysilar kiradi?
Mustaqil ishlash uchun masalalar:
1. B daraxtida element olib tashlash funksiyasini yozing va uni
daraxtda qoʻllang
2. B-daraxtda element qoʻshish funksiyasini optimallashtiring
11-§. Ustivor navbatlar
Ko'pgina ilovalar kalitlarga ega bo'lgan elementlarni qayta ishlashni
talab qiladi, lekin ular to'liq tartibda va birdaniga hammasi emas.
Ko'pincha, biz bir qator narsalarni to'playmiz, so'ngra eng katta kalit
bilan ishlov beramiz, keyin ko'proq narsalarni to'playmiz, so'ngra hozirgi
eng katta kalit bilan ishlov beramiz va hokazo. Bunday muhitda tegishli
ma'lumotlar turi ikkita amalni qo'llab-quvvatlaydi: maksimal miqdorni
oʻchirish va joylashtirish. Bunday ma'lumotlar turi
ustivor navbat
deb
nomlanadi.
Ustivor navbatlar odatdagi navbat yoki stek ma'lumotlar tuzilmasiga
o'xshash abstrakt ma'lumotlar turi bo'lib, unda har bir element
qo'shimcha ravishda bogʻliq bo'lgan "ustivorlikka" ega. Ustivor
navbatda yuqori ustivor element past ustivor elementdan oldin xizmat
qiladi.
141
Ustivor navbatlar ko'pincha uyum (kucha) bilan amalga oshirilsa-da,
ular konseptual jihatdan uyumlardan farq qiladi. Ustivor navbat - bu
"ro'yxat" yoki "karta" ga o'xshash narsa; Ro'yxat bogʻlangan ro'yxat yoki
massiv yordamida amalga oshirilishi mumkin bo'lganidek, ustivor
navbat uyum yoki tartiblanmagan massiv kabi boshqa usullar yordamida
amalga oshirilishi mumkin.
|
