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

R – bir marta o`nga burish

L – bir marta chapga burish

• O‘ng qismdaraxtga 3 qo‘shildi. Ildiz va o‘ng tugunni bog‘lovchi yoyni chapga buramiz.
•  

L – bir marta chapga burish

• O‘ng qismdaraxtga yangi element X qo‘shildi.
• Ildiz va o‘ng tugunni birlashtiruvchi yoyni chapga buramiz.
•  

LR – ikki marta chapga o`nga burish

• Ushbu algoritm ildiz chap tugunining o‘ng qismdaraxtiga yangi element kiritilganda qo‘llaniladi.
• 1. R ning chap qismini chapga L burish
•  

LR – ikki marta chapga o`nga burish

• 2. yangi darxtningР tugunini R burish

Daraxt muvozanatlandi

LR – ikki marta chapga o`nga burish

LR – ikki marta chapga o`nga burish

• Bu usul o‘ng qismdaraxtning chap qismiga yangi element kiritilganda qo‘llaniladi
•  

AVL daraxtlarining xususiyatlari

• АВЛ daraxti oddiy ikkilik qidiruv daraxtidan bir nechta xususiyatlari bilan farq qiladi:
• u balandlikda muvozanatli. Har bir tugunning chap va o'ng avlodlari tomonidan hosil bo'lgan pastki daraxtlar uzunligi bir darajadan oshmasligi kerak;

birinchi xususiyatdan yana biri kelib chiqadi — daraxtning umumiy uzunligi va shunga mos ravishda u bilan ishlash tezligi logaritmik va kafolatlangan tugunlar soniga bog'liq;

• birinchi xususiyatdan yana biri kelib chiqadi — daraxtning umumiy uzunligi va shunga mos ravishda u bilan ishlash tezligi logaritmik va kafolatlangan tugunlar soniga bog'liq;
• kuchli muvozanatsiz AVL daraxtini olish ehtimoli juda kichik va uning buzilish xavfi deyarli yo'q.

Binar qidiruv daraxti

• Binar qidiruv daraxti
• AVL – daraxti

Bunday daraxtning muvozanati , ehtimollik bilan muvozanatlangan randomizatsiyalangan daraxtlardan farqli o'laroq kafolatlanadi — ya'ni ozgina ehtimollik bilan tuzilma yana paydo bo'lishi mumkin.

• Bunday daraxtning muvozanati , ehtimollik bilan muvozanatlangan randomizatsiyalangan daraxtlardan farqli o'laroq kafolatlanadi — ya'ni ozgina ehtimollik bilan tuzilma yana paydo bo'lishi mumkin.