A randomized binary search tree
, 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
The expected value of the tree's height is logarithmic in its number of nodes, which ensures good asymptotic running time.
Operations on RBST
When a new node is inserted in an RBST of size
, it must be the root of the new tree with probability
, 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.
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
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.