“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Daraxtdan tugunlarni olib tashlash

• Tugunni ikkilik qidiruv daraxti uchun qabul qilingan standart qoidalarga muvofiq olib tashlashingiz mumkin, ammo yana bir nechta nuanslar bilan.
• Birinchidan, daraxt olib tashlanishi kerak bo'lgan tugunni qidiradi. Agar bunday tugun bo'lmasa, hech narsa qilinmaydi, lekin agar u joylashgan bo'lsa, hamma narsa ancha qiziqroq.

Siz olib tashlangan tugunning o'ng pastki daraxtidan o'tishingiz va undagi eng kichik qiymatga ega tugunni topishingiz kerak — keling, uni min deb ataymiz. Shundan so'ng, olib tashlanadigan tugunni min tuguniga almashtirish kerak va daraxtning tuzilishi tiklanadi.

• Siz olib tashlangan tugunning o'ng pastki daraxtidan o'tishingiz va undagi eng kichik qiymatga ega tugunni topishingiz kerak — keling, uni min deb ataymiz. Shundan so'ng, olib tashlanadigan tugunni min tuguniga almashtirish kerak va daraxtning tuzilishi tiklanadi.

Agar olib tashlangan tugunning o'ng pastki daraxti bo'lmasa, min o'rniga uning chap avlodi tugun o'rniga almashtiriladi. Agar chap avlod ham bo'lmasa, unda olib tashlanadigan tugun — bu varaq, ya'ni uning avlodlari printsipial jihatdan yo'q. Keyin uni oddiygina olib tashlash mumkin va uning o'rniga hech narsa almashtirilmaydi.

• Agar olib tashlangan tugunning o'ng pastki daraxti bo'lmasa, min o'rniga uning chap avlodi tugun o'rniga almashtiriladi. Agar chap avlod ham bo'lmasa, unda olib tashlanadigan tugun — bu varaq, ya'ni uning avlodlari printsipial jihatdan yo'q. Keyin uni oddiygina olib tashlash mumkin va uning o'rniga hech narsa almashtirilmaydi.

Olib tashlangandan so'ng, novdalar orasidagi juda katta farqni oldini olish uchun yana yangi balandlik qiymatlarini qayta hisoblash va muvozanatni saqlash kerak.

• Olib tashlangandan so'ng, novdalar orasidagi juda katta farqni oldini olish uchun yana yangi balandlik qiymatlarini qayta hisoblash va muvozanatni saqlash kerak.

AVL daraxtini qanday qurish kerak

• Daraxtlarni amalga oshirish odatda oddiy tuzilishga qaraganda ancha murakkab. Ammo AVL daraxtlarini yaratish uchun deyarli har qanday zamonaviy dasturlash tillarida imkoniyatlar mavjud: Java, C/C++, Python va boshqalar.