Balanced Binary Search Tree
I. In-Class Exercises
Programming Exercises
(None yet)
II. Knowledge Summary
Key Concept
A regular binary search tree (BST) can degenerate into a linked list in the worst case, causing operations to degrade to O(n). A balanced binary tree maintains tree balance, guaranteeing O(log n) time complexity for all operations.
This lesson introduces the most practical balanced tree for competitive programming -- Treap (Tree + Heap). A Treap assigns each node a random priority, satisfying both the BST property (by key) and the heap property (by priority), using randomization to ensure an expected tree height of O(log n).
Algorithm Principle
Two Implementations of Treap
- Rotational Treap: Maintains heap property through left/right rotations
- Non-rotational Treap (FHQ Treap): Implemented through split/merge operations, with simpler code and more powerful functionality
This lesson focuses on Non-rotational Treap (FHQ Treap), which is more commonly used in competitions.
Core Operations of FHQ Treap
Split (split by value): Splits the tree into two parts -- the left tree contains all values <= k, and the right tree contains all values > k.
Merge: Merges two trees, requiring that all values in the left tree are less than all values in the right tree. The root is determined by comparing priorities.
With split and merge, all BST operations can be easily implemented:
- Insert val: split(root, val-1) -> merge(left, newNode) -> merge(result, right)
- Delete val: split out val, then split out a single node, merge back
- Query rank, kth element, predecessor, successor: use subtree size information after splitting
Code Implementation
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
7
8struct FHQTreap {
9 int ls[MAXN], rs[MAXN]; // left and right children
10 int val[MAXN]; // key value
11 int pri[MAXN]; // random priority
12 int sz[MAXN]; // subtree size
13 int tot = 0; // node count
14 int root = 0; // root node
15
16 int newNode(int v) {
17 int p = ++tot;
18 ls[p] = rs[p] = 0;
19 val[p] = v;
20 pri[p] = rng();
21 sz[p] = 1;
22 return p;
23 }
24
25 void pushUp(int p) {
26 sz[p] = sz[ls[p]] + sz[rs[p]] + 1;
27 }
28
29 // Split by value: val <= k goes to left tree, val > k goes to right tree
30 void split(int p, int k, int &x, int &y) {
31 if (!p) { x = y = 0; return; }
32 if (val[p] <= k) {
33 x = p;
34 split(rs[p], k, rs[p], y);
35 } else {
36 y = p;
37 split(ls[p], k, x, ls[p]);
38 }
39 pushUp(p);
40 }
41
42 // Merge two trees (all values in x < all values in y)
43 int merge(int x, int y) {
44 if (!x || !y) return x | y;
45 if (pri[x] > pri[y]) {
46 rs[x] = merge(rs[x], y);
47 pushUp(x);
48 return x;
49 } else {
50 ls[y] = merge(x, ls[y]);
51 pushUp(y);
52 return y;
53 }
54 }
55
56 // Insert value v
57 void insert(int v) {
58 int x, y;
59 split(root, v, x, y);
60 root = merge(merge(x, newNode(v)), y);
61 }
62
63 // Delete one node with value v
64 void erase(int v) {
65 int x, y, z;
66 split(root, v, x, z);
67 split(x, v - 1, x, y);
68 // y contains all nodes with value v, delete one (remove root)
69 y = merge(ls[y], rs[y]);
70 root = merge(merge(x, y), z);
71 }
72
73 // Query rank of v (number of elements less than v + 1)
74 int getRank(int v) {
75 int x, y;
76 split(root, v - 1, x, y);
77 int rank = sz[x] + 1;
78 root = merge(x, y);
79 return rank;
80 }
81
82 // Query the value with rank k
83 int getKth(int p, int k) {
84 while (true) {
85 int leftSz = sz[ls[p]];
86 if (k <= leftSz) {
87 p = ls[p];
88 } else if (k == leftSz + 1) {
89 return val[p];
90 } else {
91 k -= leftSz + 1;
92 p = rs[p];
93 }
94 }
95 }
96
97 int getKth(int k) {
98 return getKth(root, k);
99 }
100
101 // Query predecessor of v (largest value strictly less than v)
102 int getPrev(int v) {
103 int x, y;
104 split(root, v - 1, x, y);
105 int ans = getKth(x, sz[x]); // maximum in x
106 root = merge(x, y);
107 return ans;
108 }
109
110 // Query successor of v (smallest value strictly greater than v)
111 int getNext(int v) {
112 int x, y;
113 split(root, v, x, y);
114 int ans = getKth(y, 1); // minimum in y
115 root = merge(x, y);
116 return ans;
117 }
118} treap;
119
120int main() {
121 ios::sync_with_stdio(false);
122 cin.tie(nullptr);
123
124 int n;
125 cin >> n;
126
127 while (n--) {
128 int op, x;
129 cin >> op >> x;
130 switch (op) {
131 case 1: treap.insert(x); break;
132 case 2: treap.erase(x); break;
133 case 3: cout << treap.getRank(x) << "\n"; break;
134 case 4: cout << treap.getKth(x) << "\n"; break;
135 case 5: cout << treap.getPrev(x) << "\n"; break;
136 case 6: cout << treap.getNext(x) << "\n"; break;
137 }
138 }
139
140 return 0;
141}Execution Example
Execute the following operations in order:
| Operation | Description | Result |
|---|---|---|
| insert(3) | Insert 3 | Tree: {3} |
| insert(1) | Insert 1 | Tree: {1, 3} |
| insert(5) | Insert 5 | Tree: {1, 3, 5} |
| insert(2) | Insert 2 | Tree: {1, 2, 3, 5} |
| getRank(3) | Rank of 3 | 3 (1 and 2 are before it) |
| getKth(2) | 2nd smallest | 2 |
| getPrev(3) | Predecessor of 3 | 2 |
| getNext(3) | Successor of 3 | 5 |
| erase(3) | Delete 3 | Tree: {1, 2, 5} |
| getRank(4) | Rank of 4 | 3 (1 and 2 are before it) |
Split Process Illustration
Executing split(root, 3) splits the tree by value 3:
1Original tree: After split:
2 3 Left tree(<=3): Right tree(>3):
3 / \ 3 5
4 2 5 /
5 / 2
6 1 /
7 1Merge Process Illustration
When merging the left and right trees, compare the priorities of root nodes:
- If the left root has higher priority, the left root becomes the root, recursively merge the left root's right child with the right tree
- Otherwise the right root becomes the root, recursively merge the left tree with the right root's left child
Detailed Problem-Solving Steps
Overview of FHQ Treap Operations
| Operation | Implementation | Complexity |
|---|---|---|
| Insert | split + merge | O(log n) |
| Delete | two splits + merge | O(log n) |
| Query rank | split + subtree size | O(log n) |
| Query kth element | binary search on tree | O(log n) |
| Predecessor/Successor | split + find min/max | O(log n) |
| Range reversal | split by size + lazy tag | O(log n) |
Why is FHQ Treap Better than Rotational Treap?
- Shorter code: Only two core functions -- split and merge
- More powerful: Naturally supports range operations (persistent, range reversal, etc.)
- No need to understand rotations: Correctness of rotations is harder to grasp
Introduction to AVL Trees
AVL trees maintain balance by keeping each node's balance factor (height difference between left and right subtrees not exceeding 1). When imbalanced, balance is restored through four types of rotations:
- LL rotation (right rotation)
- RR rotation (left rotation)
- LR rotation (left rotation then right rotation)
- RL rotation (right rotation then left rotation)
AVL trees have stricter balance conditions, making queries slightly faster, but require more rotations during insertion and deletion than Treap. In competitions, FHQ Treap is generally preferred.
Common Mistakes
- Poor random number generator quality: Using
rand()may not be random enough;mt19937is recommended. - Forgetting pushUp after split: Split changes the subtree structure; sz must be updated.
- Merge precondition not satisfied: merge(x, y) requires all values in x < all values in y; otherwise the result is incorrect.
- Deleting too many nodes: erase should only delete one node with value v. After splitting out y,
y = merge(ls[y], rs[y])removes only the root node (one node). - Not handling null nodes:
sz[0]must be 0,ls[0] = rs[0] = 0.
Algorithm Evaluation
| Metric | Complexity |
|---|---|
| Insert | Expected O(log n) |
| Delete | Expected O(log n) |
| Query | Expected O(log n) |
| Space | O(n) |
Comparison with STL:
std::set/std::multisetare based on red-black trees, supporting insert, delete, and find, but do not support kth element or rank queries- When rank operations are needed, you must implement a balanced tree manually or use
__gnu_pbds::tree
Competition advice: FHQ Treap is the most recommended balanced tree implementation for competitions -- moderate code length, full-featured, and can be quickly applied once memorized.