treaps

A treap is a randomized binary search tree that maintains both a binary search tree property on keys and a heap property on priorities. Each node stores a key and a randomly assigned priority; priorities are independent and drawn from a uniform distribution. The tree is organized so that keys in the left subtree are less than the node’s key, keys in the right subtree are greater, and the node’s priority is not smaller than the priorities of its children (a max-heap convention is common).

Insertion begins by performing a standard BST insert based on the key, assigning a random priority to the new node. After insertion, rotations are performed to move the node upward until the heap property holds, potentially altering the structure but preserving the BST ordering. Deletion locates the node by key and moves it down the tree by rotating with its higher-priority child until it becomes a leaf, after which it is removed. Search uses ordinary BST traversal by key.

Treaps offer expected logarithmic time for insertions, deletions, and searches, with an average height of O(log n) due to random priorities. Worst-case time can degrade to O(n), but this is statistically unlikely with good randomization. The space requirement is O(n) for n nodes.

Common applications include maintaining dynamic ordered sets and performing order-statistics or range queries without complex rebalancing rules. Treaps are valued for their simplicity and strong average-case performance, and they provide a practical alternative to other balanced trees in many programming contexts.