Randomized binary search tree

From Wikipedia, the free encyclopedia

This article is about the binary search tree. For other uses, see RBST.

A randomized binary search tree (abbreviated RBST) is a type of binary search tree, with data nodes organized as in a normal binary search tree. Each node has also an access priority, namely p(n) which is chosen in a random fashion, every time a new node is inserted. These priorities are organized in a heap order. This is a special case of a treap. The expected value of the tree's height is logarithmic in its number of nodes, which ensures good asymptotic running time.

[edit] External links

• definition from NIST
• Article on RBSTs (pdf)