Täydellinen binääripuu vs täysi binääripuu
Binaaripuu on puu, jossa jokaisella solmulla on yksi tai kaksi lasta. Binääripuussa solmulla ei voi olla enempää kuin kaksi lasta. Binääripuussa lapset nimetään "vasemmiksi" ja "oikeiksi" lapsiksi. Lapsisolmut sisältävät viittauksen emokseensa. Täydellinen binääripuu on binääripuu, jossa binääripuun jokainen taso on täysin täytetty viimeistä tasoa lukuun ottamatta. Täyttämättömällä tasolla solmut kiinnitetään äärimmäisestä vasemmasta kohdasta alkaen. Täysi binääripuu on puu, jossa jokaisella puun solmulla on kaksi lasta paitsi puun lehtiä.
Mikä on täysi binääripuu?
Täysi binääripuu on binääripuu, jossa jokaisella puun solmulla on tasan nolla tai kaksi lasta. Toisin sanoen jokaisella puun solmulla lehtiä lukuun ottamatta on täsmälleen kaksi lasta. Alla oleva kuva 1 esittää koko binääripuuta. Täydessä binääripuussa solmujen lukumäärä (n), lavien lukumäärä (l) ja sisäisten solmujen lukumäärä (i) liittyvät erityisellä tavalla siten, että jos tiedät yhden niistä, voit määrittää kaksi muuta arvot seuraavasti:
1. Jos täydessä binääripuussa on i sisäisiä solmuja:
– lehtien lukumäärä l=i+1
– Solmujen kokonaismäärä n=2i+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äydessä binääripuussa on l lehtiä:
– Solmujen kokonaismäärä n=2l-1
– Sisäisten solmujen lukumäärä i=l-1
Mikä on täydellinen binaaripuu?
Kuten kuvasta 2 näkyy, täydellinen binääripuu on binääripuu, jossa puun jokainen taso on täysin täytetty viimeistä tasoa lukuun ottamatta. Lisäksi viimeisellä tasolla solmut tulee kiinnittää alkaen vasemmanpuoleisimm alta paik alta. Täydellinen binääripuu, jonka korkeus on h, täyttää seuraavat ehdot:
– Juurisolmusta alkaen viimeisen tason yläpuolella oleva taso edustaa täyttä binaaripuuta, jonka korkeus on h-1
– Yhdellä tai useammalla viimeisen tason solmulla 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:llä, jos ja vain jos a sijaitsee b:n vasemmalla
Mitä eroa on täydellisellä binääripuulla ja täydellä binääripuulla?
Täydellisillä binääripuilla ja täysillä binääripuilla on selvä ero. Täysi binääripuu on binääripuu, jossa jokaisella solmulla on nolla tai kaksi lasta, kun taas täydellinen binääripuu on binääripuu, jossa binääripuun jokainen taso on täysin täytetty viimeistä tasoa lukuun ottamatta. Joidenkin erityisten tietorakenteiden, kuten pinojen, on oltava täydellisiä binääripuita, kun taas niiden ei tarvitse olla täydellisiä binääripuita. Täydestä binääripuusta, jos tiedät solmujen kokonaismäärän tai lavien lukumäärän tai sisäisten solmujen lukumäärän, voit löytää kaksi muuta erittäin helposti. Mutta täydellisellä binääripuulla ei ole erityistä ominaisuutta, joka liittyisi näihin kolmeen attribuuttiin.
