Treap = Tree + Heap. Each node stores a key (BST ordering) and a random priority (max-heap ordering).
BST on keys: left keys < node < right keys.
Max-heap on priorities: parent priority ≥ child priorities.
Expected height: O(log n) — random priorities keep the tree balanced regardless of insertion order.
Insert: BST insert at leaf, then rotate upward to fix heap violations.
Delete: Rotate node downward until it becomes a leaf, then remove.
Split/Merge: O(log n) operations that divide or combine treaps — the foundation for implicit treaps used in competitive programming.