xmlns:w="urn:schemas-microsoft-com:office:word"
xmlns="http://www.w3.org/TR/REC-html40">
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 mani elementlar o`sish yoki kamayishi tartibida kelib tushgan daraxt uzunligi n ga teng bog`langan ro 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 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 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 osish bortasidagi 19 ni ildiz qilib olamiz.
Uning har ikkala tomonida
ong oil 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 borinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor
muvozanatlashning boshqa algoritmlari ishlab chiqilgan.
19
30
23
15
3
12
29
44
16
Binar daraxtni muvozanatlash
Binar daraxtlar bilan ishlaganda unga element qochirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak.
Muvozanatlangan daraxt kotiboringiz uchun rahmat
http://fayllar.org
Do'stlaringiz bilan baham: |
