Treap
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
Questa voce sull'argomento programmazione è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
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
Un treap è un albero avente le seguenti proprietà. Ogni nodo ha un valore e un valore . Inoltre:
- , se è un figlio sinistro di , allora
- , se è un figlio destro di , allora
- , 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
Altri progetti
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file su treap
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)