Komplet binært træ vs fuldt binært træ
Binært træ er et træ, hvor hver knude har et eller to børn. I et binært træ kan en node ikke have mere end to børn. I et binært træ betegnes børn som "venstre" og "højre" børn. Underordnede noder indeholder en henvisning til deres forælder. Et komplet binært træ er et binært træ, hvor hvert niveau af det binære træ er fuldstændigt fyldt undtagen det sidste niveau. I det uudfyldte niveau er knudepunkterne fastgjort startende fra positionen til venstre. Et fuldt binært træ er et træ, hvor hver knude i træet har to børn undtagen træets blade.
Hvad er fuldt binært træ?
Fuldt binært træ er et binært træ, hvor hver knude i træet har nøjagtigt nul eller to børn. Med andre ord har hver knude i træet undtagen bladene nøjagtigt to børn. Figur 1 nedenfor viser et fuldt binært træ. I et fuldt binært træ er antallet af noder (n), antallet af laves (l) og antallet af interne noder (i) relateret til en speciel måde, så hvis du kender en af dem, kan du bestemme de to andre værdier som følger:
1. Hvis et fuldt binært træ har i interne noder:
- Antal blade l = i + 1
- Samlet antal noder n = 2 * i + 1
2. Hvis et fuldt binært træ har n-noder:
- Antal interne noder i = (n-1) / 2
- Antal blade l = (n + 1) / 2
3. Hvis et fuldt binært træ har l blade:
- Samlet antal noder n = 2 * l-1
- Antal interne noder i = l-1
Hvad er komplet binært træ?
Som vist i figur 2 er et komplet binært træ et binært træ, hvor hvert niveau af træet er fuldstændigt fyldt undtagen det sidste niveau. Også på det sidste niveau skal knudepunkter være knyttet fra start til venstre. Et komplet binært træ i højden h opfylder følgende betingelser:
- Fra rodnoden repræsenterer niveauet over sidste niveau et fuldt binært træ med højde h-1
- En eller flere knudepunkter i sidste niveau kan have 0 eller 1 børn
- Hvis a, b er to noder i niveauet over det sidste niveau, har a flere børn end b hvis og kun hvis a er placeret til venstre for b
Hvad er forskellen mellem komplet binært træ og fuldt binært træ?
Komplette binære træer og fulde binære træer har en klar forskel. Mens et fuldt binært træ er et binært træ, hvor hver node har nul eller to børn, er et komplet binært træ et binært træ, hvor hvert niveau af det binære træ er fuldstændigt fyldt undtagen det sidste niveau. Nogle specielle datastrukturer som dynger skal være komplette binære træer, mens de ikke behøver at være fulde binære træer. I et fuldt binært træ, hvis du kender antallet af samlede noder eller antallet af laves eller antallet af interne noder, kan du finde de to andre meget let. Men et komplet binært træ har ikke en særlig egenskab, der vedrører afhandlingens tre attributter.
