Randomized binary search tree
From Wikipedia, the free encyclopedia
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.
Alternatively, the randomization can be done using information on the size of the subtree rooted at each node. For instance, when a new node is inserted in a RBST of size n, it must be the root of the new tree with probability 1 / (n + 1), and with complementary probability it must be inserted into the appropriate subtree of the root. No matter what the approach to randomization we use (random priorities or subtree sizes), the probabilistic properties of RBSTs are equivalent.
