Komplet binært træ vs fuldt binært træ
Binært træ er et træ, hvor hver node 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æ er børn navngivet som "venstre" og "højre" børn. De underordnede noder indeholder en reference til deres forælder. Et komplet binært træ er et binært træ, hvor hvert niveau i det binære træ er fuldstændigt udfyldt undtagen det sidste niveau. I det ufyldte niveau er knudepunkterne fastgjort fra positionen længst 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 node i træet har nøjagtig nul eller to børn. Med andre ord, hver knude i træet undtagen bladene har præcis 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 laver (l) og antallet af interne noder (i) relateret på en særlig 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=2i+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=2l-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 i træet er fuldstændigt udfyldt undtagen det sidste niveau. På det sidste niveau skal der også fastgøres noder fra positionen længst til venstre. Et komplet binært træ med højden h opfylder følgende betingelser:
– Fra rodnoden repræsenterer niveauet over sidste niveau et fuldt binært træ med højden h-1
– En eller flere noder i sidste niveau kan have 0 eller 1 børn
– Hvis a, b er to noder i niveauet over det sidste niveau, så 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æ?
Fuldstændige 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 i det binære træ er fuldstændigt udfyldt undtagen det sidste niveau. Nogle specielle datastrukturer så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 laver eller antallet af interne noder, kan du meget nemt finde de to andre. Men et komplet binært træ har ikke en særlig egenskab, der relaterer disse tre attributter.
