Heap binario: differenze tra le versioni

Versione delle 11:44, 20 giu 2006

Versione delle 17:26, 28 giu 2006

Riga 4:

In ogni nodo è presente una coppia ''(k,x)'' in cui ''k'' è il valore della chiave associata alla entry ''x''. Nei dizionari, a differenza delle mappe, ogni chiave può essere associata a più entry (come in un "reale" dizionario ogni parola ha più significati).</br>

Questi tipi di albero hanno la caratteristica secondo la quale qualsiasi nodo padre ha chiave minore di entrambi (se esistono) i suoi figli.</br>

In questo modo si garantisce che compiendo un qualsiasi percorso che parte da un nodo ''v'' dell'albero e scendendo nella struttura verso le foglie, si attraaversanoattraversano nodi con chiave sempre crescente (in senso lato).

Questa tipologia di alberi nella programmazione viene sovente implementata attraverso l'utilizzo di [[vettore|vettori]], comprendenti un numero ''N'' di celle (con indici da 0 ad N-1): la prima (indice 0) resta vuota, mentre nella posizione i=1 viene memorizzata la radice. Dato quindi un nodo nella posizione ''i'', gli eventuali figli sono nelle celle ''2i'' (sinistro) e ''2i+1'' (destro).</br>