Reja: Binar darxtlar haqida tushuncha Ko`p o`lchamli daraxtni binar ko`rinishga keltirish Daraxtlar ustida amallar. 11-mavzu Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish algoritmlari

11-mavzu Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish algoritmlari. Qidiruv binar daraxtini muvozanatlash algoritmlari

Reja:

• 
  Binar darxtlar haqida tushuncha
  
• 
  Ko`p o`lchamli daraxtni binar ko`rinishga keltirish
  
• 
  Daraxtlar ustida amallar.
  

11-mavzu Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish algoritmlari.Qidiruv binar daraxtini muvozanatlash algoritmlari.

Binar daraxtlar haqida tushuncha

Def.1.
Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tugun bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.


eslatma
Umumiy holda binary daraxt har bir element 4ta maydonga ega yozuv hisoblanadi.
masaan, quyidagi kalit elementardan binar daraxt quramiz:50, 46, 61, 48, 29, 55, 79. u quyidagi ko`riishga ega bo`ladi:

Izoh
Binar daraxtda key(left_son).

оtа

Chаp o`g`il

O`ng o`g`il

Tarif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi

Tarif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi

Yuqorida hosil qilingan binary daraxtimiz ideal muvozanatlangan daraxtga misol bo`ladi.

Tarif 3. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq birdan katta bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi:

m-o`lchamli daraxtni binary ko`rinishga keltirish
Ko`p o`lchamli daraxtni binary ko`rinishga keltirishning noformal algoritmi:Daraxtning har bir tugunida katta o`g`liga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.

•