Treap (Cartesian Tree)

A treap combines a binary search tree, ordered by keys, with a heap, ordered by priorities. Each node stores a key, a priority, and links to its children; choosing priorities randomly makes the resulting tree balanced on average, avoiding the degeneration possible in an ordinary search tree. With this randomized structure, search, insertion, and deletion take expected O(log N) time. A key benefit is that distinct keys and priorities determine a unique tree regardless of insertion order.

The core operations are split and merge. Split divides a tree at a key into nodes at or below the key and nodes above it; merge joins ordered trees while preserving both ordering rules. These operations support insertion and deletion, as well as building a treap from sorted keys in O(N) time. The material also describes combining sets of trees, with union taking O(M log(N/M)) for trees of sizes M and N, and notes that subtree sizes enable order-statistic queries such as finding the K-th element or an element’s index. It extends the discussion to implicit treaps, which represent sequences by position rather than explicit keys, and covers implementation techniques for maintaining subtree information and constructing trees efficiently.