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

balanslash funktsiyasini chaqiring. Qo'shish rekursiv bo'lgani uchun, muvozanatlash kiritish funktsiyasining oxirgi ochiq nusxasidan boshlab va birinchisiga qadar amalga oshiriladi.

• balanslash funktsiyasini chaqiring. Qo'shish rekursiv bo'lgani uchun, muvozanatlash kiritish funktsiyasining oxirgi ochiq nusxasidan boshlab va birinchisiga qadar amalga oshiriladi.

Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:

• Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:
• ikkilik qidiruv daraxtining tuzilishi mantig'iga ko'ra, minimal tugun maksimal bitta avlodga ega bo'lishi mumkin — o'ngda. Shuning uchun minimal tugunni "olib tashlash" funktsiyasi uning o'ng avlodini qaytaradi-uni almashtirishda foydali bo'ladi;

minimal tugun qaytarib bo'lmaydigan tarzda o'chirilmaydi, lekin o'chiriladigan joyga almashtiriladi — yana havolalar almashtiriladi;

• minimal tugun qaytarib bo'lmaydigan tarzda o'chirilmaydi, lekin o'chiriladigan joyga almashtiriladi — yana havolalar almashtiriladi;
• chapda, minimal tugunga olib tashlangan tugunning chap avlodi, o'ngda — minimal ajratilgandan keyin o'ng avloddan qolgan narsa qo'shiladi;
• balanslash mavjud.

Foydalanilgan internet manzillar:

• 1. https://blog.skillfactory.ru/glossary/avl-derevo/
• 2. https://habr.com/ru/post/150732/
• 3. https://ru.wikipedia.org/
• 4. http://repo.ssau.ru/bitstream/Uchebnye-posobiya/Metody-programmirovaniya-Elektronnyi-resurs-ucheb-posobie-68534/1/.pdf

• E’tiboringiz uchun raxmat!