АВЛ дарахт бу мувозанатланган бинар дарахт бўлиб, унда хар бир тугуннинг ўнг ва чап қисм дарахтлари баландликлари орасидаги фарқ 1 дан катта эмас. АВЛ дарахтда хар бир тугуннинг мувозанатланганлик даражаси хақидаги маълумотни сақлаш учун хар бир тугунга қўшимча майдон киритилади. АВЛ дарахти Тугуннинг мувозанатланганлик коэффициенти (balance factor) бу тугуннинг чап ва ўнг қисм дарахтлари баландлиги фарқи АВЛ дарахтда хар бир тугуннинг мувозанатланганлик коэффициенти (-1, 0, 1) тўпламдан қиймат қабул қилади Тугун баландлиги (height) бу ундан энг узоқ жойлашган барг тугунгача бўлган баландлик хисобланади. Барг тугунннинг баландлиги 0 га тенг. Бўш қисм дарахтнинг баландлиги -1 га тенг Тугун баланлиги
11
Тугуннинг мувозанатланганлик коэффициенти
Бу қисмдарахт баландиги =1
11
Тугуннинг мувозанатланганлик коэффициенти
Бу АВЛ дарахт эмас
Бу қисмдарахт баландиги =1
11
- Бинар дарахтни мувозанатлаш учун уни чапдан ўнгга сканерлаймиз, шунда сонлар ўсиш бўйича тартибланиб чиқади.
- М-н: 3,12,15,16,19,23,29,30,44
- Ушбу сонларнинг ўртасида
ги 19 ни илдиз қилиб оламиз. - Унинг хар иккала томонида
ўртада жойлашган 12 ва 29 ни илдизнинг чап ва ўнг ўғил тугунлари қилиб оламиз.Қолганларни хам худди шу тартибда жойлаб чиқамиз.
30
15
3
19
12
16
44
29
23
Натижада қуйидагича мувозанатланган бинар дарахт хосил бўлади. Олдинги кўринишида дарахт баландлиги 4 га тенг эди. Энди эса 3 га тенг. Лекин бу алгоритмнинг бир мунча ноқулай - Натижада қуйидагича мувозанатланган бинар дарахт хосил бўлади. Олдинги кўринишида дарахт баландлиги 4 га тенг эди. Энди эса 3 га тенг. Лекин бу алгоритмнинг бир мунча ноқулай
Do'stlaringiz bilan baham: |