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 ...)
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.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 7 September 2010.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Conrado Martinez, "randomized binary search tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 7 September 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/randomizedBinarySearchTree.html