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