Treap

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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