Treap
From Free net encyclopedia
In computer science, a treap is a binary search tree that orders the nodes by adding a priority attribute to a node, as well as a key. The nodes are ordered so that the keys form a binary search tree and the priorities obey the min heap order property.
The treap was discovered by Cecilia R. Aragon and Raimund G. Seidel in 1996.
- If v is a left child of u, then key[v] < key[u];
- If v is a right child of u, then key[v] > key[u];
- If v is a child of u, then priority[v] > priority[u];
During insertion, the value is also assigned a priority. Initially, insertion proceeds in a manner identical to general binary search tree insertion. After this is done, tree rotations are employed to restore the heap property: the in-order traversal sequence is invariant under rotations, so an in-order traversal still yields the same sequence of values.
Treaps exhibit the properties of both binary search trees and heaps.
When the priority is randomly allocated, the structure is known as a randomized binary search tree.
