Algoritmdan nazorat savollariga javoblar Algoritm nima

Binar qidiruv daraxtida k-tartibli qiymatni topish

K-tartibli qiymat

• 
  Berilgan sonlar to’plamini qiymatlari o’sish tartibida joylashtirgandan k-o’rinda turadigan sonni topish.
  
• 
  Buning uchun har bir uzel(uch) uchun qo’shimcha yana bir qiymat – uning qism daraxtida jami qancha uch borligini saqlaymiz(size maydon).
  

int k_th(int k) {

if ((*root).size < k)

return -1000000001;

node *cur = root;

while (1) {

int size_left = 0;

if ((*cur).left != NULL)

size_left = (*(*cur).left).size;

if (size_left >= k)

cur = (*cur).left;

else if (size_left==k-1)

return (*cur).data;

else {

k -= size_left + 1;

cur = (*cur).right;

}

}

}

21. 
    Binar qidiruv daraxtida izlash
    

Javob: Binar daraxt bo‟yicha qidiruv funksiyasi
Mazkur funksiyaning vazifasi shundan iboratki, u berilgan kalit bo‟yicha
daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi
daraxt tuzilishiga bog‟liq bo‟ladi. Haqiqatdan, agar elementlar daraxtga kalit
qiymatlari o‟sish (kamayish) tartibida kelib tushgan bo‟lsa, u holda daraxt 4.7-rasmdagidek bir tomonga yo‟nalgan ro‟yhat hosil qiladi (chiqish darajasi bir bo‟ladi, ya‟ni yagona shoxga ega), masalan:

4.7-rasm. Bir tomonlama yo‟naltirilgan binar daraxt tuzilishi
Bu holda daraxtda qidiruv vaqti, bir tomonlama yo‟naltirilgan ro‟yhatdagi
kabi bo‟lib, o‟rtacha qarab chiqishlar soni N/2 bo‟ladi. Agar daraxt
muvozanatlangan bo‟lsa, u holda qidiruv eng samarali natija beradi. Bu holda
qidiruv log2 N dan ko‟p bo‟lmagan elementlarni ko‟rib chiqadi.
Qidiruv funksiyasini ko‟rib chiqamiz. search fuksiyasi daraxtdan key kalitga
mos elementning adresini aniqlaydi.