Binar qidiruv algoritmi. Binar qidiruv daraxti. Prioritetli navbat. Binar qidiruv algoritmi

L
R
M
1
2
3
4
5
6
7
8
9
10
11

O`rtadagi element 37 ga teng, 32<37 bo`lganligi uchun uni chap tomondan izlashni davom qildiramiz. L = 6, R = M =9, M = 7

4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11

O`rtadagi element 37 ga teng, 32<37 bo`lganligi uchun uni chap tomondan izlashni davom qildiramiz. L = 6, R = M =9, M = 7

4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11

O`rtadagi element 28 ga teng, 32≥28 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 7, R = 9, M = 8

O`rtadagi element 28 ga teng, 32≥28 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 7, R = 9, M = 8

4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11
4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11
4
7
10
14
18
25
28
32
37
41
46
L
R
M
1
2
3
4
5
6
7
8
9
10
11
O`rtadagi element 32 ga teng, 32≥28 bo`lganligi uchun uni o`ng tomondan izlashni davom qildiramiz. L = M = 8, R = 9.
R-L=1bo`lganida izlashni tugatamiz, izlanayotgan sonimiz L indeksda joylashgan massiv elementiga teng.
4
7
10
14
18
25
28
32
37
41
46
L
R
1
2
3
4
5
6
7
8
9
10
11

Binar qidiruv algoritmi funksiyasi.

int binsearch(int x, int n) {
int L = 1, R = n+1;
while (R-L > 1) {
int M = (L+R) / 2;
if (a[M] <= x)
L = M;
else
R = M;
}
if (a[L]==x)
return L;
return -1;
}

Binar qidiruv algoritmi funksiyasi2.

int binsearch(int x, int n) {
int L = 1, R = n+1;
while (R-L > 1) {
int M = (L+R) / 2;
if (a[M] < x)
L = M;
else
R = M;
}
if (a[R]==x)
return R;
return -1;
}

Binar qidiruv daraxti. Masalaning qo’yilishi

• Sonlar to’plamini saqlovchi va quyidagi amallarni bajara olish imkoniyati bo’lgan ma’lumot tuzilmasini yaratish lozim:
• son qo’shish
• sonni topish
• sonni o’chirish
• minimalni topish
• maksimalni topish
• qiymat bo’yicha k-sonni topish(k-tartibli statistika)

Binar daraxt

• Har bir uchi ikkidan ortiq bo’lmagan farzandga ega daraxt;
• Har bir uchning farzandlari tartibga ega, chap va o’ng varzandlar;
• Eng uchidagi uchi – daraxt ildizi deb nomlanib hecha qanday ajdodga ega emas;
• Uchning balandligi – ildizdan ungacha masofa;
• Daraxtning balandligi – uning uchlarining balandliklaridan eng kattasi.

Ikkilik qidiruv daraxti

• Bu ikkilik daraxti bo’lib har bir uchida son saqlanadi
• Agar qandaydir uchdagida son qiymati x ga teng bo’lsa u holda:
• Chapki qism daraxtdagi barcha sonlar qiymati x dan kichik
• O’ng qism daraxtdagi barcha sonlar qiymati x dan katta bo’ladi;

Binar qidiruv daraxti bir xil sonlar to’plamidan har xil hosil qilinishi mumkin

• 1,3,10,23,50 sonlaridan
• Balandlik O(n)

Balandlik log(n)

Daraxt uchi

• class node {
• public:
• int data;
• node *left;
• node *right;
• node(int x) {
• data = x;
• left = NULL;
• right = NULL;
• }
• };
• NULL qiymati uning mos farzandi yo’q ekenligini bildiradi

Daraxtda element izlash

• Agar qaralayotgan uchdagi y qiymat izlanayotgan x qiymatga teng bo’lsa izlanayotgan son topilgan hisoblanadi va qidiruv yakunlanadi
• Agar x > y bo’lsa u holda qidiruvni o’ng farzandidan davom ettiramiz
• Agar x < y bo’lsa u holda qidiruvni chap farzandidan davom ettitamiz

C++ da dasturi

• bool find(int x) {
• node *cur = root;
• while (cur != NULL) {
• if ((*cur).data==x)
• return true;
• if (x > (*cur).data)
• cur = (*cur).right;
• else
• cur = (*cur).left;
• }
• return false;
• }

Minimal va maksimal

• Minimal – eng chapki element
• Maksimal – eng o’ng tamondagi element

Maksimal C++ da

• int maximum() {
• node *cur = root;
• while ((*cur).right != NULL)
• cur = (*cur).right;
• return (*cur).data;
• }

Element qo’shish

• 1. Yangi elementni qo’shish uchun uni qayerga joylashtirish kerakligini topish
• 2. Daraxtning yangi uzelini tashkil qilish va qo’shiladigan sonni unga joylashtirish
• Qo’shish natijasida daraxtda bir sondan birdan ko’p bo’lmasligi kerak;

20
16
30
10
25
35
26

Qo’shish dasturi

void add(int x) {

if (root==NULL) {

root = new node(x);

return;

}

node *cur = root;

while (1) {

while (1) {

if ((*cur).data==x)

return;

if (x < (*cur).data) {

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

(*cur).left = new node(x);

return;

}

cur = (*cur).left;

}

else {

if ((*cur).right==NULL) {

(*cur).right = new node(x);

return;

}

cur = (*cur).right;

}

}

}

Elementni o’chirish

• O’chirish lozim bo’lgan elementni izlab topish
• Uchta holat bo’lishi mumkin:
• 1. O’chiriladigan uch yaproq. Shunchaki uni o’chiramiz
• 2. O’chiriladigan uch faqat bitta farzandga ega.
• Bu holda uni avlodiga almahtiramiz.
• 3. O’chiriladigan uch ikkita farzandga ega

3-holat

• O’ng qism daraxtdagi
• eng kichik elemanti
• yoki chap qism darax-
• tdagi eng katta sonni
• uning o’rniga qo’ya-
• miz.
• Mustaql dasturini yo-
• zing.

Amallarning ishlash vaqti

• Barcha amallar daraxtning balandligiga bog’liq vaqtda bajariladi. Eng yomon holda O(n). Elementlari tasodifiy tartibda qo’shilganda O(logn);
• Barcha amallarni O(logn) bo’lgan bu tuzilma asosida qurilgan boshqa ma’lumot tuzilmalari mavjud:
• Dekart daraxti
• AVL daraxti
• Qizil-qora daraxt

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) {

• 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;
• }
• }
• }

• Topshiriq: Qo’shish va o’chirish jarayonlarida size maydonining qiymatini yangidan hisoblaydigan qilib yozing.