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.