平衡树——Treap

BST

定义

1. 空树是二叉搜索树。

2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

4. 二叉搜索树的左右子树均为二叉搜索树。

性质

二叉搜索树的中序遍历是一个有序序列

操作

插入insert(o, v)

1. 若 $o$ 为空，直接返回一个值为 $v$ 的新节点。

2. 若 $o$ 的权值等于 $v$，该节点的附加域该值出现的次数自增 $1$。

3. 若 $o$ 的权值大于 $v$，在 $o$ 的左子树中插入权值为 $v$ 的节点。

4. 若 $o$ 的权值小于 $v$，在 $o$ 的右子树中插入权值为 $v$ 的节点。

删除del(o, v)

先在二叉搜索树中找到权值为 v 的节点，分类讨论如下：

1. 若该节点的附加 $\text{cnt}$ 大于 $1$，只需要减少 $\text{cnt}$。

2. 若该节点的附加 $\text{cnt}$ 为 $1$：

   • 若 $o$ 为叶子节点，直接删除该节点即可。

   • 若 $o$ 为链节点，即只有一个儿子的节点，返回这个儿子。

   • 若 $o$ 有两个非空子节点，一般是用它左子树的最大值或右子树的最小值代替它，然后将它删除。

找前驱 / 后继get_prev(o)、get_next(o)

前（后）驱表示中序遍历中前（后）一个位置，以前驱为例

1. 存在左子树，则找到左子树中最右边的元素，并返回。
2. 不存在左子树，找第一个祖先节点中节点$o$位于其右子树中，返回这个祖先节点

查找最大 / 最小值get_min(o)、get_max(o)

由二叉搜索树的性质可得，二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。

求元素排名get_rank(o)

排名定义为将数组元素排序后第一个相同元素之前的数的个数加一

查找一个元素的排名，首先从根节点跳到这个元素，若向右跳，答案加上左儿子节点个数加当前节点重复的数个数，最后答案加上终点的左儿子子树大小加一。

查找排名为$k$的元素get_value_by_rank

在一棵子树中，根节点的排名取决于其左子树的大小。

若其左子树的大小大于等于 $k$，则该元素在左子树中；

若其左子树的大小在区间 $[k-\text{cnt},k-1]$（$\text{cnt}$ 为当前结点的值的出现次数）中，则该元素为子树的根节点；

若其左子树的大小小于 $k-\text{cnt}$，则该元素在右子树中。

平衡树

对于一般的二叉搜索树，有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，插入与查找时间都是 $O(n)$
二叉搜索树的「平衡」概念是指：每一个结点的左子树和右子树高度差最多为 1。

可以对不满足平衡条件的二叉搜索树进行调整，使不平衡的二叉搜索树变得平衡。

调整要保证的标准还有二叉搜索树先天自带的条件：二叉搜索树，按照中序遍历，得到从小到大的结点值序列。对于任意一个结点，左子树各结点的最大值，小于该结点的值；该结点的值，小于右子树各结点的最小值。只有保证这一点才能称为一个二叉搜索树。

左旋、右旋zag(o)、zig(o)

左旋

左旋，左旋也称为「左单旋转」或「RR 平衡旋转」。对于结点 $A$ 的左旋操作是指：将 $A$ 的右孩子 $B$ 向左上旋转，代替 $A$ 成为根节点，将 $A$ 结点向左下旋转成为 $B$ 的左子树的根结点，$B$ 的原来的左子树变为 $A$ 的右子树。

右旋

右旋，右旋也称为「右单旋转」或「LL 平衡旋转」。对于结点 $A$ 的右旋操作是指：将 $A$ 的左孩子 $B$ 向右上旋转，代替 $A$ 成为根节点，将 $A$ 结点向右下旋转成为 $B$ 的右子树的根结点，$B$ 的原来的右子树变为 $A$ 的左子树。