Popolno binarno drevo vs popolno binarno drevo
Binarno drevo je drevo, kjer ima vsako vozlišče enega ali dva otroka. V binarnem drevesu vozlišče ne more imeti več kot dva otroka. V binarnem drevesu so otroci imenovani kot "levi" in "desni" otroci. Podrejena vozlišča vsebujejo sklic na svojega starša. Popolno binarno drevo je binarno drevo, v katerem je popolnoma izpolnjena vsaka stopnja binarnega drevesa, razen zadnje ravni. Na neizpolnjeni ravni so vozlišča pritrjena od skrajnega levega položaja. Polno binarno drevo je drevo, v katerem ima vsako vozlišče na 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 natanko nič ali dva otroka. Z drugimi besedami, vsako vozlišče na drevesu, razen listov, ima natanko dva otroka. Slika 1 spodaj prikazuje celotno binarno drevo. V celotnem binarnem drevesu je število vozlišč (n), število odprtin (l) in število notranjih vozlišč (i) povezano na poseben način, tako da, če poznate katerega od njih, lahko določite druga dva vrednosti, kot sledi:
1. Če ima polno binarno drevo i notranja vozlišča:
- Število listov l = i + 1
- Skupno število vozlišč n = 2 * i + 1
2. Če ima polno 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 = 2 * l-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 vsa raven drevesa popolnoma zapolnjena, razen zadnje ravni. Na zadnji ravni naj bodo vozlišča pritrjena od skrajnega levega položaja. Popolno binarno drevo višine h izpolnjuje naslednje pogoje:
- Od korenskega vozlišča nivo nad zadnjo stopnjo predstavlja polno binarno drevo višine h-1
- Eno ali več vozlišč na zadnji ravni ima lahko 0 ali 1 otroka
- Če sta a, b dve vozlišči na ravni nad zadnjo stopnjo, potem ima a več podrejenih kot b, če in le, če se a nahaja levo od b
Kakšna je razlika med popolnim binarnim drevesom in popolnim binarnim drevesom?
Popolna binarna drevesa in polna binarna drevesa imajo očitno 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 vsa raven binarnega drevesa popolnoma zapolnjena, razen zadnje ravni. Nekatere posebne podatkovne strukture, kot so kupi, morajo biti popolna binarna drevesa, medtem ko jim ni treba biti polna binarna drevesa. Če poznate skupno število vozlišč ali število odprtin ali število notranjih vozlišč, lahko v popolnem binarnem drevesu druga dva najdete zelo enostavno. Toda popolno binarno drevo nima posebne lastnosti, ki bi povezala ta tri atribute.
