Рекурсив маълумотлар тузилмаси

АВЛ дарахт бу мувозанатланган бинар дарахт бўлиб, унда хар бир тугуннинг ўнг ва чап қисм дарахтлари баландликлари орасидаги фарқ 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 га тенг. Лекин бу алгоритмнинг бир мунча ноқулай