Primjena binarnih stabala

Question 1

Nabrojite i objasnite svojstva binarnog stabla pretraživanja.

Answer 1

• čvorovi imaju implementirani uređaj <odnosno></odnosno>
• vrijednost lijevog dijeteta je manja od korijena
• vrijednost desnog dijeteta je veća od korijena

Question 2

Nabrojite i objasnite svojstva hrpe.

Answer 2

• na svim razinama osim posljednje i predposljednje svi čvorovi imaju po dvoje djece.
• oznake čvorova su podaci nekog tipa na kojem je definiran totalni uređaj
• oznake se dodaju s lijeva na desno
• dozvoljena je operacija brisanja korijena stabla koje se izvodi na način da nakon brisanja stablo i dalje zadržava obilježja hrpe

Question 3

Koje vrste hrpa postoje te po čemu se iste razlikuju?

Answer 3

Max hrpa - oznake oba djeteta su manje od oznaka njihova roditelja
Min hrpa - oznake oba djeteta su veće od oznaka njihova roditelja

Question 4

Objasnite algoritam sortiranja pomoću hrpe (eng. heap sort).

Answer 4

Idealna implementacija je pomoću polja. U hrpi se stablo uvijek puni tako da se u polju u kojem je stablo zapisano nalaze u prvih n čelija. Nije potrebno pamtiti koji su elementi polja zauzeti.

Question 5

Objasnite složenost algoritma sortiranja pomoću hrpe (eng. heap sort).

Answer 5

Složenost mu je O(n log n), ali je sporiji od QuickSorta i sortiranja spajanjem.