Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari

Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari.

Muvozanatlanganlik va asosiy tushunchalar
Binar daraxtlarda elementlar kelib tushish ketma ketligiga qarab daraxt ma’lum shaklga keladi. Binar daraxtda balandligi uzaygan sari uning ustida amal bajarish qiyinlashib boradi. Binar daraxt ustida amal bajarish qiyinligi uning balandligiga 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 ro’yxatga o`xshab qoladi.
Muvozanatlanganlik va asosiy tushunchalar
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.
• 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.

Balansli va degeneratsiyalangan daraxtlar o'rtasida oraliq variantlar mavjud.
Mukammal muvozanatli daraxt — iloji boricha kengaytirilgan va pastlatilgan.
Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi.
Shunday qilib, undan foydalanish iloji boricha samarali bo'ladi.
Mukammal muvozanatli daraxt — iloji boricha kengaytirilgan va pastlatilgan.
Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi.
Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi.
Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi.
Daraxt qanchalik yaxshi muvozanatlangan bo'lsa, u shunchalik samarali bo'ladi.
Muvozanatlanganlik va asosiy tushunchalar
Muvozanatlanganlik va asosiy tushunchalar
TA’RIF.Binar daraxt muvozanatlangan deyiladi ,agar uning ihtiyoriy bir tugunining har ikkala qism daraxti balandligining farqi 1ga teng bo`lsa.
Ideal muvozanatlangan daraxtda har bir tugundan chiquvchi qism daraxtlar balandligi teng hisoblanadi. Ideal muvozanatlangan binar daraxtda mavjud bo`ladigan tugunlar soni Ntugun va daraxt balandligi nbalandlik orasida quyidagicha bog‘liqlik mavjud.
Ntugun = 2nbalandlik − 1 nbalandlik = log2(Ntugun + 1)
Binar daraxtlar bilan ishlashda uni muvozanatlash zarur omil hisoblanadi, chunki daraxtning balandligi oshgan sari uning barg tugunlarini izlash va boshqa amallarni bajarishga ketadigan vaqt oshib boradi. SHu sababli daraxtlarni muvozanatlashga extiyoj seziladi.
Binar daraxtni muvozanatlash
Binar daraxtni muvozanatlash uchun uni chapdan o‘ngga skanerlaymiz, shunda sonlar o‘sish bo‘yicha tartiblanib chiqadi.
Masalan:
3,12,15,16,19,23,29,30,44
Ushbu sonlarning o‘rtasidagi 19 ni ildiz qilib olamiz.
Uning har ikkala tomonida
o‘rtada joylashgan 12 va 29 ni ildizning chap va o‘ng o‘g‘il tugunlari qilib olamiz.
Qolganlarni ham xuddi shu tartibda joylab chiqamiz.
30
15
3
19
12
16
44
29
23
Binar daraxtni muvozanatlash
Natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. Oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor

• Oldin daraxtni chapdan
• o‘ngga skanerlab elementlar
• dan massiv hosil qilish kerak.
• Bu esa xotiradan joy talab etadi.
• Bu usulda daraxtni boshqatdan

qurish kerak bo‘ladi. Keyinchalik
muvozanatlashning boshqa algoritmlari ishlab chiqilgan.

19
30
23
15
3
12
29
44
16
Binar daraxtni muvozanatlash
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. 

E’tiboringiz uchun rahmat