Kompletno binarno stablo vs potpuno 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 dvoje djece. U binarnom stablu djeca se nazivaju "lijevom" i "desnom" djecom. Podređeni čvorovi sadrže referencu na svog roditelja. Potpuno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla potpuno ispunjena, osim posljednje razine. U neispunjenoj razini, čvorovi su pričvršćeni počevši od krajnjeg lijevog položaja. Potpuno binarno stablo je stablo u kojem svaki čvor na drvetu ima dvoje djece, osim lišća stabla.
Što je potpuno binarno stablo?
Potpuno binarno stablo je binarno stablo u kojem svaki čvor u stablu ima točno nula ili dvoje djece. Drugim riječima, svaki čvor na drvetu, osim lišća, ima točno dvoje djece. Slika 1 dolje prikazuje potpuno binarno stablo. U punom binarnom stablu, broj čvorova (n), broj utora (l) i broj unutarnjih čvorova (i) povezani su na poseban način, tako da ako znate bilo kojeg od njih, možete odrediti druga dva vrijednosti kako slijedi:
1. Ako puno binarno stablo ima i unutarnje čvorove:
- Broj listova l = i + 1
- Ukupan broj čvorova n = 2 * i + 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 listova:
- Ukupan broj čvorova n = 2 * l-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 ispunjena, osim posljednje razine. Također, na posljednjoj razini, čvorovi bi trebali biti pričvršćeni počevši od krajnjeg lijevog položaja. Kompletno binarno stablo visine h zadovoljava sljedeće uvjete:
- Od korijenskog čvora, razina iznad posljednje razine predstavlja potpuno binarno stablo visine h-1
- Jedan ili više čvorova na posljednjoj razini može imati 0 ili 1 djece
- Ako su a, b dva čvora u razini iznad posljednje razine, tada a ima više djece od b ako i samo ako se a nalazi lijevo od b
Koja je razlika između cjelovitog binarnog stabla i punog binarnog stabla?
Kompletna binarna stabla i puna binarna stabla imaju jasnu razliku. Dok je potpuno binarno stablo binarno stablo u kojem svaki čvor ima nula ili dvoje djece, potpuno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla potpuno ispunjena, osim posljednje razine. Neke posebne podatkovne strukture poput gomila moraju biti cjelovita binarna stabla, dok ne trebaju biti cjelovita binarna stabla. U punom binarnom stablu, ako znate broj ukupnih čvorova ili broj udubljenja ili broj unutarnjih čvorova, druga dva možete pronaći vrlo jednostavno. Ali cjelovito binarno stablo nema posebno svojstvo koje povezuje ova tri atributa.
