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, come ogni altro nodo di un ABR. Oltre al valore, è aggiunto un campo priorità, che è un numero casuale scelto in modo indipendente per ogni nodo.

Definizione[modifica | modifica wikitesto]

Un treap è un albero avente le seguenti proprietà. Ogni nodo ha un valore e un valore . Inoltre:

  1. , se è un figlio sinistro di , allora
  2. , se è un figlio destro di , allora
  3. , se è un figlio di , allora se sono utilizzate, per la priorità, le proprietà di ordinamento dell'heap decrescente, altrimenti, se sono utilizzate le proprietà dell'heap crescente