Today’s topic: Treaps (or Tree-heap).
What are they? A cross between a binary search trees and heaps. They are binary trees where nodes are “in-order”, meaning that a node k is greater than anything in its left subtree and less than everything in its right subtree.
Furthermore, every node is assigned a priority p(k), such that p(parent(k)) < p(k) (assuming that 1 is the highest priority and smaller number is higher priority), and the root has the highest priority.
At first you might think that a treap might not exist, given a set of keys S, and a priority assignment for S. However, you can simply insert the keys into a new treap T, ordered by their priorities, as you would in a normal binary search tree. If the priorities are all unique, then we get a unique treap:
The highest priority key must be the root, then recursively build the unique treaps for the elements less than k and greater than k and attach them to k as the left and right subtrees, respectively.
How are they like BSTs? insert(x, T), member(x, T), and delete(x, T) all run in expected O(log n) time.
insert(x, T): do a normal insert into T as a leaf as you would for a BST, then randomly generate a priority for x, and percolate it up until the heap property is restored
member(x, T): same as for BST
delete(x, T): look for x as you would for a BST, then once we find it, rotate it down to a leaf by rotating x with its higher priority child, then we trim it off the tree
we must rotate it with the higher priority child so that we don’t mess up the heap property
All that’s left is the analysis. We’ll see that all of it is in expectation. We saw examples of treaps that are highly unbalanced, but if we average over all possible treaps on the same set of keys, the expected depth will be O(log n).