Fizika-matematika fakulteti

Daraxtga ikkita tugmacha bilan joylashtirish (3-tugun ichida). Bu holat uchta kichik qiamga qisqaradi: yangi kalit ikkala daraxt ichidagi kalitlardan ham kichik yoki ikkalasidan ham kattaroqdir. Ishlarning har biri unga ikkita qizil ulanishli tugunni kiritadi; bizning maqsadimiz ushbu shartni tuzatishdir.

■ Uch holatning eng sodda tomoni shundaki, yangi kalit daraxtdagi kalitdan kattaroq bo'lsa va shuning uchun 3 tugunning o'ng tomoniga bog'langan bo'lsa, qizil ulanishlar bilan bog'langan holda ildizida o'rta kalit bilan muvozanatli daraxt hosil bo'ladi. Agar ushbu ikkita bog'lanish ranglarini qizildan qora rangga o'zgartirsak, unda bizda 2 ta uchta tugunli muvozanatli balandlik daraxti bor, bizning daraxtlarimizga 1-1 ta mos kelishini ta'minlashimiz kerak. Qolgan ikkita holat oxir-oqibat bu holatga kamaydi.

 ■ Agar yangi kalit daraxtdagi ikkita kalitdan kichik bo'lsa va chap bog'lanishda davom etadigan bo'lsa, unda chap tomonga egilgan ikkita qizil ulanishni oldingi holatgacha kamaytirishimiz mumkin (ildizning o'rtasidagi tugma). Yuqoridagi havolani o'ng tomonga burab, boshqalarga ikkita qizil havolalar orqali ulanadi.

■ Agar yangi kalit daraxtdagi ikkita kalit o'rtasida ketsa, biz yana ketma-ket ikkita qizil ulanishga egamiz, o'ngga chapga egilib, oldingi holatga qisqartirishimiz mumkin (ketma-ket ikkita qizil havola, chap havolani chap tomonga burab). Xulosa qilib, nol, bitta yoki ikkita aylantirish orqali kerakli natijaga erishamiz, so'ngra ildizning ikkita farzandining ranglarini siljitamiz. 2-3 daraxtda bo'lgani kabi, bu o'zgarishlarni tushunganimizga ishonch hosil qilish mumkin, chunki ular qizil-qora daraxt dinamikasining kalitidir.

20rasm. Bitta 3 tugunga joylashtirish (uchta holat)