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


АВЛ дарахт бу мувозанатланган бинар дарахт бўлиб, унда хар бир тугуннинг ўнг ва чап қисм дарахтлари баландликлари орасидаги фарқ 1 дан катта эмас


Download 0.95 Mb.
bet4/5
Sana03.02.2023
Hajmi0.95 Mb.
#1153754
1   2   3   4   5
Bog'liq
DdIPU5G3ejYJi3INtebeotSxmk5awWPOtwDPrjUB

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

  • Download 0.95 Mb.

    Do'stlaringiz bilan baham:
1   2   3   4   5




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