Forskjell mellom fullstendig binært tre og fullt binært tre Komplett binært tre vs full binært tre binært tre er
Komplett binært tre mot fullt 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 Full 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:
en. Hvis et fullt binært tre har i 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 = 1-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 bortsett fra 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 betingelser:
- Fra rotnoden representerer nivået over siste nivå et fullt binært trehøyde 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 siste nivå, har a flere barn enn b hvis og bare hvis a ligger til venstre for b
Hva er forskjellen mellom Complete Binary Tree og fullt binært tre?
Komplette 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 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 fullstendig 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, 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.
