Ikkilik qidiruv daraxti

Ikkilik daraxtlarning samaradorligi 
Ko'rib turganimizdek, ko'plab daraxt operatsiyalari ma'lum bir tugunni topish 
uchun darajadan pastga tushishni o'z ichiga oladi. Ushbu o'tish qancha davom 
etadi? To'liq daraxtda pastki darajadagi tugunlarning taxminan yarmi mavjud. 
(Aniqroq, agar daraxt to'lgan bo'lsa, daraxtning qolgan qismiga qaraganda pastki 
sathda bitta tugun bor.) Shunday qilib, qidirish, qo'shish yoki o'chirish 
operatsiyalarining taxminan yarmi pastki sathda tugunni topishni talab qiladi. 
Amaliyotlar soni daraxtning balandligiga bog'liq. Oddiy daraxt operatsiyalari 
uchun bajarilish vaqti N.ning 2-asosli logarifmiga mutanosibdir O-sintaksisida 
bunday operatsiyalarning bajarilish vaqti O (log
2
N) bilan belgilanadi. 
Keling, daraxtni hozirgacha muhokama qilingan boshqa ma'lumotlar 
tuzilmalari bilan taqqoslaylik. 1.000.000 elementlarning tartibsiz qatori yoki 
bog'langan ro'yxatida kerakli elementni topish o'rtacha 500000 taqqoslashni talab 
qiladi. 
Ammo 1 000 000 tugunli daraxt uchun 20 (yoki undan kam) taqqoslash etarli. 

---

Elementlar buyurtma qilingan qatorda tezda topiladi, ammo qo'shish uchun 
o'rtacha 500000 ta harakat talab etiladi. 1.000.000 tugunli daraxtga element kiritish 
20 yoki undan kam taqqoslashni, shuningdek tugunni bog'lash uchun oz vaqtni 
talab qiladi. 
Xuddi shunday, elementni 1 000 000 elementli massivdan olib tashlash uchun 
o'rtacha 500 000 ta element harakatlanishi kerak, 1 000 000 tugunli daraxtdan 
elementni olib tashlash uchun 20 yoki undan kam taqqoslash kerak bo'ladi, 
shuningdek, voris topish uchun yana bir necha taqqoslashlar va elementni ajratish 
va vorisni biriktirish uchun oz vaqt. 
Shunday qilib, daraxt barcha asosiy ma'lumotlarni saqlash operatsiyalarini 
bajarishda yuqori samaradorlikni ta'minlaydi. Bypass boshqa operatsiyalar kabi tez 
emas. Biroq, odatdagi katta ma'lumotlar bazasi uchun sudralib yurish odatiy 
operatsiya emas. Daraxtlarni kesib o'tish ko'pincha algebraik va kamdan-kam uzun 
bo'lgan boshqa iboralarni tahlil qilishda qo'llaniladi. 
Ikkilik qidiruv daraxtining kamchiligi shundaki, kirish ma'lumotlari 
tartiblangan ketma-ketlikda bo'ladi, keyin qo'shish va qidirish operatsiyalari O (n) 
uzoq vaqt davomida amalga oshiriladi, chunki bu holda muvozanatsiz daraxt 
olinadi, ya'ni chapga yoki orqaga qarab daraxt.