Randomized Binary Search Trees

A treap is a binary search tree in which each node has both a key and a priority: nodes are ordered in an inorder fashion by their keys (as in a standard binary search tree) and are heap-ordered by their priorities (so that the each parent has a higher priority than its children).

To implement randomized binary search trees, random priorities are assigned to each node when an insertion is performed. Insertion uses the standard algorithm for inserting the new node as a leaf, and then restores heap ordering by "bubbling up" the node through a sequence of rotations. Deletion reverses this procedure by first "bubbling down" the node until it is a leaf, and then pruning it off the tree. One can show that the expected depth of any node in this tree is about ln n, and the expected number of rotations per insertion or deletion is about 2.

The following demo starts with a sequence of 12 insertions in a "worst case" (increasing) order. Priorities are entirely random.

The Source.