Ikkilik (binar) daraxt

Ikkilik (binar) daraxt
Binar daraxtlar ma’lumotlar tuzilmalari ichida eng ko’p talab qilinadigan tuzilmalardjan biri hisoblanadi, butuzilmako’plabasosan hisoblash masalalariva turlixil qidiruv tizimlarida keng qo’llaniladi. Ushbumavzudabinardaraxtlarning asosiy xarakteristikasi va binar daraxt tuzilmalari ustida bajariladigan turli xil
amallarni o’rganamiz.
Odatdagidek, nazariy ma’lumotlardan tashqari: binar daraxtlar klassifikatsiyasi va binar daraxtlarustida amallarbajarishning standartusullarini qarab chiqamiz. Mavzuda binar daraxtlar ustida qo’llaniladigan algoritmlarning
Si va Python tillaridagitadbiqini o’rganib chiqamiz.


Binar daraxtlar klassifikatsiyasi
^{Binar daraxtlarning turlarini o’rganishdan oldin qidiruv algoritmlarining}
klassifikatsiyasi bilan tanishamiz.
Chiziqli qidiruvda qidirilayotgan element ro’yxatning barcha elementlari bilan qadamma-qadam solishtirib chiqiladi. Bunday qidirish tezligi ro’yxatning o’lchami (uzunligi) bilan bog’liq: ro’yxat qanchauzun bo’lsa, tezlikshunchakam bo’ladi, ya’ni tezlik ro’yxat uzunligi bilan teskari proportsional. Bunday
qidiruvdatezlikni oshirish uchun ro’yxatni oldin saralab olish kerakbo’ladi.
Saralangan ro’yxatlar uchun bundan samaraliroq algoritmlar mavjud. Saralangan ro’yxatning o’rtasida joylashgan element bilan qidirilayotgan elementni solishtirish zarurbo’ladi. Agaro’rta element qidirilayotgan elementdan kattabo’lsa, demak, qidirilayotgan element ro’yxatning chap yarmida joylashgan bo’ladi. Aks holda o’ng yarmida. Keyin ajratib olingan yarmidagi elementlar qidirilayotgan elementgasolishtirish amali boshlanadi. Bunda ham tanlabolingan yarim ro’yxatning o’rta elementi solishtirladi va zarur bo’lgan yarim ro’yxat ajratiladi. Bunday qidiruv usuli ikkilik qidiruv deb ataladi. Bu qidiruv chiziqli qidiruvga nisbatan tezroq bajariladi. Ro’yxat n ta elementdan tashkil topgan
bo’lsa, uni teng ikkiga bo’lib olish kerak, bu 2 asosga ko’ra n ning logarifmiga
^{teng bo’ladi. Ikkilik qidiruv ikki asosga ko’ra O(log) darajali algoritm}
hisoblanadi.
Ammo an’anaviy bog’langan ro’yxatlar ikkilik qidiruv uchun qulay emas, shuninguchun ham 1-rasmda ko’rsatilganmisoldagikabi ikkilik (binar) daraxtni
qo’llash tavsiya etiladi.

1-rasm. Binar daraxtgamisol
Umumiy holda daraxtdagi har bir tugun cheklanmagan sondagi o’g’il tugunlarga egabo’lishimumkin. Daraxtlarning qolganturlaridan binardaraxtning farqli tomoni, binar daraxtning har bir tugunida ikkitadan ko’p bo’lmagan o’g’il tugunlar bo’ladi. Oddiybinardaraxt- buharbiriba’zi qiymatlarni hamdachapva o’ng qismdaraxtlarga ko’rsatkichlarni saqlovchi tugunlardan tashkil topgan tuzilma hisoblanadi. Bu qismdaraxtlarning bitta yoki ikkala ko’rsatkichlari ham NULL qiymatiga ega bo’lishi mumkin. Ikkilik daraxtlar ham bog’langan
ro’yxatlar kabirekursiv tuzilmahisoblanadi.

160