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. [1] The nodes are ordered so that the keys form a binary search tree and the priorities obey the max heap order property. The name treap is a composition of tree and heap.
Contents |
Definitions
The treap was invented by Cecilia R. Aragon and Raimund G. Seidel in 1989, [2] though the authors credit Jean Vuillemin with studying essentially the same data structure in 1980.
- If v is a left descendant of u, then key[v] < key[u];
- If v is a right descendant 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. (This priority may be random, in which case the use of a pseudorandom number generator is applicable.) 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. If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case behavior may be outweighed by better expected-case behavior, as the most important items will be near the root. Treaps exhibit the properties of both binary search trees and heaps.
Related data structures
When the priority is randomly allocated according to subtree size, the structure is known as a randomized binary search tree or RBST.
References
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001), Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, ISBN 0-262-03293-7
- ^ Seidel, Raimund & Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica 16 (4/5): pp. 464-497, <http://citeseer.ist.psu.edu/seidel96randomized.html>
