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, ${\displaystyle val(x)}$ come ogni altro nodo di un ABR. Oltre al valore, è aggiunto un campo priorità, ${\displaystyle priority(x)}$ che è un numero casuale scelto in modo indipendente per ogni nodo.

Definizione

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

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

  Portale Informatica

  Portale Matematica