Täydellinen binääripuu vs Täysi binääripuu
Binaarinen puu on puu, jossa jokaisessa solmussa on yksi tai kaksi lasta. Binaaripuussa solmussa voi olla enintään kaksi lasta. Binaaripuussa lapset nimetään "vasen" ja "oikea" lapsiksi. Lapsisolmut sisältävät viittauksen vanhempiinsa. Täydellinen binääripuu on binääripuu, jossa binääripuun kaikki tasot on täysin täytetty viimeistä tasoa lukuun ottamatta. Täyttämättömällä tasolla solmut kiinnitetään alkaen vasemmanpuoleisimmasta sijainnista. Täysi binääripuu on puu, jossa jokaisessa puun solmussa on kaksi lasta paitsi puun lehdet.
Mikä on täysi binaarinen puu?
Täysi binääripuu on binääripuu, jossa jokaisessa puun solmussa on täsmälleen nolla tai kaksi lasta. Toisin sanoen jokaisessa puun solmussa lehtiä lukuun ottamatta on täsmälleen kaksi lasta. Alla oleva kuva 1 kuvaa täydellistä binääripuuta. Täydessä binääripuussa solmujen lukumäärä (n), väylien lukumäärä (l) ja sisäisten solmujen lukumäärä (i) liittyy erityisellä tavalla siten, että jos tunnet jonkin niistä, voit määrittää kaksi muuta arvot seuraavasti:
1. Jos täydellä binääripuulla on i sisäistä solmua:
- Lehtien lukumäärä l = i + 1
- Solmujen kokonaismäärä n = 2 * i + 1
2. Jos täydessä binääripuussa on n solmua:
- Sisäisten solmujen lukumäärä i = (n-1) / 2
- Lehtien lukumäärä l = (n + 1) / 2
3. Jos täysikokoisessa binääripuussa on l lehtiä:
- Solmujen kokonaismäärä n = 2 * l-1
- Sisäisten solmujen lukumäärä i = l-1
Mikä on täydellinen binaarinen puu?
Kuten kuvassa 2 on esitetty, täydellinen binääripuu on binääripuu, jossa puun kaikki tasot ovat täysin täytettyjä viimeistä tasoa lukuun ottamatta. Lisäksi viimeisellä tasolla solmut tulisi kiinnittää alkaen vasemmanpuoleisimmasta sijainnista. Täydellinen binääripuu, jonka korkeus on h, täyttää seuraavat ehdot:
- Juurisolmusta viimeisen tason yläpuolella oleva taso edustaa täyttä binääripuuta, jonka korkeus on h-1
- Yhdessä tai useammassa viimeisen tason solmussa voi olla 0 tai 1 lasta
- Jos a, b ovat kaksi solmua viimeisen tason yläpuolella, niin a: lla on enemmän lapsia kuin b, ja vain, jos a sijaitsee b: n vasemmalla puolella
Mikä on ero täydellisen binääripuun ja täyden binääripuun välillä?
Täydellisillä binääripuilla ja täys binääripuilla on selkeä ero. Vaikka täysi binääripuu on binääripuu, jossa jokaisessa solmussa on nolla tai kaksi lasta, täydellinen binääripuu on binääripuu, jossa binääripuun kaikki tasot ovat täysin täytettyjä viimeistä tasoa lukuun ottamatta. Joidenkin erityisten tietorakenteiden, kuten kasojen, on oltava täydellisiä binääripuita, kun taas niiden ei tarvitse olla täydellisiä binääripuita. Jos tiedät koko binaaripuussa, löydät kaksi muuta erittäin helposti, jos tiedät solmujen kokonaismäärän tai lavesien määrän tai sisäisten solmujen määrän. Mutta täydellisellä binääripuulla ei ole erityisominaisuutta, joka liittyy näihin kolmeen attribuuttiin.
