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.