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

1 2 3

Bog'liq
6-лаб c732f20aa4501885a58ea2190c7e6ba9

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

Мувозанатланганлик ва асосий тушунчалар
Бинар дарахтларда элементлар келиб тушиш кетма кетлигига қараб дарахт маълум шаклга келади. Бинар дарахт баландлиги узайган сари унинг устида амал бажариш қийинлашиб боради.
Бинар дарахт устида амал бажариш қийинлиги унинг баландигига тўғри пропорцонал.
Дарахт шаклланганда ўртача холатда унинг баландлиги О(log(n)) га тенг.
Энг ёмон холатда, яъни элементлар ўсиш ёки камайиш тартибида келиб тушганда дарахт узунлиги n га тенг боғланган рўйхатга ўхшаб қолади.

Бинар дарахт мувозанатланган дейилади, агар унинг ихтиёрий бир тугунининг хар иккала қисм дарахти баландлиги фарқи 1 га тенг бўлса.
Идеал мувозанатланган дарахтда хар бир тугундан чиқувчи қисм дарахтлар баланлиги тенг хисобланади.
Идеал мувозанатланган бинар дарахтда мавжуд бўладиган тугунлари сони Nтугун ва дарахт баландлиги nбаландлик орасида қуйидагича боғлиқлик мавжуд.
Nтугун = 2nбаландлик − 1
nбаландлик = log2(Nтугун + 1)
Бинар дарахтлар билан ишлашда уни мувозанатлаш зарур омил хисобланади, чунки дарахтнинг баландлиги ошган сари унинг барг тугунларини излаш ва бошқа амалларни бажаришга кетадиган вақт ошиб боради. Шу сабабли дарахтларни мувозанатлашга эхтиёж сезилади.

Бинар дарахтлар билан ишлаганда унга элемент қўшиш ёки ўчиришда унинг мувозанатланганлиги бузилиши мумкин. Бундай холларда уни мувозанатлаб туриш керак. Мувозанатланган дарахт кўринишлари:
АВЛ дарахт
Қора-қизил дарахт
Б-дарахт ва х.к.

Do'stlaringiz bilan baham:

1 2 3