Razlika med celotnim binarnim drevesom in polnim binarnim drevesom

Popolno Binarno Drevo vs Polno Binarno Drevo

Binarno drevo je drevo, kjer ima vsako vozlišče enega ali dva otroka. V binarnem drevesu vozlišče ne sme imeti več kot dveh otrok. V binarnem drevesu so otroci imenovani kot "levi" in "desni" otroci. Otroška vozlišča vsebujejo sklic na svojega starša. Popolno binarno drevo je binarno drevo, v katerem je vsaka raven binarnega drevesa popolnoma napolnjena, razen zadnje stopnje. Na neizpolnjeni ravni so vozlišča pritrjena, začenši z najbolj 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?

Popolno binarno drevo je binarno drevo, v katerem ima vsako vozlišče na drevesu točno nič ali dva otroka. Z drugimi besedami, vsako vozlišče na drevesu razen listov ima točno dva otroka. Slika 1 spodaj prikazuje polno binarno drevo. V polnem binarnem drevesu je število vozlišč (n), število laves (l) in število notranjih vozlišč (i) povezano na poseben način, tako da če poznate katero 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 liste:

- 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 vsaka raven drevesa popolnoma napolnjena, razen zadnje stopnje. Na zadnji ravni naj bodo vozlišča pritrjena, začenši z levega levega položaja. Popolno binarno drevo višine h izpolnjuje naslednje pogoje:

- Od korenskega vozlišča raven nad zadnjo stopnjo predstavlja polno binarno drevo višine h-1

- V enem ali več vozliščih na zadnji ravni je lahko 0 ali 1 otrok

- Če so a, b dve vozli na ravni nad zadnjo stopnjo, potem ima a več otrok kot b, če in le, če se a nahaja levo od b

Kakšna je razlika med celotnim binarnim drevesom in polnim 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 stopnja binarnega drevesa popolnoma napolnjena, razen zadnje stopnje. Nekatere posebne podatkovne strukture, kot so gomile, morajo biti popolna binarna drevesa, medtem ko ni treba, da so polna binarna drevesa. Če veste, koliko skupnih vozlišč ali število lastov ali število notranjih vozlišč lahko najdete, lahko zelo enostavno najdete druga dva. Toda popolno binarno drevo nima posebne lastnosti, ki se nanaša na tri atribute.