Fizika-matematika fakulteti

3-§. Qizil-qora BSTlarning xususiyatlari.

Qizil-qora BSTlarning xususiyatlarini o'rganish 2-3 daraxt bilan mosligini tekshirish va keyin 2-3 daraxtning tahlilini qo'llashdir. Natijada, qizil-qora BST-larda barcha ramziy jadval operatsiyalari daraxtning o'lchamida logarifmik bo'lishi kafolatlangan (qatorni qidirish bundan mustasno, bu qo'shimcha ravishda qaytarilgan kalitlar soniga mutanosib ravishda sarflanadi).

Tahlil. Birinchidan, qizil-qora BSTlar mutanosib emasligiga qaramay, kalitlarning qanday tartibda joylashtirilganidan qat'i nazar, deyarli har doim shunday bo'lishini aniqladik. Bu haqiqat darhol 1-1 dan 2-3 daraxtga va 2-3 daraxtning aniqlangan xususiyatlariga (mukammal balans) bog'liqdir.

• 
  Qizil-qora BSTning tugunlari bilan balandligi 2lgNdan oshmaydi.
  

Eng yomon holat, 2-3 ta daraxt bu barcha 2-tugunlardan iborat, bundan tashqari, chap yo'l 3-tugunlardan iborat bo’lishidir. Ildizdan chap aloqalarni olib boruvchi yo'l faqat 2 tugunni qamrab oladigan ~ lgN uzunlikdagi yo'llardan ikki baravar uzundir. O'rtacha uzunligi 2lgN ga teng bo'lgan qizil-qora BSTlarning paydo bo'lishiga olib keladigan asosiy ketma-ketliklarni yaratish mumkin, ammo bu oson emas. Ushbu yuqori chegara konservativdir: odatiy ilovalarda topilgan tasodifiy qo'shib qo'yish va kiritish tartibini o'z ichiga olgan tajribalar har bir qidirish qizil-qora BST tugunlarida o'rtacha 1,00 lg N - 5 ni ishlatadi degan farazni qo'llab-quvvatlaydi.

26-rasm. Odatda tasodifiy tugmachalardan qurilgan odatiy qizil-qora BST

(nol ishoratlar bekor qilingan).

• 
  Qizil qora BSTda tugunlari bo'lgan ildizdan tugungacha bo'lgan yo'lning o'rtacha uzunligi ~ 1,00 lg N ga teng.
  

Qizil-qora BST-larda get () usuli tugun rangini tekshirmaydi, shuning uchun muvozanat mexanizmi qo'shimcha xarajatlarni qo'shmaydi, qidirish oddiy BSTlarga qaraganda tezroq, chunki daraxt muvozanatli. Har bir kalit bir marta kiritiladi, lekin ko'pgina qidiruv jarayonlarida qatnashishi mumkin, shuning uchun biz qidiruv vaqtlarini nisbatan kam xarajat bilan (ikkilik qidirishdan farqli o'laroq, qo'shimchalar logarifmik bo'lishi kafolatlanadi) maqbul darajaga yaqinlashamiz (chunki daraxtlar deyarli muvozanatlashgan va qidirish paytida muvozanat uchun hech qanday ish qilinmaydi). Qidiruvning ichki halqasi - bu ikkilangan qidirishning ichki pastadir kabi taqqoslash va undan keyin havolani yangilash. Ushbu amalga oshirish, qidirish va kiritish uchun logarifmik kafolatlar bilan birinchi bo'lib ko'rdik, shuning uchun undan foydalanish turli xil dasturlarda, shu jumladan kutubxonada ham oqlanadi.