b daraxtlar

PPTX 17 pages 208.8 KB Free download

17 pages

FaylHub.uz

Download via Telegram

Size 208.8 KB

File type PPTX

Pages 17

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 17

10-mavzu: b daraxtlar 10-mavzu: b daraxtlar “axborot texnologiyalari” kafedrasi katta o‘qituvchisi x.x.ikromov reja: b daraxti ta’rifi b daraxtda amallar b-daraxtni realizatsiya qilish b daraxti 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 bo‗ladi. 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 daraxt strukturasi b daraxti mukammal muvozanatlashgan, ya'ni uning barcha barglarining chuqurligi bir xil. t – bu daraxt parametrlari, b daraxtining minimal darajasi deyiladi, 2 dan kam emas xususiyatlari 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 …

2 / 17

h b daraxtda izlash algoritmi 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 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. b daraxtlarda element qoʻshish izlashdan farqli o'laroq, qo'shish usuli ikkilik daraxtga qaraganda ancha murakkab, chunki yangi barg yaratish va unga kalit qo'yish mumkin emas, chunki b daraxtining xususiyatlari buziladi. kalitni allaqachon to'ldirilgan bargga kiritish mumkin emas. tugunni ikkiga bo'lish amali kerak, agar barg to'ldirilgan bo'lsa, unda 2t-1 kalit bor edi. 2 ga t-1 ga bo'lamiz undan kam kalitlar va oxirgi t-1 ajdod tuguniga o'tkaziladi. shunga ko'ra, agar …

3 / 17

ga kiritiladi. bu holda b daraxtining barcha xususiyatlari saqlanib qolgan. element oʻchirish 1) agar bargdan o'chirish sodir bo'lsa, unda qancha kalit borligini tekshirish kerak. agar t-1 dan ko'p bo'lsa, biz shunchaki o'chirib tashlaymiz va boshqa hech narsa qilishimiz shart emas. aks holda, agarda t-1 dan ortiq kalitlarni o'z ichiga oluvchi qo'shni barg bo'lsa (uning yonida joylashgan va avlod-ajdodi bir xil bo'lsa), biz qo'shni tugunning qolgan kalitlari orasidagi ajratuvchi bo'lgan bu qo'shnidan kalitni tanlaymiz. bu kalit k1 bo'lsin. avval tugunni va uning qo'shnisini ajratuvchi asosiy tugundan k2 kalitini tanlaymiz. kerakli kalitni manba tugundan olib tashlaylik (o'chirilishi kerak edi), bu tugunga k2 ni tushiring va ajdod tugunidagi k2 o'rniga k1 qo'ying. tushunarli bo'lishi uchun quyida "9" tugmasi o'chirilgan rasm (48 -rasm) ko'rsatilgan. agar bizning tugunning barcha qo'shnilarida t-1 kalitlari bo'lsa. keyin biz uni qo'shnisi bilan birlashtiramiz, kerakli kalitni o'chirib tashlaymiz va bu ikkita "sobiq" qo'shnilar uchun ajratuvchi bo'lgan avlod-ajdod tugunining kaliti, yangi …

4 / 17

$ildizdan chiqariladi (keyingi tugunda t-1 avlodlari ko'p bo'lgan holat) 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) * 2 * t - 1); node->value = malloc(sizeof(*node->value) 2 * t - 1); node->child = malloc(sizeof(*node->child) 2 * t); return node; } b-daraxtni realizatsiya qilish b daraxtda element izlash void btree_lookup(struct btree *tree, int key, struct btree **node, int *index) { int i; for (i = 0; i nkeys && key > tree->key[i]; ) { i++; } if (i 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 = …$

5 / 17

$->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++; 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 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 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); tree = btree_insert(tree, 12, 0); tree = btree_insert(tree, 9, 0); tree = btree_insert(tree, 18, 0); return 0; } mavzu yuzasidan savollar: b daraxt nima? b daraxtda izlash qanday amalga …$

Want to read more?

Download all 17 pages for free via Telegram.

Download full file

About "b daraxtlar"

10-mavzu: b daraxtlar 10-mavzu: b daraxtlar “axborot texnologiyalari” kafedrasi katta o‘qituvchisi x.x.ikromov reja: b daraxti ta’rifi b daraxtda amallar b-daraxtni realizatsiya qilish b daraxti 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 bo‗ladi. 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 daraxt strukturasi b daraxti mukammal muvozanatlashgan, ya'ni uning barcha barglarining chuqurligi bir xil. t – bu daraxt para...

This file contains 17 pages in PPTX format (208.8 KB). To download "b daraxtlar", click the Telegram button on the left.

Tags: b daraxtlar PPTX 17 pages Free download Telegram