Treap
|
|
In computer science, a treap is a binary search tree that orders the nodes by adding a random number 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];
- (priority[v] > priority[u] means u was inserted before v)
During insertion, the value is also assigned a random 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.
External links
- Animated treap (http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/Treap-Example.html)Template:Compu-stub