Fizika-matematika fakulteti

Muvozanatlashgan binar daraxt.
Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari va tugunlari soni teng bo’lsa, u holda bunday binar daraxt ideal muvozanatlashgan daraxt deyiladi.

1-rasm. Ideal muvozanatlashgan daraxt.

Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmasa, u holda bunday binar daraxt muvozanatlashgan daraxt deyiladi. Masalan,

2-rasm. Muvozanatlashgan daraxt.

1-§. Muvozanatlashgan daraxtlarni qidirish. 2-3 qidiruv daraxti.

Biz ikki tomonlama qidirish daraxti turini taqdim etamiz, bu yerda ularni qurish uchun kalitlarning ketma-ketligidan qat'i nazar, xarajatlar logarifmik bo'lishi kafolatlanadi. Ideal holda, biz ikki tomonlama qidirish daraxtlarni mukammal muvozanatlashni bajaramiz. N tugunli daraxtda biz ikkitadan qidirishda bo'lgani kabi barcha qidiruvlarni ~ lg N taqqoslashda bajarilishini kafolatlashimiz uchun uning balandligi ~ lg N bo'lishi ta’minlanadi. Afsuski, dinamik qo'shimchalar uchun mukammal muvozanatni saqlash juda qiyin. Ushbu bo'limda biz buyurtma qilingan barcha operatsiyalar (diapazonli qidiruvdan tashqari) uchun kafolatlangan logarifmik ishlashni ta'minlash uchun mukammal muvozanat talabini biroz yengillashtiradigan ma'lumotlar tuzilishini ko'rib chiqamiz.

Qidiruv daraxtlaridagi muvozanatni ta'minlashimiz kerak bo'lgan moslashuvchanlikni olishning asosiy bosqichi, daraxtlarimizdagi tugunlarga bir nechta tugmachalarni bosishga imkon berishdir. Xususan, standart BST-dagi tugunlarni 2-tugun deb atash (ular ikkita ulanish va bitta kalitga ega), endi biz uchta ulanish va ikkita tugmachani o'z ichiga olgan 3-tugunlarga ruxsat beramiz. 2-tugun ham, 3-tugun ham har bir oraliq uchun bitta tugmachaga ega bo'lib, uning tugmachalari qo'shib qo'yilgan.

3-rasm. 2-3 qidiruv daraxtining tuzilishi.

To'liq muvozanatlangan 2-3 qidirish daraxti - bu null ishoratlar ildizdan bir xil masofada joylashgan daraxtdir. Qisqacha aytganda, biz 2-3 daraxti atamasini mukammal muvozanatlangan 2-3 qidirish daraxtiga ishora qilamiz (bu so'z boshqa kontekstlarda umumiyroq tuzilishni anglatadi).

4-rasm. H uchun muvaffaqiyatli qidiruv. B uchun muvaffaqiyatsiz qiduruv