randomized binary search tree

(data structure)

Definition: A binary search tree in which nodes have a randomly assigned priority. Updates keep priorities in heap order instead of keeping balance information and doing rebalance operations.

Also known as cartesian tree, RBST.

Generalization (I am a kind of ...)
treap.

See also randomized search tree.

Note: Also called a treap, but strictly a treap does not define how priorities are assigned.

Because of the random priority, the trees are always expected to be nearly balanced, regardless of the number, kind and order of updates made. The expected worst case is O(log n) for any update or search in a RBST of size n.

Author: CM

Implementation

Oleg Kiselyov's treap implementation (Scheme) and verification code and other links.

More information

Conrado Martinez and Salvador Roura, Randomized Binary Search Trees, Journal of the ACM, 45(2):288-323, March 1998.

Jean Vuillemin, A Unifying Look at Data Structures, CACM, 23(4):229-239, April 1980.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 7 September 2010.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Conrado Martinez, "randomized binary search tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 September 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/randomizedBinarySearchTree.html