Fizika-matematika fakulteti

Bog'lanishdan keyin ota-onadagi havolani tiklash. Chapdami yoki o'ngdami, har bir aylanish bizni bog'lab qo'yadi. Otada (yoki daraxtning ildizida) tegishli havolani tiklash uchun doimo rotateRight () yoki rotateLeft () orqali qaytarilgan havoladan foydalanamiz. Bu o'ng yoki chap yo'nalish bo'lishi mumkin, lekin uni har doim ota-onada havolani tiklash uchun ishlatamiz. Ushbu yo'nalish qizil yoki qora rangga ega bo'lishi mumkin - rotateLeft () va rotateRight () x.color-ni h.color-ga belgilab, rangini saqlab qoladi. Bu daraxtning ichida ketma-ket ikkita qizil havolani paydo bo'lishiga imkon berishi mumkin, ammo bizning algoritmlarimiz bu holat yuzaga kelganda tuzatish uchun aylanishlardan ham foydalanadi. Masalan,

h = rotateLeft (h);

kod h tugunning o'ng tomonidagi chap tomonga buriladigan qizil ulanishni aylantiradi, h ni hosil bo'lgan pastki daraxtning ildiziga (h aylanishdan oldin h belgisi bilan ko'rsatilgan barcha tugunlarni o'z ichiga oladi, lekin boshqa ildiz ). Ushbu turdagi kodni yozish qulayligi, BST usullarining rekursiv tatbiqlaridan foydalanishimizning asosiy sababi hisoblanadi, chunki ko'rib turganingizdek aylanishlarni oddiy qo'shishga oson qo'shimcha qiladi. Biz 2-3 ta daraxt va qizil-qora BSTlar orasidagi 1-1 o'zaro moslikni saqlab qolish uchun aylanishlardan foydalanishimiz mumkin, chunki yangi kalitlar kiritilgan, ular qizil-qora BSTlarning ikkita aniqlovchi xususiyatlarini saqlab qolishadi: tartib va mukammal qora balans. Ya'ni, tartibni yoki mukammal qora balansni yo'qotish haqida tashvishlanmasdan, qizil-qora BST-da aylanishlardan foydalanishimiz mumkin. Keyinchalik, BTs-ning boshqa ikkita aniqlovchi xususiyatlarini saqlab qolish uchun aylanishlardan qanday foydalanishni ko'rib chiqamiz (biron bir yo'lda ketma-ket qizil havolalar va o'ngga suyanadigan qizil havolalar yo'q).