15-mavzu: Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari. Avl daraxti

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.

Birinchidan, ishlab chiquvchi bitta tugunning tuzilishini tavsiflaydi. Bu bir nechta o'zgaruvchini o'z ichiga oladigan ob'ekt bo'lishi mumkin: C++ da buning uchun struct (struct) ma'lumotlar turi mavjud, Python-da tugun odatda o'z sinfini yaratadi va hokazo.

• Birinchidan, ishlab chiquvchi bitta tugunning tuzilishini tavsiflaydi. Bu bir nechta o'zgaruvchini o'z ichiga oladigan ob'ekt bo'lishi mumkin: C++ da buning uchun struct (struct) ma'lumotlar turi mavjud, Python-da tugun odatda o'z sinfini yaratadi va hokazo.
• Dasturiy jihatdan tavsiflangan tugun quyidagilarni o'z ichiga oladi:

Keyin balandlikni, pastki daraxtlar orasidagi farqni va boshqalarni aniqlash uchun alohida funktsiyalar belgilanadi.

• Keyin balandlikni, pastki daraxtlar orasidagi farqni va boshqalarni aniqlash uchun alohida funktsiyalar belgilanadi.
• ba'zi ma'lumotlar, ularning qiymati, yuqorida aytib o'tilganidek, elementning joylashgan joyiga bog'liq — ota-onaning chap yoki o'ng tomonida;
• chap va o'ng avlodlarga havolalar;
• ushbu tugundan boshlanadigan pastki daraxtning balandligi yoki chap va o'ng pastki daraxtlar orasidagi balandlik farqi.