Fizika-matematika fakulteti

Minimalni o'chirish. O'chirish uchun biz 2-3 daraxtdan minimalni o'chirish operatsiyasini ko'rib chiqamiz. Asosiy g'oya kuzatishlarga asoslanib, kalitni daraxtning pastki qismidagi 3-tugundan osongina o'chirishimiz mumkin, ammo 2- tugundan emas. Kalitni 2-tugundan o'chirish tugmasiz tugunni qoldiradi; tabiiy narsa tugunni nol ulanish bilan almashtirishdir, ammo bu operatsiya mukammal muvozanat holatini buzadi. Shunday qilib, quyidagi yondashuvni qabul qilamiz: 2 tugunga tushmaslikni ta'minlash uchun, joriy tugun 2-tugun emasligi haqidagi invariantni saqlab qolish uchun daraxtni pastga tushirishda tegishli o'zgarishlar amalga oshiriladi. Birinchidan, ildizda ikkita imkoniyat bor: agar ildiz 2 tugunli bo'lsa va ikkala bola ham 2-tugun bo'lsa, biz uchta tugunni 4-tugunga aylantirishimiz mumkin, ildizning chap bolasi 2 tugun emasligiga ishonch hosil qilish uchun.

25-rasm. Minimalni o'chirish uchun transformatsiyalar.

Keyin, daraxtdan pastga tushayotganda, quyidagi holatlardan biri ushlab turilishi kerak:

■ Agar joriy tugunning chap bolasi 2 tugun bo'lmasa, unda hech qanday ish bo'lmaydi.

■ Agar chap bola 2 tugunli bo'lsa va uning qarindoshi 2 tugunli bo'lmasa, u holda tugmachani ukadan chap bolaga o'tkazing.

■ Agar chap bola va uning yaqin qarindoshlari 2 tugunli bo'lsa, ularni ota-onaning eng kichik tugmachasi bilan 4 tugunli qilib, ota-onani 3-tugundan 2-tugunga yoki 4-tugunga o'zgartiriladi. Ushbu jarayondan so'ng chap ulanishlarni pastki qismga o'tkazganimizda, 3 tugunni yoki eng kichik kalit bilan 4 tugunni o'rab olamiz, shunda biz 3-tugunni 2-tugunga yoki 4-ga aylantirib, shunchaki uni olib tashlashimiz mumkin.

O’chirish. Minimallikni yo'q qilish uchun ta'riflangan qidirish yo'lidagi xuddi shunday o'zgarishlar, har qanday kalitni qidirish paytida mavjud tugun 2-tugun emasligiga ishonch hosil qilish uchun samarali bo'ladi. Agar qidirish kaliti pastki qismida bo'lsa, uni olib tashlash mumkin. Agar kalit pastki qismida bo'lmasa, unda biz BSTda bo'lgani kabi uni vorisi bilan almashtirish kerak. Keyin, hozirgi tugun 2-tugun emasligi sababli, ildiz 2-tugun bo'lmagan satrda minimal o'chirish muammosini kamaytiriladi va ushbu pastki qism uchun faqat tasvirlangan protseduradan foydalanishimiz mumkin. O'chirishdan so'ng daraxtni ko'tarish yo'lida qolgan 4-tugunni qidiruv yo'liga ajratamiz.