Fizika-matematika fakulteti

Qizil bog'dan daraxtga o'tish. 2-3 daraxtni kiritish algoritmi 3 tugunni ajratishga chaqiradi, o'rta tugmachani ota-onasiga joylashtirilib, 2 tugun yoki ildizga duch kelguncha davom etadi. Ko'rib chiqqan har bir holatda, ushbu maqsadni aniq bajaramiz: kerakli aylanishlarni amalga oshirgandan so'ng, o'rta tugunni qizilga aylantiradigan ranglarni siljitamiz. Ushbu tugunning ota-onasi nuqtai nazaridan, bu qizilga ulanishni, xuddi qizil tugma yangi tugunni biriktirishdan kelib chiqqanidek amalga oshirish mumkin: qizil tugmani o'rta tugunga o'tkazamiz. Keyingi sahifadagi diagrammada keltirilgan uchta holat, 2-3 daraxtni qo'shib qo'yishda asosiy operatsiyani bajarish uchun qizil-qora daraxtda zarur bo'lgan amallarni aniq oladi: 3-tugunga kiritish, vaqtincha 4-tugunni yaratish, bo'linish. U ota-onasigacha o'rta tugmachaga qizil havolani yuboradi. Xuddi shu jarayonni davom ettirib, biz 2 tugunga yoki ildizga yetib borguncha daraxtga qizil ulanishni o'tkazamiz.

23-rasm. Qizil qora BST-ga qizil ulanish.

Xulosa qilib aytganda, uchta oddiy operatsiyadan oqilona foydalanish orqali chap daraxtni aylantirish, o'ngga burish va rangli siljitish orqali 2-3 daraxt va qizil-qora BST o'rtasidagi 1-1 yozishmalarimizni saqlab qolishimiz mumkin. Kiritishni har bir tugunga birin-ketin bajarib, daraxtni kiritish joyidan yuqoriga ko'targanimizdan so'ng bajaramiz:

■ Agar o'ng bola qizil bo'lsa va chap bola qora bo'lsa, chapga buriling.

■ Agar chap va chap bola ikkalasi ham qizil bo'lsa, o'ng tomonga buriling.

■ Agar ikkala bola ham qizil bo'lsa, ranglarini o'zgartiring. Ushbu ketma-ketlik, yuqorida tavsiflangan holatlarning har birini o'z ichiga olganligini tekshirish uchun vaqt sarflash kerak. Birinchi operatsiya ota-ona 2 tugunli bo'lganda, 3-tugunni chapga egish uchun zarur bo'lgan aylanishni va pastki aloqani chapga egish uchun zarur bo'lgan aylanishni ham bajaradi, qachonki yangi qizil havola 3-tugunli o'rtadagi havola bo'lsa.