Treap

In informatica, il treap è un particolare tipo di albero bilanciato che mette insieme le tipiche caratteristiche di un albero binario di ricerca e quelle di un heap. Ogni nodo dell'albero ha un valore, $val(x)$ come ogni altro nodo di un ABR. Oltre al valore, è aggiunto un campo priorità, $priority(x)$ che è un numero casuale scelto in modo indipendente per ogni nodo.

Definizione

Un treap è un albero $T$ avente le seguenti proprietà. Ogni nodo $x\in T$ ha un valore $val(x)$ e un valore $priority(x)$. Inoltre:

1. $\forall \;x,v\in T$, se $v$ è un figlio sinistro di $x$, allora $val(x)>val(v)$
2. $\forall \;x,v\in T$, se $v$ è un figlio destro di $x$, allora $val(x)<val(v)$
3. $\forall \;x,v\in T$, se $v$ è un figlio di $x$, allora $priority(x)>priority(v)$ se sono utilizzate, per la priorità, le proprietà di ordinamento dell'heap decrescente, altrimenti, $priority(x)<priority(v)$ se sono utilizzate le proprietà dell'heap crescente

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su treap