我的算法书 - Treap：带旋转的普通平衡树

一句话算法

Treap = 二叉搜索树的值顺序 + 随机堆的优先级，用旋转同时维护“按值有序”和“按优先级平衡”。

问题模型

维护一个可重复元素集合，支持下面六类操作：

插入一个数；
删除一个数；
查询某个数的排名；
查询排名为 $k$ 的数；
查询某个数的前驱；
查询某个数的后继。

如果只用普通二叉搜索树，数据接近有序时树会退化成链，单次操作可能变成 $O(n)$ 。Treap 给每个节点额外分配一个随机优先级，让树形状近似随机，从而把期望高度控制在 $O(\log n)$ 。

核心直觉

Treap 同时满足两个规则：

值满足 BST 规则：左子树的值更小，右子树的值更大。
优先级满足堆规则：父节点的优先级小于子节点的优先级。

插入时，先像普通 BST 一样按值插到底。新节点可能破坏堆规则，于是把它往上旋转，直到堆规则恢复。

插入时的旋转过程：

Open in Excalidraw

删除时，如果节点有两个孩子，就把优先级更小的孩子旋上来，让目标节点往下沉；沉到只有一个孩子或没有孩子时，就可以直接删除。

删除时让目标节点下沉：

Open in Excalidraw

旋转只改变局部父子关系，不改变中序遍历顺序：

Open in Excalidraw

“为什么随机能平衡”

如果优先级是随机的，那么 Treap 的形状等价于“按随机顺序插入 BST”得到的形状。随机顺序不容易长期偏向一侧，所以树高的期望是 $O(\log n)$ 。

节点信息

每个节点维护：

value：节点的值；
priority：随机优先级；
count：这个值出现了几次；
size：子树中元素总个数，包含重复元素；
child[0]、child[1]：左右孩子。

size 是排名和第 $k$ 小查询的关键：

size(u)=size(left(u))+size(right(u))+count(u)

算法步骤

插入

按 BST 规则找到插入位置。
如果值已经存在，只增加 count。
否则新建节点，并赋予随机 priority。
回溯时，如果孩子的 priority 比当前节点小，就旋转孩子上来。
每次结构变化后 pushup 更新 size。

删除

按 BST 规则找到目标值。
如果 count > 1，只减少 count。
如果只有一个孩子，直接用孩子替代当前节点。
如果有两个孩子，把 priority 更小的孩子旋转上来。
目标节点被旋到下一层后继续删除。

查询排名

从根向下走：

如果 value <= 当前值，答案在左边；
如果 value > 当前值，左子树和当前节点的所有重复值都比它小，排名加上 left_size + count，再去右边。

排名从 1 开始。

查询第 k 小

设当前节点左子树大小为 left_size：

k <= left_size：去左子树；
left_size < k <= left_size + count：当前值就是答案；
否则去右子树，并令 k -= left_size + count。

算法证明

核心不变量：任何时刻，Treap 都同时满足 BST 顺序和堆优先级。

插入保持 BST 顺序

新节点先按值插入普通 BST 的叶子位置，所以插入后 BST 顺序成立。
旋转不破坏 BST 顺序

旋转只是局部改变三段区间的位置。以右孩子上旋为例：

$A < u < B < v < C$
旋转后中序遍历仍然是：

$A,\ u,\ B,\ v,\ C$
所以值的顺序不变。
旋转恢复堆规则

如果孩子优先级更小，就把孩子旋到父亲位置。这个操作修复当前父子之间的堆规则。继续向上检查，最终路径上的堆规则全部恢复。
删除正确

删除有两个孩子的节点时，不能直接拼接左右子树。先把优先级更小的孩子旋上来，可以保持堆规则；目标节点下降一层，问题规模变小。重复这个过程，目标节点最终变成至多一个孩子的情况，可以直接删除。

因此所有操作都保持 Treap 的两个不变量，查询依赖的 size 由 pushup 正确维护，所以算法正确。

复杂度分析

设当前集合大小为 $n$ 。

插入、删除、排名、第 $k$ 小、前驱、后继的期望时间复杂度都是 $O(\log n)$ 。
空间复杂度是 $O(n)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

        #include <bits/stdc++.h>
using namespace std;

struct Treap {
    struct Node {
        int child[2] = {0, 0};
        int value = 0;
        int priority = 0;
        int count = 0;
        int size = 0;
    };

    vector<Node> tree;
    int root = 0;
    mt19937 rng;

    Treap(int max_nodes = 0) : rng(712367821) {
        tree.reserve(max_nodes + 1);
        tree.push_back(Node()); // node 0 is the null sentinel.
    }

    int new_node(int value) {
        tree.push_back(Node());
        int id = (int)tree.size() - 1;
        tree[id].value = value;
        tree[id].priority = (int)rng();
        tree[id].count = 1;
        tree[id].size = 1;
        return id;
    }

    int node_size(int u) const {
        return u == 0 ? 0 : tree[u].size;
    }

    void pushup(int u) {
        tree[u].size = node_size(tree[u].child[0]) +
                       node_size(tree[u].child[1]) +
                       tree[u].count;
    }

    // direction=0: lift left child by right rotation.
    // direction=1: lift right child by left rotation.
    void rotate(int &u, int direction) {
        int v = tree[u].child[direction];
        tree[u].child[direction] = tree[v].child[direction ^ 1];
        tree[v].child[direction ^ 1] = u;
        pushup(u);
        pushup(v);
        u = v;
    }

