Potpuno binarno stablo u odnosu na potpuno binarno stablo
Binarno stablo je stablo u kojem svaki čvor ima jedno ili dva djeteta. U binarnom stablu, čvor ne može imati više od dva djeteta. U binarnom stablu, djeca su imenovana kao "lijeva" i "desna" djeca. Podređeni čvorovi sadrže referencu na svog roditelja. Potpuno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla u potpunosti ispunjena osim posljednje razine. U neispunjenoj razini, čvorovi su pričvršćeni počevši od krajnje lijeve pozicije. Potpuno binarno stablo je stablo u kojem svaki čvor u stablu ima dva djeteta osim listova stabla.
Što je potpuno binarno stablo?
Puno binarno stablo je binarno stablo u kojem svaki čvor u stablu ima točno nula ili dva djeteta. Drugim riječima, svaki čvor u stablu osim lišća ima točno dva djeteta. Slika 1 u nastavku prikazuje puno binarno stablo. U potpunom binarnom stablu, broj čvorova (n), broj lava (l) i broj unutarnjih čvorova (i) povezani su na poseban način tako da ako znate bilo koji od njih, možete odrediti druga dva vrijednosti kako slijedi:
1. Ako puno binarno stablo ima i unutarnjih čvorova:
– Broj listova l=i+1
– Ukupan broj čvorova n=2i+1
2. Ako puno binarno stablo ima n čvorova:
– Broj unutarnjih čvorova i=(n-1)/2
– Broj listova l=(n+1)/2
3. Ako puno binarno stablo ima l listova:
– Ukupan broj čvorova n=2l-1
– Broj unutarnjih čvorova i=l-1
Što je potpuno binarno stablo?
Kao što je prikazano na slici 2, potpuno binarno stablo je binarno stablo u kojem je svaka razina stabla potpuno popunjena osim posljednje razine. Također, u posljednjoj razini, čvorovi bi trebali biti pričvršćeni počevši od krajnje lijeve pozicije. Kompletno binarno stablo visine h zadovoljava sljedeće uvjete:
– Od korijenskog čvora, razina iznad posljednje razine predstavlja puno binarno stablo visine h-1
– Jedan ili više čvorova na zadnjoj razini mogu imati 0 ili 1 djecu
– Ako su a, b dva čvora na razini iznad posljednje razine, tada a ima više djece od b ako i samo ako je a smješten lijevo od b
Koja je razlika između potpunog binarnog stabla i potpunog binarnog stabla?
Potpuna binarna stabla i potpuna binarna stabla imaju jasnu razliku. Dok je potpuno binarno stablo binarno stablo u kojem svaki čvor ima nula ili dva djeteta, potpuno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla potpuno popunjena osim posljednje razine. Neke posebne podatkovne strukture poput gomila moraju biti potpuna binarna stabla, ali ne moraju biti potpuna binarna stabla. U potpunom binarnom stablu, ako znate broj ukupnih čvorova ili broj lava ili broj unutarnjih čvorova, možete vrlo lako pronaći druga dva. Ali potpuno binarno stablo nema posebno svojstvo koje povezuje ova tri atributa.
