Ntugun va daraxt balandligi nbalandlik


Download 10.65 Kb.
Sana11.11.2023
Hajmi10.65 Kb.
#1766993
Bog'liq
Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari m-fayllar.org


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


  • Oldin daraxtni chapdan
  • oladi. Keyinchalik

    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

Download 10.65 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling