Treap — Randomized BST via Heap Property

class TreapNode {
  int key, priority;
  TreapNode left, right;
  TreapNode(int k) { key = k; priority = random(); }
}

TreapNode insert(TreapNode t, int key) {
  if (t == null) return new TreapNode(key);
  if (key < t.key) {
    t.left = insert(t.left, key);
    if (t.left.priority > t.priority) t = rotateRight(t);
  } else {
    t.right = insert(t.right, key);
    if (t.right.priority > t.priority) t = rotateLeft(t);
  }
  return t;
}