全称“平衡二叉搜索树”，常见的类型有：

1. splay
2. treap
3. AVL Treap
4. Red Black Tree
5. Scape Goat Tree
6. Weight Blanced Leafy Tree (特殊结构)

性质：一个节点 $x$ 左子树所有点的关键字都比 $x$ 的关键字小，右子树所有点的关键字都比 $x$ 的关键字大

如果我们有了这样一棵树，那么我们可以很高效地去寻找第 $k$ 小或 $< k$ 的元素个数，做这两种任务时会比较简单

很多其他的功能可以用 std::set 来代替，std::set 也是平衡二叉搜索树，但 std::set 的话，只有求前驱和后继的功能是比较重要的，比如求小于 $k$ 的最大元素以及大于 $k$ 的最小元素

treap

“树堆” “Tree + Heap”
性质：每个点随机分配一个权值，使 $\operatorname{treap}$ 同时满足堆性质和二叉搜索树性质
复杂度：$\mathcal{O}(\log n)$

设每个节点的关键字是 $\operatorname{key}$，随机权值是 $\operatorname{rand}$

1. 如果 $v$ 是 $u$ 的左儿子，则 $\operatorname{key}[v] < \operatorname{key}[u]$
2. 如果 $v$ 是 $u$ 的右儿子，则 $\operatorname{key}[v] > \operatorname{key}[u]$
3. 如果 $v$ 是 $u$ 的子节点，则 $\operatorname{rand}[u] > \operatorname{rand}[v]$

$\operatorname{Treap}$ 维护权值的时候一般会把相同的权值放在同一个节点上
所以一个 $\operatorname{treap}$ 节点需要维护以下信息：

• 左右儿子
• 关键字
• 关键字出现次数
• 堆随机值
• 节点大小（即子树大小）

struct Node {
    int l, r; // 表示左右儿子的编号
    int key; // 节点的关键字
    int cnt; // 这个关键字出现的次数
    int rd; // treap 这个节点的随机堆权值 
} t[MAXN];

之所以要这个堆随机值，是为了达到平衡

旋转

• 平衡树主要通过旋转来保持树的平衡，即保证复杂度

• 旋转有单旋和双旋，treap 只需要单旋，这一点比较简单

// 右旋
void rturn(int &o) {
    int t = tr[o].l;
    tr[o].l = tr[t].r;
    tr[t].r = o;
    tr[t].size = tr[o].size();
    update(o);
    o = t;
}   

// 左旋
void lturn(int &o) {
    int t = tr[o].r;
    tr[o].r = tr[t].l;
    tr[t].l = o;
    tr[t].size = tr[o].size();
    update(o);
    o = t;
}  

插入

• 先给这个节点分配一个随机的堆权值
• 然后把这个节点按照 bst 的规则插入到一个叶子上
• 从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子
• 然后通过旋转来调整，使得treap满足堆性质