6-лаборатория: Бинар дарахтни мувозанатлаш Ишдан мақсад

АВЛ-дарахти

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