Forskjellen mellom komplett binært tre og fullt binært tre

Komplett binært tre mot full binært tre

Binært tre er et tre hvor hver knute har ett eller to barn. I et binært tre kan en knute ikke ha mer enn to barn. I et binært tre kalles barn som "venstre" og "rette" barn. Barnnodeene inneholder en referanse til foreldrene deres. Et komplett binært tre er et binært tre hvor hvert nivå av binærtreet er fullstendig bortsett fra det siste nivået. I det ufylte nivået knyttes knutepunktene fra venstre til venstre. Et fullt binært tre er et tre der hver knute i treet har to barn unntatt bladets tre.

Hva er fullt binært tre?

Full binært tre er et binært tre hvor hver knute i treet har nøyaktig null eller to barn. Med andre ord har hver knute i treet unntatt bladene nøyaktig to barn. Figur 1 nedenfor viser et fullt binært tre. I et fullt binært tre er antallet noder (n), antall laves (l) og antall interne noder (i) relatert på en spesiell måte slik at hvis du kjenner noen av dem, kan du bestemme de to andre verdier som følger:

1. Hvis et fullt binært tre har jeg interne noder:

- Antall blad 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 blad l = (n + 1) / 2

3. Hvis et fullt binært tre har l løv:

- 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 hvor hvert nivå av treet er fullstendig unntatt det siste nivået. Også i det siste nivået bør noder festes fra venstre til venstre. Et komplett binært tre med høyde h tilfredsstiller følgende forhold:

- Fra rotnoden representerer nivået over siste nivå et fullt binært tre med høyde h-1

- Én 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, 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?

Komplette binære trær og full binære trær har en klar forskjell. Mens et fullt binært tre er et binært tre hvor hver knute har null eller to barn, er et komplett binært tre et binært tre hvor hvert nivå av binærtreet er fullt fylt unntatt 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, kan du finne de andre to veldig enkelt hvis du vet antall totale noder eller antall laves eller antall interne noder. Men et komplett binært tre har ikke en spesiell egenskap knyttet til disse tre attributter.