Potpuno binarno stablo vs puno binarno stablo
Binarno stablo je stablo u kojem svaki čvor ima jedno ili dvoje djece. U binarnom stablu, čvor ne može imati više od dva djeteta. U binarnom stablu, djeca se nazivaju "lijevo" i "desno" dijete. Podređeni čvorovi sadrže referencu na svog roditelja. Potpuno binarno stablo je binarno stablo u kojem je svaki nivo binarnog stabla potpuno popunjen osim posljednjeg nivoa. U nepopunjenom nivou, čvorovi su pričvršćeni počevši od krajnje lijeve pozicije. Puno binarno stablo je drvo u kojem svaki čvor u stablu ima dva djeteta osim listova drveta.
Šta je puno binarno stablo?
Puno binarno stablo je binarno stablo u kojem svaki čvor u stablu ima tačno nula ili dva djece. Drugim riječima, svaki čvor u drvetu osim lišća ima tačno dva djeteta. Slika 1 ispod prikazuje puno binarno stablo. U punom binarnom stablu, broj čvorova (n), broj lavesa (l) i broj internih č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 interne čvorove:
– Broj listova l=i+1
– Ukupan broj čvorova n=2i+1
2. Ako puno binarno stablo ima n čvorova:
– Broj internih čvorova i=(n-1)/2
– Broj listova l=(n+1)/2
3. Ako puno binarno stablo ima l listove:
– Ukupan broj čvorova n=2l-1
– Broj internih čvorova i=l-1
Šta je kompletno binarno stablo?
Kao što je prikazano na slici 2, potpuno binarno stablo je binarno stablo u kojem je svaki nivo stabla potpuno popunjen osim posljednjeg nivoa. Također, u posljednjem nivou, čvorovi bi trebali biti pričvršćeni počevši od krajnje lijeve pozicije. Kompletno binarno stablo visine h zadovoljava sljedeće uslove:
– Od korijenskog čvora, nivo iznad posljednjeg nivoa predstavlja puno binarno stablo visine h-1
– Jedan ili više čvorova na zadnjem nivou može imati 0 ili 1 dijete
– Ako su a, b dva čvora na nivou iznad posljednjeg nivoa, tada a ima više djece od b ako i samo ako se a nalazi lijevo od b
Koja je razlika između kompletnog binarnog stabla i punog binarnog stabla?
Potpuna binarna stabla i potpuna binarna stabla imaju jasnu razliku. Dok je puno binarno stablo binarno stablo u kojem svaki čvor ima nula ili dva djeteta, potpuno binarno stablo je binarno stablo u kojem je svaki nivo binarnog stabla potpuno popunjen osim posljednjeg nivoa. Neke posebne strukture podataka kao što su hrpe moraju biti potpuna binarna stabla dok ne moraju biti puna binarna stabla. U punom binarnom stablu, ako znate broj ukupnih čvorova ili broj lavova ili broj unutrašnjih čvorova, možete vrlo lako pronaći druga dva. Ali kompletno binarno stablo nema posebno svojstvo koje se odnosi na ova tri atributa.
