11-mavzu(davomi): Qidiruv binar daraxtini muvozanatlash algoritmlari

11-mavzu(davomi): Qidiruv binar daraxtini muvozanatlash algoritmlari.

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.

TA’RIF.Binar daraxt muvozanatlangan deyiladi ,agar uning ihtiyoriy bir tugunining har ikkala qism daraxti balandligining farqi 1ga teng bo`lsa.

• 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.
• M-n: 3,12,15,16,19,23,29,30,44
• Ushbu sonlarning o‘rtasida
• gi 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