muvozanatlangan binar daraxtlar

PPTX 14 стр. 3,8 МБ Бесплатная загрузка

14 стр.

FaylHub.uz

Скачать через Telegram

Размер 3,8 МБ

Тип файла PPTX

Страницы 14

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 14

prezentatsiya powerpoint 1 muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti ma’lumotlar tuzilmasi va algoritmlar muvozanatlangan binar daraxtlar butunov dilshod muvozanatlangan binar daraxtlar daraxtni muvozanatlash algoritmi binar daraxt muvozanatlangan yoki avl-muvozanatlangan bo’lishi mumkin. daraxtavl-muvozanatlangan (1962 yil sovet olimlari adelson, velsk georgiy maksimovich va landis yevgeniya mihaylovichlar tomonidan taklif qilingan) deyiladi, agar daraxtdagi har bir tugunning chap va o’ng qism daraxtlari balandliklari farqi 1 tadan ko’p bo’lmasa. berilgan butun sonlar – kalitlar ketma-ketligidan binar daraxt yaratib olamiz va uni muvozanatlaymiz. daraxtni muvozanatlashdan maqsad, bunday daraxtga yangi element kiritish va daraxtdan element izlash algoritmi samaradorligini oshirishdan iborat, ya’ni bu amallarni bajarishdagi solishtirishlar soni kamayadi. binar daraxtni muvozanatlash algoritmi quyidagicha bo’ladi. algoritm binar daraxtni yaratib olamiz. binar daraxtni chapdan o’ngga ko’rikdan o’tkazamiz va tugunlarning info maydonlaridan a[..] massiv hosil qilamiz. tabiiyki, massiv o’sish bo’yicha tartiblangan bo’ladi. muvozanatlangan daraxtning tugunlarini belgilash uchun massivni ko’riladigan oralig’ini belgilab olamiz, ya’ni start=0 va end=n-1. massivning ko’rilayotgan oralig’i o’rtasida …

2 / 14

$nt start, int end) { if(start>end) return null; else { int mid=(start+end)/2; node *tree=new node; tree->info=arr[mid]; tree->left=new_tree(arr,start,mid-1); tree->right=new_tree(arr,mid+1,end); return tree; } } informatika fanida oʻz-oʻzini muvozanatlashtirgan ikkilik qidiruv daraxti (bst) har qanday tugunga asoslangan ikkilik qidiruv daraxti boʻlib, u oʻz balandligini (ildiz ostidagi sathlarning maksimal soni) oʻzboshimchalik bilan element qoʻshish va oʻchirish holatlarida avtomatik ravishda kichik darajada saqlaydi.[1] o'z-o'zini muvozanatlashtiruvchi ikkilik qidiruv daraxti uchun mo'ljallangan ushbu operatsiyalar daraxt balandligining cheksiz o'sishiga qarshi ehtiyot choralarini o'z ichiga oladi, shuning uchun bu mavhum ma'lumotlar tuzilmalari "o'zini muvozanatlash" atributini oladi. balandligi muvozanatli ikkilik daraxtlar uchun balandlik logarifmik {\displaystyle {\mathcal {o}}(\log n)}{\displaystyle {\mathcal {o}}(\log n)} sonida aniqlanadi. \displaystyle n}n element. bu avl daraxtlari va qizil-qora daraxtlar kabi ko'plab ikkilik qidiruv daraxtlariga tegishli. splay daraxtlari va treaplar o'z-o'zidan muvozanatlashadi, lekin balandlikda muvozanatlashmaydi, chunki ularning balandligi elementlar soni bo'yicha logarifmik bo'lishi kafolatlanmaydi. o'z-o'zini muvozanatlashtirgan ikkilik qidiruv daraxtlari o'zgaruvchan tartibli ro'yxatlar uchun samarali ilovalarni ta'minlaydi va assotsiativ …$

3 / 14

