A randomized binary search tree (abbreviated RBST, also known as Cartesian tree) 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 according to subtree size, every time a new node is inserted. These priorities are organized in a max heap order.

The expected value of the tree's height is logarithmic in its number of nodes, which ensures good asymptotic running time.

Operations on RBST

Insertions

When a new node is inserted in an 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. Inserting at the root requires the split operation, which splits an RBST into two trees. The new root node links up these two subtrees as its left child and right child.

Deletions

When the RBST node to be deleted is found, its left child and its right child are joined together to form a new RBST. The no longer referenced node is deleted.

RBST versus treaps

A RBST node has a random priority of the range from 0 to the subtree size, while a treap node has a random priority of the machine's word size. RBST supports searches and deletions by rank. No matter what the approach to randomization we use (random priorities or subtree sizes), the probabilistic properties of RBSTs and treaps are equivalent.

References

See also

• Treap

External links

• Definition from NIST