Razlika između kompletnog binarnog stabla i potpunog binarnog stabla

Kompletno binarno stablo vs potpuno binarno stablo

Binarno stablo je drvo na 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 su imenovana kao djeca „lijeva i desna“. Dijelovi čvorovi sadrže referencu na svog roditelja. Kompletno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla potpuno ispunjena osim posljednje razine. Na neispunjenoj razini čvorovi su pričvršćeni počevši od najviše lijeve pozicije. Potpuno binarno stablo je drvo u kojem svaki čvor na stablu ima dvoje djece osim lišća stabla.

Što je puno binarno drvo?

Potpuno binarno stablo je binarno stablo u kojem svaki čvor na stablu ima točno nulu 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 lakova (l) i broj unutarnjih čvorova (i) povezani su na poseban način, tako da ako poznajete bilo koji od njih, možete odrediti druga dva vrijednosti su kako slijedi:

1. Ako puno binarno stablo ima unutarnje čvorove:

- Broj lišća l = i + 1

- Ukupan broj čvorova n = 2 * i + 1

2. Ako puno binarno stablo ima n čvorova:

- Broj unutarnjih čvorova i = (n-1) / 2

- Broj lišća l = (n + 1) / 2

3. Ako puno binarno stablo ima l lišće:

- Ukupan broj čvorova n = 2 * l-1

- Broj unutarnjih čvorova i = l-1

Što je cjelovito binarno stablo?

Kao što je prikazano na slici 2, kompletno binarno stablo je binarno stablo u kojem je svaka razina stabla potpuno ispunjena osim posljednje razine. Također, na posljednjoj razini čvorove treba pričvrstiti počevši od položaja s najviše lijeve strane. Kompletno binarno stablo visine h zadovoljava sljedeće uvjete:

- Iz 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 dijete

- Ako su a, b dva čvora na razini iznad posljednje razine, tada a ima više djece nego b ako i samo ako se a nalazi lijevo od b

Koja je razlika između Kompletnog binarnog stabla i Potpunog 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, kompletno binarno stablo je binarno stablo u kojem je svaka razina binarnog stabla potpuno ispunjena osim posljednje razine. Neke posebne strukture podataka poput hrpa trebaju biti cjelovita binarna stabla dok ne moraju biti puna binarna stabla. U punom binarnom stablu, ako znate broj ukupnih čvorova ili broj lakova ili broj unutarnjih čvorova, ostala dva možete vrlo lako pronaći. Ali potpuno binarno stablo nema posebno svojstvo koje se odnosi na teze tri atributa.