二叉搜索树 & 平衡树

定义

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

1. 空树是二叉搜索树。

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

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

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

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 个结点的二叉搜索树中，这些操作的最优时间复杂度为 ，最坏为 。随机构造这样一棵二叉搜索树的期望高度为 。

过程

在接下来的代码块中，我们约定 为结点个数， 为高度，val[x] 为结点 处存的数值，cnt[x] 为结点 存的值所出现的次数，lc[x] 和 rc[x] 分别为结点 的左子结点和右子结点，siz[x] 为结点的子树大小。

遍历二叉搜索树

由二叉搜索树的递归定义可得，二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为 。

遍历一棵二叉搜索树的代码如下：

查找最小/最大值

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

findmin 和 findmax 函数分别返回最小值和最大值所对应的结点编号 ，用 val[o] 可以获得相应的最小/最大值。

插入一个元素

定义 insert(o,v) 为在以 为根节点的二叉搜索树中插入一个值为 的新节点。

分类讨论如下：

若 为空，直接返回一个值为 的新节点。

若 的权值等于 ，该节点的附加域该值出现的次数自增 。

若 的权值大于 ，在 的左子树中插入权值为 的节点。

若 的权值小于 ，在 的右子树中插入权值为 的节点。

时间复杂度为 。

删除一个元素

定义 del(o,v) 为在以 为根节点的二叉搜索树中删除一个值为 的节点。

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

若该节点的附加 大于 ，只需要减少 。

若该节点的附加 为 ：

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

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

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

时间复杂度 。

求元素的排名

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

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

时间复杂度 。

查找排名为 k 的元素

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

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

若其左子树的大小在区间 ( 为当前结点的值的出现次数）中，则该元素为子树的根节点；

若其左子树的大小小于 ，则该元素在右子树中。

时间复杂度 。

平衡树简介

使用二叉搜索树的目的之一是缩短插入与查找时间，一棵合理的二叉搜索树插入与查找时间可以缩短到 。

对于一般的二叉搜索树，有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，插入与查找时间都是 ，可以说是极大的时间浪费，所以研究平衡二叉搜索树是非常有必要的。

关于查找效率分析，如果树的高度为 ，则在最坏的情况，查找一个关键字需要对比 次，查找时间复杂度（也为平均查找长度 ASL，Average Search Length）不超过 。

二叉搜索树的「平衡」概念是指：每一个结点的左子树和右子树高度差最多为 。

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

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

对于拥有同样元素值集合的二叉搜索树，平衡状态可能是不唯一的。也就是说，可能两棵不同的二叉搜索树，含有的元素值集合相同，并且都是平衡的。

过程

保证中序遍历序列不变的平衡调整，基本操作为 右旋（rotate right 或者 zig） 和 左旋（rotate left 或者 zag）。这两种操作均不改变中序遍历序列。

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

右旋操作只改变了三组结点关联，相当于对三组边进行循环置换一下，因此需要暂存一个结点再进行轮换更新。

对于右旋操作一般的更新顺序是：暂存 结点，先让 的左孩子指向 的右子树 ，再让 的右孩子指针指向 （ 被它的父结点指向），最后让 的父结点指向暂存的 。整个操作只要找到 的父节点孩子即可完成。

完全同理，有对应的左旋操作，也称为「左单旋转」或「RR 平衡旋转」。左旋操作与右旋操作互为镜像。

一段可行的代码为：

对于这段示例代码，只有调用者知道结点 的父结点是什么。对于这种情形，代码的返回值为新的子树根结点的下标，令调用者将左边为 的父节点赋值为指向新的子树根结点的下标即可。

对于拥有同样元素值集合的全体合法的二叉搜索树，可以证明，在任意两棵树之间均可通过若干右旋和左旋操作，完成从一棵树到另一棵树的变换。因此，借助右旋和左旋操作，可以将任意一棵合法的二叉搜索树调整至平衡状态。