“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

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.

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