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

AVL daraxtini qanday muvozanatlash mumkin

• Elementlarni muvozanatlash, qo'shish va olib tashlash — bu alohida yozilgan funktsiyalar. Odatda, birinchi navbatda, ishlab chiquvchi odatdagi burilishni amalga oshiradigan kodni amalga oshiradi, so'ngra bu funktsiya muvozanat uchun mas'ul bo'lgan boshqa, kattaroq kodda ishlatiladi.

Balanslash funktsiyasi kodi shartlarni tekshirish va agar tekshiruv nomutanosiblikni aniqlasa, burilishlarni bajarish uchun kamayadi. Birinchidan, bitta oddiy burilish amalga oshiriladi, keyin bu yordam bermasa, ikkinchisi boshqa avlod uchun va teskari yo'nalishda. Shunday qilib, katta burilish amalga oshiriladi.

• Balanslash funktsiyasi kodi shartlarni tekshirish va agar tekshiruv nomutanosiblikni aniqlasa, burilishlarni bajarish uchun kamayadi. Birinchidan, bitta oddiy burilish amalga oshiriladi, keyin bu yordam bermasa, ikkinchisi boshqa avlod uchun va teskari yo'nalishda. Shunday qilib, katta burilish amalga oshiriladi.

Dastur yaratilishida almashinishlar daraxt elementlarini bir-biriga bog'laydigan havolalarni qayta tartibga solish uchun kamayadi. Shundan so'ng, balandliklar orasidagi farqni ko'rsatadigan raqamli qiymatlar qayta hisoblab chiqiladi.

• Dastur yaratilishida almashinishlar daraxt elementlarini bir-biriga bog'laydigan havolalarni qayta tartibga solish uchun kamayadi. Shundan so'ng, balandliklar orasidagi farqni ko'rsatadigan raqamli qiymatlar qayta hisoblab chiqiladi.

Qo'shish va o'chirishni amalga oshirish

• Kiritish. Elementni kiritish funktsiyasi odatda rekursivdir, ya'ni o'zini o'zi chaqiradi. Uni juda oqlangan tarzda amalga oshirish mumkin:
• boshlang'ich tugundagi funktsiyani chaqiring;

agar kiritilishi kerak bo'lgan qiymat biz joylashgan tugun qiymatidan kam bo'lsa, chapga o'ting-chap avlod uchun bir xil funktsiyani chaqiring;

• agar kiritilishi kerak bo'lgan qiymat biz joylashgan tugun qiymatidan kam bo'lsa, chapga o'ting-chap avlod uchun bir xil funktsiyani chaqiring;
• agar qiymat biz hozir bo'lgan joyga teng yoki undan katta bo'lsa, o'ng tomonga o'ting — biz o'ng avlod uchun funktsiyani chaqiramiz;
• agar biz hali tugun bo'lmagan joyga etib borsak, u erda tugun yarating va u erda yangi qiymat qo'ying;