Random BST: Treap

Treap is a data structure which combines binary search tree and binary heap (hence the name: Tree + Heap ⇒ Treap).

  • Each entry (key-value pair) is assigned a random priority.
  • The BST ordering property is based on keys.
  • The priorities are used to create a (min or max) heap.

Insertion

  • Generate random priority for the entry (key-value pair).
  • Insert the entry as you would in BST (based on the "key" and ignoring priorities)
  • If priorities (inserted node and its parent) are not in desired order (based on whether we maintain a max- or min-heap), rotate node up and parent down (instead of swim up).
  • Repeat the last step until all priorities are in desired order.

Deletion

  • Find the entry to be removed following a "look up" in BST (on keys, ignoring priorities).
  • Change the priority of the entry to be removed to a value that results in the entry to sink down. For example, if the priorities are non-negative, set the priority of entry to be removed to $-1$.
  • Rotate down the entry to be removed until it cannot sink down any further (it becomes a leaf), then remove it.

After any sequence of insertions and deletions, the height of the tree is, with high probability, proportional to the logarithm of the number of entries.

Resources