Treap

Template:S 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. $\mathrm{\forall }x,v\in T$, se $v$ è un figlio sinistro di $x$, allora $val(x)>val(v)$
2. $\mathrm{\forall }x,v\in T$, se $v$ è un figlio destro di $x$, allora $val(x)<val(v)$
3. $\mathrm{\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