Разлика између комплетног бинарног стабла и потпуног бинарног стабла

Комплетно Бинарно Дрво вс Потпуно Бинарно Дрво

Бинарно дрво је дрво на коме сваки чвор има једно или двоје деце. У бинарном дрвету, чвор не може имати више од двоје деце. У бинарном дрвету деца су именована као деца „лево и десно“. Дечији чворови садрже референцу на свог родитеља. Комплетно бинарно дрво је бинарно дрво у коме је сваки ниво бинарног стабла потпуно испуњен осим последњег нивоа. На непопуњеном нивоу чворови су причвршћени почевши од леве стране. Потпуно бинарно дрво је дрво у коме сваки чвор на дрвету има двоје деце осим лишћа.

Шта је потпуно бинарно дрво?

Потпуно бинарно дрво је бинарно дрво у којем сваки чвор на дрвету има тачно нулу или двоје деце. Другим речима, сваки чвор на дрвету осим лишћа има тачно двоје деце. Слика 1 испод приказује потпуно бинарно стабло. У пуном бинарном стаблу број чворова (н), број лавеса (л) и број унутрашњих чворова (и) повезани су на посебан начин, тако да ако познајете било који од њих, можете одредити друга два вредности су следеће:

1. Ако потпуно бинарно стабло има и унутрашње чворове:

- Број листова л = и + 1

- Укупан број чворова н = 2 * и + 1

2. Ако потпуно бинарно стабло има н чворова:

- Број унутрашњих чворова и = (н-1) / 2

- Број листова л = (н + 1) / 2

3. Ако потпуно бинарно дрво има л лишће:

- Укупан број чворова н = 2 * л-1

- Број унутрашњих чворова и = л-1

Шта је комплетно бинарно дрво?

Као што је приказано на слици 2, комплетно бинарно стабло је бинарно дрво у коме је сваки ниво стабла потпуно испуњен осим последњег нивоа. Такође, на последњем нивоу, чворове треба причврстити почевши од положаја са највише леве стране. Комплетно бинарно дрво висине х задовољава следеће услове:

- Из коријенског чвора, ниво изнад задњег нивоа представља потпуно бинарно дрво висине х-1

- Један или више чворова на последњем нивоу може имати 0 или 1 детета

- Ако су а, б два чвора на нивоу изнад последњег нивоа, тада а има више деце него б ако и само ако се а налази лево од б

Која је разлика између комплетног бинарног стабла и потпуног бинарног стабла?

Комплетна бинарна стабла и пуна бинарна стабла имају јасну разлику. Док је потпуно бинарно дрво бинарно дрво у коме сваки чвор има нула или двоје деце, комплетно бинарно дрво је бинарно дрво у коме је сваки ниво бинарног стабла потпуно испуњен осим последњег нивоа. Неке посебне структуре података попут гомиле морају бити комплетна бинарна стабла док не морају бити пуна бинарна стабла. У пуном бинарном стаблу, ако знате број укупних чворова или број лакова или број унутрашњих чворова, остала два ћете лако наћи. Али комплетно бинарно стабло нема посебно својство које се односи на тезе три атрибута.