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

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

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 noqulay

• 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 noqulay
• ligi 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