15-mavzu: Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari. Avl daraxti

Binar daraxtlar bilan ishlaganda unga element qo‘shish yoki o‘chirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak. Muvozanatlangan daraxt ko‘rinishlari:

• 
  Binar daraxtlar bilan ishlaganda unga element qo‘shish yoki o‘chirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak. Muvozanatlangan daraxt ko‘rinishlari:
  
• 
  AVL daraxt
  
• 
  Qora-qizil daraxt
  
• 
  B-daraxt va x.k.
  
• 
  

AVL-daraxt

• 
  AVL daraxt bu muvozanatlangan binar daraxt bo‘lib, unda xar bir tugunning o‘ng va chap qism daraxtlari balandliklari orasidagi farq 1 dan katta emas.
  
• 
  AVL daraxtda xar bir tugunning muvozanatlanganlik darajasi xaqidagi ma’lumotni saqlash uchun xar bir tugunga qo‘shimcha maydon kiritiladi.
  
• 
  

АВЛ дарахти

• 
  Asosiy g‘oya: agar element ko‘shish, o‘chirish amallarida muvozanat buzilsa, u xolda daraxt muvozanatlanadi
  
• 
  Tugunning muvozanatlanganlik koeffitsienti (balance factor) bu tugunning chap va o‘ng qism daraxtlari balandligi farqi
  
• 
  AVL daraxtda xar bir tugunning muvozanatlanganlik koeffitsienti (-1, 0, 1) to‘plamdan qiymat qabul qiladi
  
• 
  Tugun balandligi (height) bu undan eng uzoq joylashgan barg tugungacha bo‘lgan balandlik xisoblanadi.
  
• 
  Barg tugunnning balandligi 0 ga teng.
  
• 
  Bo‘sh qism daraxtning balandligi -1 ga teng
  
• 
  

AVL daraxtlari 60-yillarda Sovet olimlari Adelson-Velskiy va Landis tomonidan ixtiro qilingan. Ularning familiyalarining birinchi harflariga ko'ra, ma'lumotlar tuzilishi nomlangan-AVL. Bu klassik ikkilik qidiruv daraxtining modifikatsiyasi bo'lib, u strukturani yaxshiroq muvozanatlashtiradi va deyarli buzilmaydi. Degeneratsiya(Вырождение)-bu har bir tugunda faqat bitta avlod bo'lgan va tuzilish aslida chiziqli bo'lib qoladigan holat-bu optimal bo'lmagan holat.

• 
  AVL daraxtlari 60-yillarda Sovet olimlari Adelson-Velskiy va Landis tomonidan ixtiro qilingan. Ularning familiyalarining birinchi harflariga ko'ra, ma'lumotlar tuzilishi nomlangan-AVL. Bu klassik ikkilik qidiruv daraxtining modifikatsiyasi bo'lib, u strukturani yaxshiroq muvozanatlashtiradi va deyarli buzilmaydi. Degeneratsiya(Вырождение)-bu har bir tugunda faqat bitta avlod bo'lgan va tuzilish aslida chiziqli bo'lib qoladigan holat-bu optimal bo'lmagan holat.