    void insert(int &u, int value) {
        if (u == 0) {
            u = new_node(value);
            return;
        }
        if (tree[u].value == value) {
            tree[u].count++;
            pushup(u);
            return;
        }

        int direction = value > tree[u].value;
        insert(tree[u].child[direction], value);
        if (tree[tree[u].child[direction]].priority < tree[u].priority) {
            rotate(u, direction);
        }
        pushup(u);
    }

    void insert(int value) {
        insert(root, value);
    }

    void erase(int &u, int value) {
        if (u == 0) return;

        if (tree[u].value == value) {
            if (tree[u].count > 1) {
                tree[u].count--;
                pushup(u);
                return;
            }

            int left = tree[u].child[0];
            int right = tree[u].child[1];
            if (left == 0 || right == 0) {
                u = left + right;
                return;
            }

            int direction = tree[left].priority < tree[right].priority ? 0 : 1;
            rotate(u, direction);
            erase(tree[u].child[direction ^ 1], value);
            pushup(u);
            return;
        }

        int direction = value > tree[u].value;
        erase(tree[u].child[direction], value);
        pushup(u);
    }

    void erase(int value) {
        erase(root, value);
    }

    // Rank is 1-based: the smallest value has rank 1.
    int rank_of(int value) const {
        int u = root;
        int rank = 1;
        while (u != 0) {
            if (value <= tree[u].value) {
                u = tree[u].child[0];
            } else {
                rank += node_size(tree[u].child[0]) + tree[u].count;
                u = tree[u].child[1];
            }
        }
        return rank;
    }

    int kth(int k) const {
        int u = root;
        while (u != 0) {
            int left_size = node_size(tree[u].child[0]);
            if (k <= left_size) {
                u = tree[u].child[0];
            } else if (k <= left_size + tree[u].count) {
                return tree[u].value;
            } else {
                k -= left_size + tree[u].count;
                u = tree[u].child[1];
            }
        }
        return -1;
    }

    int predecessor(int value) const {
        int u = root;
        int answer = INT_MIN;
        while (u != 0) {
            if (tree[u].value < value) {
                answer = tree[u].value;
                u = tree[u].child[1];
            } else {
                u = tree[u].child[0];
            }
        }
        return answer;
    }

    int successor(int value) const {
        int u = root;
        int answer = INT_MAX;
        while (u != 0) {
            if (tree[u].value > value) {
                answer = tree[u].value;
                u = tree[u].child[0];
            } else {
                u = tree[u].child[1];
            }
        }
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;

    Treap treap(m + 5);
    while (m--) {
        int operation, x;
        cin >> operation >> x;

        if (operation == 1) treap.insert(x);
        if (operation == 2) treap.erase(x);
        if (operation == 3) cout << treap.rank_of(x) << '\n';
        if (operation == 4) cout << treap.kth(x) << '\n';
        if (operation == 5) cout << treap.predecessor(x) << '\n';
        if (operation == 6) cout << treap.successor(x) << '\n';
    }

    return 0;
}

测试用例

输入：

输出：

解释：

插入后集合为 {3,5,5,7}；
5 的排名是 2；
第 3 小是 5；
5 的前驱是 3，后继是 7；
删除一个 5 后，7 的排名是 3。

应用分类详解

Treap 的本质是维护一个动态有序集合。只要题目既有“动态修改”，又有“按大小顺序查询”，就应该考虑平衡树。

一、普通平衡树操作

典型模式： 插入、删除、排名、第 $k$ 小、前驱、后继混合出现。

识别信号： 题面直接要求动态排名、动态第 $k$ 小或动态前驱后继。

核心建模： 把所有数放入 Treap，用 size 维护排名信息。

应用场景	经典题目	核心思路
普通平衡树模板	luogu-P3369	Treap 六个基本操作
文艺平衡树以外的动态集合	luogu-P6136	动态维护排名和前驱后继

二、动态中位数和第 k 小

典型模式： 数据不断变化，每次询问当前第 $k$ 小或中位数。

识别信号： 出现“插入/删除后查询中位数”“当前集合第 k 小”。

核心建模： 中位数就是第 $(size+1)/2$ 小，用 kth 查询。

应用场景	经典题目	核心思路
动态中位数	动态数据流类题目	插入后查询固定排名
动态排名统计	luogu-P3369	用子树大小定位排名

三、需要批量拆分合并的序列问题

典型模式： 题目要按区间切开、翻转、移动、拼接。

识别信号： 出现“区间翻转”“区间移动”“把一段拿出来再放回去”。

核心建模： 这类问题更适合 FHQ Treap 或 Splay。旋转 Treap适合动态有序集合；如果主要操作是 split/merge，应转到本书 FHQ Treap 章节。

应用场景	经典题目	核心思路
区间翻转	luogu-P3391	使用按排名分裂的 FHQ Treap
区间移动	Codeforces 863D	分裂出区间后重新合并

经典例题

1. luogu-P3369

普通平衡树模板题。完整练习 Treap 的插入、删除、排名、第 $k$ 小、前驱、后继。

2. luogu-P6136

普通平衡树数据加强版。重点是保证每个操作都是 $O(\log n)$ 期望复杂度。

3. luogu-P3391

文艺平衡树。它不是旋转 Treap 的典型用法，而是提醒读者：当题目核心是序列区间操作时，应使用 FHQ Treap 或 Splay。

参考

旧版草稿：Rbook_ejs_old/book/data_structure/treap/index.md
本书相关章节：data_structure/fhq-treap