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

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

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

Reja:

• 
  Muvozanatlanganlik va asosiy tushunchalar
  
• 
  AVL-daraxti
  
• 
  Muvozanatlash algoritmlari
  

Muvozanatlanganlik va asosiy tushunchalar

Binar darxtlarda elementlar kelib tushish ketma ketligiiga qarab daraxt ma’lum shaklga keladi. Binar daraxtda balandligi uzaygan sari uning ustida amal bajarish qiyinlashib boradi. Binar daraxt ustida amal bajarish qiyinligi uning blanadligiga to`g`ri proporsional. Daraxt shakllanganda o`rtacha holatda uning samaradorligi О(log(n)) ga teng.

Eng yomon holatda, ya’ni elementlar o`sish yoki kamayishi tartibida kelib tushgan daraxt uzunligi n ga teng bog`langan royhatga o`xshab qoladi.

Turlari. Daraxt muvozanatli bo'lishi mumkin, ya'ni optimal taqsimlangan daraxtga o'xshash tuzilishga ega, mukammal muvozanatli yoki degeneratsiyalangan: bu holda u aslida chiziqli bo'ladi, chunki har bir tugunning faqat bitta avlodi bor. Bunday daraxtlar ba'zan лоза deb ataladi. Ulardagi operatsiyalarni bajarish tezligi chiziqli bo'ladi va muvozanatli bo'lsa, u logarifmikaga yaqinroq bo'ladi, bu tezroq amalga oshiriladi.

• 
  Turlari. Daraxt muvozanatli bo'lishi mumkin, ya'ni optimal taqsimlangan daraxtga o'xshash tuzilishga ega, mukammal muvozanatli yoki degeneratsiyalangan: bu holda u aslida chiziqli bo'ladi, chunki har bir tugunning faqat bitta avlodi bor. Bunday daraxtlar ba'zan лоза deb ataladi. Ulardagi operatsiyalarni bajarish tezligi chiziqli bo'ladi va muvozanatli bo'lsa, u logarifmikaga yaqinroq bo'ladi, bu tezroq amalga oshiriladi.
  

Balansli va degeneratsiyalangan daraxtlar o'rtasida oraliq variantlar mavjud. Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi. Muvozanatlangan daraxt(Balansli daraxt)-bu cheklangan tugunlardan tashqari barcha tugunlarning ikkita avlodi va bir xil darajadagi barcha kichik daraxtlarning uzunligi bir xil bo'lgan daraxtdir. Mukammal muvozanatli daraxt — iloji boricha kengaytirilgan va pastlatilgan. Shunday qilib, undan foydalanish iloji boricha samarali bo'ladi.

• 
  Balansli va degeneratsiyalangan daraxtlar o'rtasida oraliq variantlar mavjud. Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi. Muvozanatlangan daraxt(Balansli daraxt)-bu cheklangan tugunlardan tashqari barcha tugunlarning ikkita avlodi va bir xil darajadagi barcha kichik daraxtlarning uzunligi bir xil bo'lgan daraxtdir. Mukammal muvozanatli daraxt — iloji boricha kengaytirilgan va pastlatilgan. Shunday qilib, undan foydalanish iloji boricha samarali bo'ladi.