Algoritmdan nazorat savollariga javoblar Algoritm nima

16.Binar qidiruv daraxtida maksimal va minimal qanday topiladi?
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;

}

Minimal C++ da:

int minimum() {

node *cur = root;

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

cur = (*cur).left;

return (*cur).data;

}

17.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.


18 va 20.Prioritetli navbatda minimalni o’chirish. (18 va 20-chi savol bir xil ekan)

Priotetli navbat - Sonlar navbatini saqlash uchun tuzilma. Navbat boshida hamisha pririteti katta element turadi.

Ikkita amal bajariladi:

• 
  1. Yangi element qo’shish
  
• 
  2. Prioriteti eng katta bo’lgan elementni o’chirish
  

Prioritet sifatida sonning o’zining qiymatini yoki alohida yangi qiymat ishlatimiz mumkin. Qiymati eng kichigi prioriteti eng katta qilib olish ham mumkin.

To’liq ikkilik daraxt ko’rinishiga ega bo’ladi. Har bir uzeldagi qiymat uning farzandlari qiymatlaridan katta bo’ladi.

Massiv shaklida saqlanadi. i-uch uchun:

• 
  2i va 2i+1 uchlar farzandlar.
  
• 
  i/2 uch otasi
  

heap[i]<=heap [2i] va

heap [i]<=heap [2i+1]

Elementlar 1 dan nomerlanadi.

Daraxtning balandligi log(n).