3-ma’ruza “tartiblangan va muvozanatlashgan daraxtlar (avl-daraxt)”

PPTX 29 sahifa 2,4 MB Bepul yuklash

29 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 2,4 MB

Fayl turi PPTX

Sahifalar 29

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 29

1-ma’ruza. ma’lumotlar bazasining maqsadi, vazifalari va asosiy tushunchalari 3-ma’ruza. tartiblangan va muvozanatlashgan daraxtlar avl daraxt avl-daraxt (inglizcha avl-tree) bu muvozanatlashgan ikkilik qidiruv daraxti bo'lib, unda quyidagi xususiyat qo'llab-quvvatlanadi: uning har bir uchlari uchun uning ikkita ostki daraxtining balandligi 1 dan ko'p bo'lmagan farq qiladi. avl daraxtlari birinchi marta 1962-yilda avl daraxtlaridan foydalanishni taklif qilgan g.m. adelson-velskiy va e.m. landisning ismlarining birinchi harflari bilan nomlangan. muvozanatlash uchlarni muvozanatlash - bu chap va o'ng pastki daraxtlari balandliklari farqi bo'lgan taqdirda, daraxtining xususiyati tiklanishi uchun ushbu uchlarning pastki daraxtidagi ajdod va avlod munosabatlarini o'zgartiradigan amal, aks holda hech narsani o'zgartirmaydi. muvozanatlash uchun biz har bir uch uchun uning chap va o'ng pastki daraxtlari balandliklari orasidagi farqni saqlaymiz. muvozanatlash daraxtning balandligi uning maksimal darajasi, ildizdan tashqi tugunga qadar eng uzun yo'lning uzunligi sifatida aniqlanadi. ikkilik qidiruv daraxti muvozanatli deyiladi, agar biron bir tugunning chap pastki daraxtining balandligi o'ng pastki daraxtning balandligidan ± 1 dan …

2 / 29

'rib chiqaylik: • hl=hr. yoqilgandan so'ng, l va r har xil balandliklarga aylanadi, ammo muvozanat mezonlari buzilmaydi; • hl hr. yoqilgandan so'ng muvozanat mezonlari buziladi va daraxtni qayta qurish kerak. muvozanatlashgan daraxtlar shunday qilib, biz avl daraxtiga yangi tugunni kiritish uchun umumiy algoritmni tuzamiz: 1. kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun daraxtni aylanib o'tish; 2. yangi uchni kiritish va natijada balans ko'rsatkichini aniqlash; 3. qidiruv yo'li bo'ylab "orqaga chekinish" va har bir uchda balans ko'rsatkichini tekshirish. agar kerak bo'lsa, muvozanatni saqlash. amalda avl balansini tiklashning 4 algoritmi qo'llaniladi:muvozanat ko'rsatkichlari qiymatiga qarab tanlangan kichik va katta chap burilish, kichik va katta o'ng burilish (rasm) kichik chap burilish algoritmi kichik o’ng burilish algoritmi katta chap burilish algoritmi katta o’ng burilish algoritmi muvozanatlashgan daraxtlar rasmlarda to'rtburchaklar pastki daraxtlarni bildiradi, ichidagi raqamlar kichik daraxtlarning raqamlari, tugunlar yonidagi raqamlar balans ko'rsatkichlari. balanslash algoritmi chap tomonga burilishning quyidagi misolida keltirilgan. boshlang’ich daraxt muvozanatlashgan daraxtlar …

3 / 29

o'ng pastki daraxtini aniqlash muvozanatlashgan daraxtlar 7. ko'rsatkichning qiymatini daraxtning ildiziga o'zgartiring (p) va balans qiymatini tiklang: 8. (*p).bal=0; p=p1; 4-rasm. "yangi" ildizning o'ng pastki daraxtini aniqlash muvozanatlashgan daraxtlar muvonazatlash algortmidan so'ng, avl bo'yicha muvozanatlashgan quyidagi daraxt hosil bo‘ldi: dastlabki daraxt muvozanatlashgan daraxt avl daraxtlarining samaradorligini tahlil qilish n elementni o'z ichiga olgan avl daraxtining balandligini yuqoridan baholaylik. h balandlikdagi avl daraxtini hosil qilish uchun zarur bo'lgan minimal tugunlarni n (h) bilan belgilaymiz. avl daraxtlarining samaradorligini tahlil qilish avl daraxtlarining samaradorligini tahlil qilish fibonachchi ketma-ketligining h –hadi uchun binet formulasidan oltin nisbat avl daraxtlarining samaradorligini tahlil qilish avl daraxtining h (n) balandligi uchun yuqori chegara avl daraxtidan tugunlarni olib tashlash avl daraxtidan barcha tugunlarni olib tashlash tugundan kalit bo’yicha izlash tugun hosil qilish daraxtni ekranda chiqarish daraxtni ekranda chiqarish (davomi) image2.png image2.tmp image4.png image3.tmp image4.tmp image5.tmp image6.tmp image7.tmp image8.tmp image9.tmp image10.tmp image11.tmp image12.tmp image13.tmp image14.tmp image15.tmp image16.tmp image17.tmp image18.tmp image19.tmp …

4 / 29

3-ma’ruza “tartiblangan va muvozanatlashgan daraxtlar (avl-daraxt)” - Page 4

5 / 29

3-ma’ruza “tartiblangan va muvozanatlashgan daraxtlar (avl-daraxt)” - Page 5

Ko'proq o'qimoqchimisiz?

Barcha 29 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"3-ma’ruza “tartiblangan va muvozanatlashgan daraxtlar (avl-daraxt)”" haqida

1-ma’ruza. ma’lumotlar bazasining maqsadi, vazifalari va asosiy tushunchalari 3-ma’ruza. tartiblangan va muvozanatlashgan daraxtlar avl daraxt avl-daraxt (inglizcha avl-tree) bu muvozanatlashgan ikkilik qidiruv daraxti bo'lib, unda quyidagi xususiyat qo'llab-quvvatlanadi: uning har bir uchlari uchun uning ikkita ostki daraxtining balandligi 1 dan ko'p bo'lmagan farq qiladi. avl daraxtlari birinchi marta 1962-yilda avl daraxtlaridan foydalanishni taklif qilgan g.m. adelson-velskiy va e.m. landisning ismlarining birinchi harflari bilan nomlangan. muvozanatlash uchlarni muvozanatlash - bu chap va o'ng pastki daraxtlari balandliklari farqi bo'lgan taqdirda, daraxtining xususiyati tiklanishi uchun ushbu uchlarning pastki daraxtidagi ajdod va avlod munosabatlarini o'zgartiradigan amal, aks holda...

Bu fayl PPTX formatida 29 sahifadan iborat (2,4 MB). "3-ma’ruza “tartiblangan va muvozanatlashgan daraxtlar (avl-daraxt)”"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: 3-ma’ruza “tartiblangan va muvo… PPTX 29 sahifa Bepul yuklash Telegram