Fullstendig binært tre vs fullt binært tre
Binært tre er et tre der hver node har ett eller to barn. I et binært tre kan ikke en node ha mer enn to barn. I et binært tre er barn navngitt som "venstre" og "høyre" barn. Undernodene inneholder en referanse til deres forelder. Et komplett binært tre er et binært tre der hvert nivå i det binære treet er fullstendig fylt bortsett fra det siste nivået. I det ufylte nivået festes nodene fra posisjonen lengst til venstre. Et fullt binært tre er et tre der hver node i treet har to barn bortsett fra bladene på treet.
Hva er fullt binært tre?
Full binært tre er et binært tre der hver node i treet har nøyaktig null eller to barn. Med andre ord, hver node i treet unntatt bladene har nøyaktig to barn. Figur 1 nedenfor viser et fullstendig binært tre. I et fullt binært tre er antall noder (n), antall laver (l) og antall interne noder (i) relatert på en spesiell måte slik at hvis du kjenner en av dem kan du bestemme de to andre verdier som følger:
1. Hvis et fullstendig binært tre har i interne noder:
– Antall blader l=i+1
– Tot alt antall noder n=2i+1
2. Hvis et fullt binært tre har n noder:
– Antall interne noder i=(n-1)/2
– Antall blader l=(n+1)/2
3. Hvis et fullt binært tre har l blader:
– Tot alt antall noder n=2l-1
– Antall interne noder i=l-1
Hva er komplett binært tre?
Som vist i figur 2, er et komplett binært tre et binært tre der hvert nivå i treet er fullstendig fylt bortsett fra det siste nivået. I det siste nivået bør også noder festes fra posisjonen lengst til venstre. Et komplett binært tre med høyde h tilfredsstiller følgende betingelser:
– Fra rotnoden representerer nivået over siste nivå et fullt binært tre med høyden h-1
– En eller flere noder på siste nivå kan ha 0 eller 1 barn
– Hvis a, b er to noder i nivået over det siste nivået, så har a flere barn enn b hvis og bare hvis a er plassert til venstre for b
Hva er forskjellen mellom komplett binært tre og fullt binært tre?
Fullstendige binære trær og fulle binære trær har en klar forskjell. Mens et fullt binært tre er et binært tre der hver node har null eller to barn, er et komplett binært tre et binært tre der hvert nivå i det binære treet er fullstendig fylt bortsett fra det siste nivået. Noen spesielle datastrukturer som hauger må være komplette binære trær mens de ikke trenger å være fulle binære trær. I et fullt binært tre, hvis du vet antall totale noder eller antall laver eller antall interne noder, kan du finne de to andre veldig enkelt. Men et komplett binært tre har ikke en spesiell egenskap knyttet til disse tre attributtene.
