平衡树

平衡树

二叉搜索树

性质：一个节点 \(x\) 的左子树的关键字都比 \(x\) 的关键字小，右子树的关键字都比 \(x\) 的关键字大。

这种结构规定了左边都比右边小的关系，所以可以很方便的寻找第 \(k\) 小，或者叫询问小于 \(k\) 的元素个数。

treap

"树堆" : Tree + Heap

给每个节点赋一个随机的权值，使得这棵树同时满足（两个权值分别满足）二叉搜索树和堆的性质。(笛卡尔树

设每个点原始的权值叫 \(key\)， 随机赋的叫 \(rand\)。

让 \(key\) 满足二叉搜索树的同时，让 \(rand\) 也满足堆的性质。

\(key[ls] < key[cur]\)

\(key[rs] > key[cur]\)

\(rand[son] < rand[cur]\) 大根堆。

因为相等的情况我们不想要，所以我们直接在每个key上维护一下这和权值出现的次数即可。

struct node
{
    int lson, rson; // 左右儿子
    int key; // 权值
    int cnt; // 这个key权值的出现次数
    int rand; // 随机堆权值
    int siz; // 子树大小
} t[ MAXN ];
void update(int u)
{
    siz[u] = siz[t[u].lson] + siz[t[u].rson] + t[u].cnt;
}

为什么要赋一个随机值呢？你考虑如果依次插入 1 , 2, 3, 4, 5, 6, 7 ... 这时这棵树就退化成了一条链，操作的复杂度就炸了。（不加入删除的话 你静态二分不就行了。

这些平衡树实际上就是在平衡树的高度，他们会尽量让树高在 \(log\) 左右。

旋转

平衡树通过旋转保持树高，保证复杂度。（改变树形态，同时不破坏二叉搜索树的性质）

平衡树呢就是通过rand也就是通过随机的heap来保证的复杂度。

每次插入的时候呢，要通过旋转来满足heap

删除分几种

1. 叶子直接删
2. 只有一个儿子直接删
3. 有两个儿子要不断旋转变成1/2再删 注意要看ls rs的rand觉得左旋还是右旋 因为你需要保证heap