Treap
Vai alla navigazione
Vai alla ricerca
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:
- , 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
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file su treap