Treap: Randomized Binary Search Tree
The treap is a randomized binary search tree that achieves balance through probability rather than rigid structural rules. The name combines 'tree' and 'heap'—an apt description since treaps...
Key Insights
- Treaps combine binary search tree ordering with heap priorities, using randomization to achieve expected O(log n) operations without complex rebalancing rules
- The simplicity of treap implementation (just rotations based on priorities) makes them significantly easier to code correctly than AVL or Red-Black trees
- Split and merge operations make treaps exceptionally powerful for range queries and problems requiring implicit indexing
Introduction to Treaps
The treap is a randomized binary search tree that achieves balance through probability rather than rigid structural rules. The name combines “tree” and “heap”—an apt description since treaps simultaneously satisfy both BST and heap properties. Invented by Cecilia Aragon and Raimund Seidel in 1989, treaps offer an elegant alternative to deterministically balanced trees like AVL and Red-Black trees.
The core insight is simple: if you randomly assign priorities to nodes and maintain heap order on those priorities, the resulting tree structure mirrors what you’d get from inserting keys in random order. Random insertion order produces balanced BSTs with high probability, so treaps inherit this property without requiring actual random insertion sequences.
This probabilistic approach yields expected O(log n) time for all operations while keeping implementation complexity remarkably low. Where Red-Black trees require tracking colors and handling multiple rebalancing cases, treaps need only two rotation operations and a random number generator.
The Core Concept: Dual Properties
Every treap node contains a key and a priority. The key follows standard BST ordering: left descendants have smaller keys, right descendants have larger keys. The priority follows max-heap ordering: every node’s priority exceeds its children’s priorities.
Consider a treap with nodes (key, priority): (5, 90), (3, 70), (8, 85), (1, 40), (4, 60). Node 5 sits at the root because it has the highest priority. Node 3 is its left child (smaller key, lower priority), and node 8 is its right child (larger key, lower priority). This dual constraint uniquely determines the tree structure for any set of (key, priority) pairs.
typedef struct TreapNode {
int key;
int priority;
struct TreapNode *left;
struct TreapNode *right;
} TreapNode;
TreapNode* createNode(int key) {
TreapNode *node = malloc(sizeof(TreapNode));
node->key = key;
node->priority = rand(); // Random priority assignment
node->left = NULL;
node->right = NULL;
return node;
}
The random priority assignment is crucial. By drawing priorities uniformly at random, we ensure that any node is equally likely to have the highest priority among its descendants. This produces the same distribution as random BST insertion, giving us expected logarithmic height.
Rotations: The Balancing Mechanism
Rotations are the only structural operations treaps need. A rotation moves a node up or down one level while preserving BST ordering. When a child’s priority exceeds its parent’s priority (violating heap property), we rotate the child upward.
Right rotation promotes a left child to its parent’s position. The parent becomes the right child of its former left child. Left rotation does the mirror operation for right children.
TreapNode* rotateRight(TreapNode *y) {
TreapNode *x = y->left;
TreapNode *T2 = x->right;
x->right = y;
y->left = T2;
return x; // x is new root of this subtree
}
TreapNode* rotateLeft(TreapNode *x) {
TreapNode *y = x->right;
TreapNode *T2 = y->left;
y->left = x;
x->right = T2;
return y; // y is new root of this subtree
}
The beauty of rotations is that they preserve BST ordering automatically. In a right rotation, node x was less than y (it was y’s left child), and after rotation, y is still in x’s right subtree (containing larger values). The subtree T2, originally between x and y in value, moves from x’s right to y’s left—still correctly positioned.
Insertion Operation
Insertion follows a two-phase approach. First, insert the new node as a leaf using standard BST insertion. Second, rotate the node upward until heap property is restored.
The algorithm descends the tree comparing keys to find the correct leaf position. After creating the new node with a random priority, it bubbles up through rotations. If the new node’s priority exceeds its parent’s, rotate it upward. Repeat until the heap property holds throughout the path.
TreapNode* insert(TreapNode *root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
// Fix heap property if violated
if (root->left->priority > root->priority) {
root = rotateRight(root);
}
} else if (key > root->key) {
root->right = insert(root->right, key);
// Fix heap property if violated
if (root->right->priority > root->priority) {
root = rotateLeft(root);
}
}
// Duplicate keys: do nothing (or handle as needed)
return root;
}
The recursive structure handles the bubble-up naturally. After inserting into a subtree, we check if the subtree’s new root (potentially the inserted node after lower rotations) violates heap property with the current node. If so, one rotation fixes it.
Expected time complexity is O(log n). The initial descent takes O(h) where h is tree height. The number of rotations equals the depth at which we inserted minus the final depth—bounded by h. Since expected height is O(log n), both phases complete in expected logarithmic time.
Deletion Operation
Deletion uses the reverse strategy: rotate the target node downward until it becomes a leaf, then simply remove it. To push a node down, we rotate its higher-priority child upward, which pushes our target node into the opposite subtree.
TreapNode* delete(TreapNode *root, int key) {
if (root == NULL) {
return NULL;
}
if (key < root->key) {
root->left = delete(root->left, key);
} else if (key > root->key) {
root->right = delete(root->right, key);
} else {
// Found the node to delete
if (root->left == NULL) {
TreapNode *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreapNode *temp = root->left;
free(root);
return temp;
}
// Node has two children: rotate higher-priority child up
if (root->left->priority > root->right->priority) {
root = rotateRight(root);
root->right = delete(root->right, key);
} else {
root = rotateLeft(root);
root->left = delete(root->left, key);
}
}
return root;
}
When the target node has two children, we compare their priorities. Rotating the higher-priority child upward maintains heap property in that subtree while pushing our target down. We then recursively delete from the subtree where our target landed. Eventually, the target has at most one child and we remove it directly.
This approach maintains both properties throughout deletion. The BST property is preserved by rotations. The heap property is preserved because we always rotate the higher-priority child upward.
Search and Additional Operations
Search works exactly like standard BST search—priorities don’t affect it. Compare the target key with each node’s key and descend left or right accordingly.
TreapNode* search(TreapNode *root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
}
return search(root->right, key);
}
The split operation divides a treap into two treaps: one containing all keys less than a given value, another containing all keys greater or equal. This operation is where treaps truly shine.
void split(TreapNode *root, int key, TreapNode **left, TreapNode **right) {
if (root == NULL) {
*left = NULL;
*right = NULL;
return;
}
if (root->key < key) {
*left = root;
split(root->right, key, &((*left)->right), right);
} else {
*right = root;
split(root->left, key, left, &((*right)->left));
}
}
The merge operation combines two treaps where all keys in the first are less than all keys in the second. We compare root priorities to decide which becomes the merged root, then recursively merge subtrees.
TreapNode* merge(TreapNode *left, TreapNode *right) {
if (left == NULL) return right;
if (right == NULL) return left;
if (left->priority > right->priority) {
left->right = merge(left->right, right);
return left;
} else {
right->left = merge(left, right->left);
return right;
}
}
Split and merge enable powerful operations. Range deletion becomes: split at range start, split again at range end, discard the middle, merge the remaining parts. Insertion can be implemented as split followed by two merges. These operations also enable “implicit treaps” where array indices are derived from subtree sizes rather than stored explicitly—useful for rope data structures and dynamic sequences.
Performance Analysis and Use Cases
Treaps provide expected O(log n) time for insert, delete, and search. The expected height of a treap with n nodes is approximately 2.4 log n. Worst case is O(n) if priorities conspire to create a degenerate tree, but this probability is astronomically small with proper randomization.
Compared to AVL trees, treaps have slightly worse constants (AVL guarantees height ≤ 1.44 log n) but far simpler implementation. Compared to Red-Black trees, treaps are dramatically easier to code correctly—Red-Black insertion has multiple cases and colors to track, while treap insertion is a dozen lines.
Treaps excel in several scenarios:
Competitive programming: The simple implementation reduces bugs under time pressure. Split and merge operations solve range problems elegantly.
Persistent data structures: Treap operations naturally support path copying for persistence. Each modification creates new nodes along one path, leaving old versions intact.
Randomized algorithms: When you need a balanced BST but want to avoid deterministic adversarial inputs, treaps’ randomization provides protection.
Dynamic sequences: Implicit treaps (using subtree sizes as implicit keys) support efficient insertion and deletion at arbitrary positions—something arrays can’t do efficiently.
Choose treaps over Red-Black trees when implementation simplicity matters more than guaranteed worst-case bounds. Choose them over skip lists when you need tree structure for operations like finding k-th element. Avoid them in hard real-time systems where worst-case guarantees are mandatory.
The treap represents a powerful idea: sometimes randomization provides simpler solutions than determinism. By embracing probability, we trade theoretical worst-case guarantees for practical simplicity and excellent expected performance.