Popolno binarno drevo v primerjavi s celotnim binarnim drevesom
Binarno drevo je drevo, kjer ima vsako vozlišče enega ali dva otroka. V binarnem drevesu vozlišče ne more imeti več kot dveh otrok. V binarnem drevesu so otroci poimenovani kot "levi" in "desni" otroci. Podrejena vozlišča vsebujejo sklic na svojega nadrejenega. Popolno binarno drevo je binarno drevo, v katerem je vsak nivo binarnega drevesa v celoti zapolnjen, razen zadnje ravni. V nezapolnjeni ravni so vozlišča pritrjena od skrajnega levega položaja. Polno binarno drevo je drevo, v katerem ima vsako vozlišče v drevesu dva otroka razen listov drevesa.
Kaj je polno binarno drevo?
Polno binarno drevo je binarno drevo, v katerem ima vsako vozlišče v drevesu točno nič ali dva otroka. Z drugimi besedami, vsako vozlišče v drevesu, razen listov, ima točno dva otroka. Slika 1 spodaj prikazuje celotno binarno drevo. V polnem binarnem drevesu je število vozlišč (n), število lavov (l) in število notranjih vozlišč (i) povezano na poseben način, tako da če poznate katero od njih, lahko določite drugi dve naslednje vrednosti:
1. Če ima polno binarno drevo i notranja vozlišča:
– Število listov l=i+1
– skupno število vozlišč n=2i+1
2. Če ima celotno binarno drevo n vozlišč:
– število notranjih vozlišč i=(n-1)/2
– Število listov l=(n+1)/2
3. Če ima polno binarno drevo l listov:
– skupno število vozlišč n=2l-1
– Število notranjih vozlišč i=l-1
Kaj je popolno binarno drevo?
Kot je prikazano na sliki 2, je popolno binarno drevo binarno drevo, v katerem je vsaka raven drevesa popolnoma zapolnjena, razen zadnje ravni. Prav tako je treba na zadnji ravni pritrditi vozlišča od skrajnega levega položaja. Popolno binarno drevo višine h izpolnjuje naslednje pogoje:
– Od korenskega vozlišča nivo nad zadnjim nivojem predstavlja celotno binarno drevo višine h-1
– Eno ali več vozlišč na zadnji ravni ima lahko 0 ali 1 podrejenega
– Če sta a, b dve vozlišči na ravni nad zadnjo ravnjo, ima a več podrejenih kot b, če in samo če je a levo od b
Kakšna je razlika med popolnim binarnim drevesom in celotnim binarnim drevesom?
Popolna binarna drevesa in polna binarna drevesa imajo jasno razliko. Medtem ko je polno binarno drevo binarno drevo, v katerem ima vsako vozlišče nič ali dva otroka, je popolno binarno drevo binarno drevo, v katerem je vsaka raven binarnega drevesa popolnoma zapolnjena, razen zadnje ravni. Nekatere posebne podatkovne strukture, kot so kopice, morajo biti popolna binarna drevesa, ni pa nujno, da so polna binarna drevesa. Če v polnem binarnem drevesu poznate skupno število vozlišč ali število lavov ali število notranjih vozlišč, lahko drugi dve zelo enostavno najdete. Toda popolno binarno drevo nima posebne lastnosti, ki bi povezovala te tri atribute.
