Fizika-matematika fakulteti

Ekvivalent ta'rif. Davom etishning yana bir usuli - qizil-qora BSTlarni qizil va qora yo'nalishlarga ega va quyidagi uchta shartni qanotlantiradigan BST deb belgilash:

■ Qizil havolalar chapga egilgan.

■ Hech qanday tugun unga ikkita qizil ulanishga ega emas.

■ Daraxt mukammal qora balansga ega: ildizdan nullgacha bo'lgan har bir yo'l bir xil miqdordagi qora havolalarga ega.

Shu tarzda aniqlangan qizil-qora BSTlar va 2-3 daraxt o'rtasida 1-1 muvofiqlik mavjud.

1-1 muvofiqlik. Agar qizil ulanishlarni gorizontal ravishda qizil qora BSTga chizsak: barcha nol ishoratlar ildizdan bir xil masofada joylashgan bo’ladi, agar qizil ulanishlar bilan bog'langan tugunlarni birlashtirsak, natija 2-3 daraxt bo'ladi.

14-rasm. Gorizontal qizil yo'nalishlarga ega bo'lgan qizil-qora daraxt - bu 2-3 daraxt.

Aksincha, agar 2-3 daraxtda 3-tugunni chap tomonga suyanadigan qizil aloqa bilan bog'langan ikkita 2-tugun sifatida chizsak, unda hech qanday tugun unga ikkita qizil ulanishga ega emas va daraxt mukammal qora balansga ega, chunki qora havolalar ta'rifi bo'yicha mukammal muvozanatlangan 2-3 daraxt bog'lanishiga to'g'ri keladi. Qaysi usulni tanlashimizdan qat'i nazar, qizil-qora BSTlar ham BSTlar, ham 2-3 daraxtlardir. Shunday qilib, agar 1-1muvofiqlikni saqlab qolish orqali 2-3 daraxtni kiritish algoritmini amalga oshira olsak, unda har ikkisining eng optimalini olamiz: standart BSTlardan oddiy va samarali qidirish usuli va 2-3 daraxtdan qo'shishni muvozanatlash usuli.

15-rasm. Qizil-qora BST va 2-3 daraxt orasidagi 1-1 muvofiqlik.