4. Cho'qqini o'chirish algoritmi
Oddiylik uchun biz rekursiv o'chirish algoritmini tasvirlaymiz. Agar cho'qqi barg bo'lsa, uni o'chiring va ota-onadan ildizga qadar barcha ajdodlarining muvozanatini chaqiring. Aks holda, eng yaqin yaqin guruh eng yuqori balandlikdagi pastki daraxtning tepasida (o'ng yoki chap) bo'ladi deb taxmin qilamiz va uni olib tashlanishiga olib kelgan holda olib tashlangan tepaning joyiga o'tkazamiz.
Faraz qilaylik, bu algoritm muvozanatni saqlaydi. Buning uchun, bu yog'ochdan vertex fraktsiyasini olib tashlash va yog'och balandligi balanslash kamaytirish so'ng, kamaytirish ko'pi 1. Ishtirok etish uchun asos bo'ladi, deb taxmin qilish mumkin: Bir barg uchun, aniq to'g'ri. Baholash bosqichi: Yoki ildizlardagi muvozanat holati (oʻchirilgandan keyin ildiz oʻsishi mumkin) buzilmagan boʻlsa, keyin berilgan daraxtning balandligi oʻzgarmagan yoki pastki daraxtlardan qatʼiy kamroq pasaygan boʻlsa => balandligi bor. balanslashdan oldin o'zgartirilmagan => shundan keyin u 1 dan ko'p bo'lmagan kamayadi.
Shubhasiz, jinoyat ishini qo'zg'atish choralarini ko'rish natijasida 3 martadan ko'p bo'lmagan, chunki 2-chaqiruv bilan o'chirilgan cho'qqi pastki daraxtlardan biriga ega emas. Ammo har safar eng yaqin cho'qqilarni qidirish O(N) operatsiyalarini talab qiladi, shuning uchun aniq optimallashtirish: eng yaqin cho'qqilarni qidirish pastki daraxtning chetida amalga oshiriladi. harakatlar soni O(log(N)).
5. Olib tashlashda balanslarni tartibga solish
Yuqorida aytib o'tilganidek, agar o'chirilishi kerak bo'lgan cho'qqi barg bo'lsa, u o'tadi va teskari daraxt o'chirilgan bargning ota-onasidan keladi. Agar u barg bo'lmasa, u "almashtirish" ga ega va qaytish yo'li "almashtirish" ota-onasidan keladi. Element chiqarilgandan so'ng darhol muvozanatli tugun sifatida "almashtirish" olinadi.
Teskari aylanma yo'lda: agar ota-onaga o'tishda ular chap tomonga o'tishgan bo'lsa, balans 1 ga teng, lekin agar ular to'g'ri yo'ldan borgan bo'lsa, u 1 ga teng edi.
Bu balansdan foydalanganda -1 yoki 1 ga bog'liq bo'lmaganda sodir bo'ladi (elementni kiritish bilan farqga e'tibor bering!): Balansning bunday o'zgarishi taqdirda pastki daraxtlarning delta balandligi o'zgarmagan deb hisoblanadi. Aylanishlar kiritish paytida bo'lgani kabi bir xil qoidalarga amal qiladi
|
