Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 31-07-2011, 11:58:17



Title: Dubbi sulle Heap
Post by: Daréios89 on 31-07-2011, 11:58:17
Mi sapreste dimostrare 3 cose?
Perchè se prendo un sottoalbero di dimensione n, e poi considero i sottoalberi radicati nei figli ognuno di essi non può avere dimensione maggiore di 2n/3 ?
Perchè in una heap il numero di nodi massimo ad altezza h è:

(http://latex.codecogs.com/gif.latex?\left%20\lceil%20\frac{n}{2^{h+1}}%20\right%20\rceil) ?

Perchè in una heap si verifica che i nodi interni sono a (http://latex.codecogs.com/gif.latex?\left%20\lfloor%20\frac{n}{2}%20\right%20\rfloor) mentre le foglie a (http://\left \lfloor \frac{n}{2} \right \rfloor+1) ?

Grazie.