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