Treap

From Wikipedia, the free encyclopedia

In computer science, a treap is a binary search tree that orders the nodes by adding a random 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.

A treap with alphabetic key and numeric max heap order
A treap with alphabetic key and numeric max heap order

Contents

[edit] Definitions

The treap was invented by Cecilia R. Aragon and Raimund G. Seidel in 1989,[2][3] though the authors credit Jean Vuillemin with studying essentially the same data structure in 1980.[2]

  • 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.

[edit] 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.

[edit] References

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001), Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, pp. 296-300, ISBN 0-262-03293-7 
  2. ^ a b Aragon, Cecilia R. & Seidel, Raimund (1989), “Randomized Search Trees”, Foundations of Computer Science, 30th Annual Symposium on: 540-545, ISBN 0-8186-1982-1, DOI 10.1109/SFCS.1989.63531 
  3. ^ Seidel, Raimund & Aragon, Cecilia R. (1996), “Randomized Search Trees”, Algorithmica 16 (4/5): pp. 464-497, doi:10.1007/s004539900061, <http://citeseer.ist.psu.edu/seidel96randomized.html> 

[edit] External links