Komplett binärt träd vs Fullt binärt träd
Binärt träd är ett träd där varje nod har ett eller två barn. I ett binärt träd kan en nod inte ha mer än två barn. I ett binärt träd benämns barn som”vänster” och”höger” barn. Barnnoderna innehåller en hänvisning till sin förälder. Ett komplett binärt träd är ett binärt träd där varje nivå i det binära trädet fylls helt utom den sista nivån. I den ofyllda nivån fästs noderna med början från positionen längst till vänster. Ett fullständigt binärt träd är ett träd där varje nod i trädet har två barn utom trädets löv.
Vad är Full Binary Tree?
Fullt binärt träd är ett binärt träd där varje nod i trädet har exakt noll eller två barn. Med andra ord har varje nod i trädet utom bladen exakt två barn. Figur 1 nedan visar ett fullständigt binärt träd. I ett fullständigt binärt träd är antalet noder (n), antalet laves (l) och antalet interna noder (i) relaterade på ett speciellt sätt så att om du känner någon av dem kan du bestämma de andra två värden enligt följande:
1. Om ett fullständigt binärt träd har i interna noder:
- Antal löv l = i + 1
- Totalt antal noder n = 2 * i + 1
2. Om ett fullständigt binärt träd har n-noder:
- Antal interna noder i = (n-1) / 2
- Antal blad l = (n + 1) / 2
3. Om ett fullständigt binärt träd har l löv:
- Totalt antal noder n = 2 * l-1
- Antal interna noder i = l-1
Vad är komplett binärt träd?
Som visas i figur 2 är ett komplett binärt träd ett binärt träd där varje nivå i trädet är helt fyllt utom den sista nivån. På den sista nivån bör noder också fästas från början längst till vänster. Ett komplett binärt höjdträd uppfyller följande villkor:
- Från rotnoden representerar nivån över den sista nivån ett fullständigt binärt träd med höjd h-1
- En eller flera noder på sista nivån kan ha 0 eller 1 barn
- Om a, b är två noder i nivån ovanför den sista nivån, har a fler barn än b om och bara om a ligger till vänster om b
Vad är skillnaden mellan Complete Binary Tree och Full Binary Tree?
Kompletta binära träd och fullständiga binära träd har en tydlig skillnad. Medan ett fullständigt binärt träd är ett binärt träd där varje nod har noll eller två barn, är ett komplett binärt träd ett binärt träd där varje nivå i det binära trädet är helt fyllt utom den sista nivån. Vissa speciella datastrukturer som högar måste vara kompletta binära träd medan de inte behöver vara fullständiga binära träd. I ett fullständigt binärt träd, om du vet antalet totala noder eller antalet lavar eller antalet interna noder, kan du hitta de andra två mycket enkelt. Men ett komplett binärt träd har ingen speciell egenskap som relaterar till dessa tre attribut.