$rn vec; } prenode.push_back(node->data); preorder(node->left); preorder(node->right); return prenode; } int main() { vector v = { 4, 3, 1, 2 }; node* root = createbst(v, 0, v.size() - 1); vector ans = preorder(root); for (auto i : ans) { cout left); h2 = height(tree->right); if (h1>h2) return (1 + h1); else return (1 + h2); } } binar daraxtni muvozanatlanganmi yoki yo’qligini tekshirish daraxtning balandligini aniqlashni o’rganganimizdan keyin uning muvoza-natlanganligini tekshirish mumkin. binar daraxtning muvozanatlanganligini tekshirish uchun uning har bir tugunini har ikkala qismdaraxti balandliklarini hisoblab, farqlarini tekshirib ko’rish kerak. agar farq 0 yoki 1 ga teng bo’lsa, bu muvozanatlangan daraxt hisoblanadi. quyida binar daraxtni muvozanatlanganlikka tekshirishning rekursiv funksiyasini qo’llovchi dastur keltirilgan dastur kodi #include #include using namespace std; class node{ public: int info; node *left; node *right; }; int k=0,flag=1; int height(node *tree){ int h1,h2; if (tree==null) return (-1); else { h1 = height(tree->left); h2 = height(tree->right); if (h1>h2) …$

4 / 14

$ur kodi quyidagi a-rasmdagi daraxtni konsol ekranida b-rasm ko’rinishda ifodalaydi. a-rasm b-rasm e’tiboringiz uchun rahmat! image2.jpeg image3.jpeg image4.png image5.svg image6.png image7.svg image8.png image9.jpeg image10.jpeg image11.png image12.jpeg image13.jpeg image14.jpeg image15.jpeg image16.jpeg .msftofcthm_background1_fill { fill:#000000; } binary tree 18 int mid = (start + end) / 25 19 node* root - new node(v[mid]); 20 root->left - createbst(v, start, mid - 1); 2 root->right - createbst(v, mid + 1, end); 22 return roots 23 } 24 vector prenode, vec; 25 vector preorder(node* node) 26-{ 27 if (node == null) { 28 return vecs 29 } 38 prenode. push_back(node->data) ; 31 preorder (node->left); 32 preorder(node->right) ; 33 return prenodes 34 } 35. int main() 36~ff 37 vector v = { 10, 5, 6, 4, 3, 8, 1, 2, 7,9. 5 38 node” root = createbst(v, 0, v-size() - 1)3 39 vector ans = preorder(root); 40 for (auto i: ans) { 41 | cout << …$

5 / 14

muvozanatlangan binar daraxtlar - Page 5

Хотите читать дальше?

Скачайте все 14 страниц бесплатно через Telegram.

Скачать полный файл

О "muvozanatlangan binar daraxtlar"

prezentatsiya powerpoint 1 muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti ma’lumotlar tuzilmasi va algoritmlar muvozanatlangan binar daraxtlar butunov dilshod muvozanatlangan binar daraxtlar daraxtni muvozanatlash algoritmi binar daraxt muvozanatlangan yoki avl-muvozanatlangan bo’lishi mumkin. daraxtavl-muvozanatlangan (1962 yil sovet olimlari adelson, velsk georgiy maksimovich va landis yevgeniya mihaylovichlar tomonidan taklif qilingan) deyiladi, agar daraxtdagi har bir tugunning chap va o’ng qism daraxtlari balandliklari farqi 1 tadan ko’p bo’lmasa. berilgan butun sonlar – kalitlar ketma-ketligidan binar daraxt yaratib olamiz va uni muvozanatlaymiz. daraxtni muvozanatlashdan maqsad, bunday daraxtga yangi element kiritish va daraxtdan element izlash algoritmi...

Этот файл содержит 14 стр. в формате PPTX (3,8 МБ). Чтобы скачать "muvozanatlangan binar daraxtlar", нажмите кнопку Telegram слева.

Теги: muvozanatlangan binar daraxtlar PPTX 14 стр. Бесплатная загрузка Telegram