Komplett binært tre vs Full binært tre
Binært tre er et tre der hver node har ett eller to barn. I et binært tre kan en node ikke ha mer enn to barn. I et binært tre blir barn kalt "venstre" og "høyre" barn. Barnetodene inneholder en referanse til foreldrene. Et komplett binært tre er et binært tre der hvert nivå av binærtreet er fullstendig unntatt det siste nivået. I det ufylte nivået er nodene festet fra den venstre posisjonen. Et fullt binært tre er et tre der hver node i treet har to barn, bortsett fra bladene på treet.
Hva er Full Binary Tree?
Fullt 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, bortsett fra bladene, har nøyaktig to barn. Figur 1 nedenfor viser et fullt 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 fullt binært tre har i interne noder:
- Antall blader l = i + 1
- Totalt antall noder n = 2 * i + 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:
- Totalt antall noder n = 2 * l-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å av treet er fullstendig fylt unntatt det siste nivået. I det siste nivået skal det også festes noder med utgangspunkt i posisjonen til venstre. Et komplett binært høydetre h oppfyller 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 i siste nivå kan ha 0 eller 1 barn
- Hvis a, b er to noder i nivået over det siste nivået, har a flere barn enn b hvis og bare hvis a ligger til venstre for b
Hva er forskjellen mellom Complete Binary Tree og Full Binary Tree?
Komplette binære trær og full binære trær har en klar forskjell. Mens et fullstendig 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å av binærtreet er fullstendig bortsett fra det siste nivået. Noen spesielle datastrukturer som dynger trenger å være komplette binære trær mens de ikke trenger å være fulle binære trær. Hvis du vet antall totale noder eller antall laver eller antall interne noder, i et fullstendig binært tre, kan du finne de to andre veldig enkelt. Men et komplett binært tre har ikke en spesiell egenskap knyttet til disse tre attributtene.
