Data Structure 07 - AVL Tree
# 前置知识
在阅读本文档前,请确保你已经知晓平衡树的基本概念,详见 Data Structure 知识板块中的 06 - Self-Balancing Binary Search Tree 文档。
# 基本概念
AVL树 (AVL Tree) 是最先被发明的平衡树,它是由它的发明者——两位苏联科学家 Georgy Adelson-Velsky 和 Evgenii Landis 的名字来命名的。
为便于描述,设 表示树上节点总数,设 表示节点 的左右子节点,设 表示以 为根节点的子树,设 表示树 的高度。特别地,若 是空树,则 。
AVL树中的每个节点 都有一个 平衡因子 (balance factor) ,定义平衡因子为 ,即节点 的左右子树的高度之差。 为负表示左子树较高,为正表示右子树较高。
AVL树要求保证,对于树上的任意一个节点 ,其平衡因子满足 ,由此可以保证树高最大为 左右。绝大多数的教程都没有说清楚这个数据是怎么来的,本文在后文中给出了详细的推导过程,可供有兴趣的同学参考。
如下图所示, 是满足平衡条件的AVL树,而 不是。图中每个节点 的黑色数值表示 处存储的元素值,红色上标为 ,蓝色下标为 。另外,在 中的不平衡的节点被标记为紫色。
当节点 的平衡因子 不满足上述约束条件的时候,即 时,我们称以 为根节点的子树 是不平衡的。此时,我们需要不断进行旋转操作,直到整棵树是平衡的为止。
# AVL旋转
# 失衡与AVL旋转
除了为了维持平衡性而加入的旋转操作以外,AVL树的基本操作的实现与朴素的二叉查找树完全一致,因此不再赘述其基本原理,只考虑失衡是如何发生的、以及恢复是如何进行的。
对于所有非修改操作,包括查询和遍历操作,显然不会改变AVL树中任何节点的平衡因子,因此无需进行任何额外操作。
对于插入和删除操作,二者均可能会破坏若干个节点的平衡性,所以AVL树在此类操作之后必须进行检查,如果平衡性被破坏,则通过若干次旋转来改变树的结构,在保持二叉查找树的性质的情况下恢复平衡性。
你可能会觉得,子树不平衡有非常多的可能性,事实上,因为在每次插入和删除后都会立即将树恢复平衡,所以实际上需要考虑的情况很少,且必有 。
设 为失衡节点,即 ,设 是 的左右子树中高度值较大的那棵子树的根节点。下图中给出了其中一些例子。记住,节点 和 是我们关注的重点。
需要明白的是,以 为根节点的子树一定是平衡的,只有 处存在不平衡,否则 将会使得 ,这种情况显然是不应该发生的,因为每次插入或删除操作至多会令节点的平衡因子发生大小为 的变化,而在 时我们就会将其恢复至 ,这保证了 只会由 变成 ,而不会变成其他任何值。
此外,平衡因子的计算涉及左右子树的高度,如果我们每次都当场计算这些高度值,会导致时间复杂度劣化成 ,而这些计算中显然是存在冗余的。
为了避免无用的重复计算,我们在每个节点的结构上,存储以该节点为根节点的子树的高度值,然后在插入或删除后更新高度值即可。具体更新方式详见下文中的代码实现。
// 定义
class Node {
public:
int value;
Node * left;
Node * right;
int height; // 追加定义
public:
// ...
};
可能出现的不平衡的子树有四类,包括右右失衡、左左失衡、右左失衡、左右失衡。这里先只列举出来,无需担心,后面会给出详细解释。
对这四类失衡情况,我们执行四类不同的 AVL旋转 (AVL rotations) 操作,包括左旋、右旋、右左旋、左右旋,其中前两者统称为单旋、后两者统称为双旋。这里先只列举出来,无需担心,后面会给出详细解释。
执行AVL旋转的过程有时也被称为 再平衡 (rebalance, or maintain) 过程。
AVL旋转对初学者来说较为复杂难懂,祝你好运。
记住,旋转只是一种被发明出来解决问题的手段,你无需去纠结这个天才的想法是怎么来的,你只需要知道他确实能恢复节点的平衡性,记住这个神一般的操作即可。
# 单旋
单旋 (single rotation) 包括左旋和右旋,分别用于处理右右失衡和左左失衡。单旋操作会逆转 和 之间的父子关系。
右右失衡: 是 的右子树, 且 。当发生右右失衡时,需要执行 左旋 (Left Rotation, or L-Rotation) 操作。
左左失衡: 是 的左子树, 且 。当发生左左失衡时,需要执行 右旋 (Right Rotation, or R-rotation) 操作。
左旋和右旋对应的失衡情况是类似的,只是失衡的方向不同。所以我们接下来将会详细介绍左旋,而不再介绍右旋。
右右失衡的两种最简情况如图所示,注意观察 和 的状态以及二者之间的关系。发生右右失衡的子树上最少有 个节点。
右右失衡的两种情况如图所示。在最简情况1中子树 和 为空树,在最简情况2中子树 为空树。
右右失衡的两种最简情况及其左旋操作如图所示。你可以把左旋想象成把 以 为轴逆时针(向左)旋转。当然,在代码实现时,我们并不会真的去“旋转”它,其本质不过是各个指针的指向的变化,你可以回忆一下链表的插入和删除。
右右失衡的两种情况及其左旋操作如图所示。
左旋操作的具体实现可以用如下步骤解决:
获取节点 ,即
Z = X->right
。将 的右子节点指针指向 ,即
X->right = Z->left
。将 的左子节点指针指向 ,即
Z->left = X
。
左旋操作的代码实现如下,其返回值为该子树的新的根节点。
// 左旋
Node * rotation_L(Node * X) {
// 旋转
Node * Z = X->right;
X->right = Z->left;
Z->left = X;
// 更新子树高度
update_height(X);
update_height(Z);
// 返回
return Z;
}
其中 函数用于更新当前子树高度。各类旋转之后都需要更新高度值,因而将其抽出作为函数使用。注意必须先更新 的高度再更新 的高度,因为旋转之后 是 的子节点, 的高度依赖于 的高度,所以必须先计算后者。
void update_height(Node * p) {
p->height = max(get_height(p->left), get_height(p->right)) + 1;
}
其中 函数用于获取子树高度,使用该函数是为了简洁地处理空指针,否则你就需要频繁地写下判断指针是否为空的代码,太过冗余。
// 获取子树高度
int get_height(Node * p) {
return (p == nullptr ? 0 : p->height);
}
左左失衡和右旋操作就是右右失衡和左旋操作的镜像,原理相同,因而不再赘述,只给出代码实现。
右旋操作的代码实现如下,其返回值为该子树的新的根节点。
// 右旋
Node * rotation_R(Node * X) {
// 旋转
Node * Z = X->left;
X->left = Z->right;
Z->right = X;
// 更新子树高度
update_height(X);
update_height(Z);
// 返回
return Z;
}
# 双旋
双旋 (double rotation) 包括右左旋和左右旋,分别用于处理右左失衡和左右失衡。双旋可以被认为是用来处理单旋无法恢复平衡的情况的。
右左失衡: 是 的右子树, 且 。当发生右左失衡时,需要执行 右左旋 (Right-Left Rotation, or RL-Rotation) 操作。
左右失衡: 是 的左子树, 且 。当发生左右失衡时,需要执行 左右旋 (Left-Right Rotation, or LR-Rotation) 操作。
右左旋和左右旋对应的失衡情况是类似的,只是失衡的方向不同。所以我们接下来将会详细介绍右左旋,而不再介绍左右旋。
如图所示,在右左失衡的情况下,对 执行左旋操作是没有用处的,这只会让 从右左失衡转化为左右失衡而已,因此才引入了双旋的方法。
双旋的方法非常巧妙。仔细思考,如果我们在对 执行左旋操作之前,先对 执行右旋操作,就可以将右左失衡转化为右右失衡!此时再对 执行左旋操作,就一定可以使之恢复平衡。
所以不要把双旋想得太复杂,如果你已经较为透彻地理解了单旋,那么双旋将会变得很容易理解,它只不过是对两个不同的节点接连执行单旋而已。
因为需要对 执行右旋,所以我们再另外标记出 的左右子树中高度值较大的那棵子树(在右左失衡中即为左子树)的根节点 。
如图所示,在标记出 后,右左失衡一共有三种可能的情况。但是右旋后可以把 的右子树视为一体,也就是说,子树 的高度对其它节点的平衡情况没有任何影响,所以我们可以将情况2和情况3合并为一类。
右左失衡的两种情况及其右左旋操作如图所示。
右左失衡的最简情况及其右左旋操作如图所示。
右左旋操作的代码实现如下,其返回值为该子树的新的根节点。
// 右左旋
Node * rotation_RL(Node * X) {
// 对Z右旋
X->right = rotation_R(X->right);
// 对X左旋
return rotation_L(X);
}
左右失衡和左右旋操作就是右左失衡和右左旋操作的镜像,原理相同,因而不再赘述,只给出代码实现。
左右旋操作的代码实现如下,其返回值为该子树的新的根节点。
// 左右旋
Node * rotation_LR(Node * X) {
// 对Z左旋
X->left = rotation_L(X->left);
// 对X右旋
return rotation_R(X);
}
# 正确性证明
不要忘了,我们必须确保AVL旋转不会破坏二叉查找树的性质。虽然证明非常简单,但这里还是提一下吧。
因为双旋由两次单旋组成,所以我们只需证明单旋的正确性即可。考虑到左旋和右旋的对称性,我们只需证明左旋的正确性即可。
为便于描述,我们用 表示节点 上的值,用 表示子树 (或以 为根节点的子树)上的 任意一个节点 的值。
在旋转前,这是一棵合法的二叉查找树,所以对 而言,子树 上的任意值小于 上的值,而 上的值小于以 为根节点的子树上的任意值。对 而言同理。因此有 且 ,即 。
在旋转后,假定这仍然是一棵合法的二叉查找树,同理可得 且 ,而 包括了 和 ,因此有 。
可以发现,旋转前后不会改变二叉查找树的性质,正确性得证。
# 基本操作与AVL旋转
对于所有非修改操作,包括查询和遍历操作,显然不会改变AVL树中任何节点的平衡因子,因此无需进行任何额外操作。
对于插入和删除操作,二者均可能会破坏若干个节点的平衡性,所以AVL树在此类操作之后必须进行检查,如果平衡性被破坏,则通过若干次旋转来改变树的结构,在保持二叉查找树的性质的情况下恢复平衡性。
根据前文,我想你自己也可以看出,执行插入和删除操作都可能导致四种不同的失衡情况,对每种情况用if-else判断然后执行对应的旋转操作即可。
再平衡的代码实现如下:
// 获取平衡因子
int get_factor(Node * p) {
return (p == nullptr ? 0 : get_height(p->right) - get_height(p->left));
}
// 再平衡
void rebalance(Node * & X) {
// 特判空子树
if (X == nullptr) {
return;
}
// 更新子树高度
update_height(X);
// 获取平衡因子
int f_X = get_factor(X);
Node * Z = (f_X < 0 ? X->left : X->right);
int f_Z = get_factor(Z);
// 分类讨论
if (f_X == +2 && f_Z >= 0) {
X = rotation_L(X); // 右右失衡,左旋
}
if (f_X == -2 && f_Z <= 0) {
X = rotation_R(X); // 左左失衡,右旋
}
if (f_X == +2 && f_Z < 0) {
X = rotation_RL(X); // 右左失衡,右左旋
}
if (f_X == -2 && f_Z > 0) {
X = rotation_LR(X); // 左右失衡,左右旋
}
}
注意在执行再平衡操作之前,一定要确保子树高度已经被更新。或是在插入和删除时执行 update_height(X)
也可。
但是事情并没有这么简单。我们之前所考虑的都是单个子树,问题在于,执行插入和删除操作之后,真的只需要考虑单个子树吗?答案是否定的,在极端情况下,从受影响子树到根节点的这一整条路径上的节点都会发生失衡。
单次旋转能使以 为根节点的子树恢复平衡,但是不一定能使整棵树恢复平衡,原因是在某些失衡情况下,施加旋转操作后,新子树的高度值相对于 插入或删除之前 发生了变化,那么你无法保证更上级的祖先节点的平衡性没有被破坏。
因此,我们需要在操作完成后,从发生变化的节点出发,沿着祖先链不断回溯,对链上的每个节点进行检查和恢复,一直到根节点为止。注意一定是自下而上的进行调整,而不是自上而下的。这个过程可以合并到插入和删除操作的代码实现中。
下面的代码示例来自上一篇文档,只显示了受到影响的部分,其余部分省略。如果你不能理解这个函数调用的位置,说明你对递归和回溯的理解不足。
// 插入
void insert(Node * & p, int value) {
// 递归终止
// ...
// 递归
// ...
// 回溯
rebalance(p);
}
// 删除
void erase(Node * & p, int value) {
// 递归终止
if (value == p->value) {
// 分类讨论
if (p->left != nullptr && p->right != nullptr) {
// ...
} else {
// 删除
// ...
// 回溯
rebalance(p);
}
} else {
// 递归
// ...
}
// 回溯
rebalance(p);
}
————unfinished
事实上,我们并不总是需要对祖先链上的每个节点都进行检查,这里可以进行一些优化。
。。。。
直到发现当前节点的 深度 相对于插入或删除之前没有变化为止,此时说明其余的祖先节点不可能发生失衡,整棵树已经恢复平衡。
————unfinished
# 推导AVL树的最大高度
前文已经提到,维护AVL树的平衡性质,可以保证树的高度值最大为 左右。这里将给出详细推导。
# 考虑最大情况
设高度为 的AVL树的最少节点个数为 。
我们考虑如何能使节点个数最少而不失衡。
考虑根节点的平衡因子显然满足 ,否则,一定可以在左子树(或右子树)处删除一些节点,从而使 从 变为 。
那么对于高度为 的AVL树,当 时,其左右子树的高度分别为 和 。
那么我们递归地考虑,每棵子树都应满足同样的条件,我们再让每棵子树的节点个数都尽可能少,即可得到下列递推式:
即树的大小等于左右子树的大小之和 。
此外,显然有 。由此我们就得到了一个类似于斐波那契数列的递推公式。
接下来我们将推导 的通项公式,数学恐惧症患者可直接跳到后面看结果。
# 通项公式推导
下面给出两种推导方法,均只需初等数学知识即可。感谢 Lingzhi Pan 和 Chao Peng 两位同学的帮助。
方法1,初作者为 Lingzhi Pan ,由 JM233333 完善其语言描述:
我们用待定系数法构造等比数列,设未知数 满足:
与递推式 联立可得:
解此方程组可得到如下两组解 和 :
代回到构造式中可得:
设 ,则上述构造式即为 的等比数列通项公式:
计算初值 可得:
代回到构造式中,并将各变量的数值代入,可得:
对齐 的系数:
联立求解,消去 ,可得:
化简即可得到最终结果。
方法2,初作者为 Chao Peng ,由 JM233333 完善其语言描述:
我们将公式列举如下:
令 得:
令 得:
令 得:
令 得:
因此有:
其中 表示斐波那契数列的第 项,此处我们规定 。
所以有:
代入数值可得:
我们知道斐波那契数列的通项公式为:
代入上述通项公式可得:
那么 即为两个等比数列的前 项和的差。根据等比数列的求和公式代入计算,再化简即可得到最终结果。
# 计算最终结果
推导得到 的通项公式为:
此时已经可以看出 和 之间的关系是指数级别的。
高度为 的AVL树的最少节点个数为 ,那么节点个数为 的AVL树的高度最大为 。也就是说,节点个数为 的AVL树的高度是 的。
下面我们考虑 的具体数字是如何得到的。
我们知道 ,而 ,因此当 不是太小时,我们就可以将该项对结果的影响忽略不计。而若 太小,那么时间复杂度稍大一些我们也不在意。
因此我们将 的表达式估算为:
移项后两边取对数可得:
化简可得:
化为数值可得:
在 的里面 对结果的影响显然可以忽略不计,因此树的最大高度约为 。
其实根据之前的推导可以发现,这是在极端情况下才会出现的,要求每个节点的左右子树都达到最大并不容易。在大多数情况下,AVL树的高度是很接近 的,只是其最大值不超过 而已。
# 总结
在AVL树中可能出现的失衡情况有四类,对这四类失衡情况,我们执行四类不同的AVL旋转操作:
右右失衡: 是 的右子树, 且 。当发生右右失衡时,需要执行左旋操作。
左左失衡: 是 的左子树, 且 。当发生左左失衡时,需要执行右旋操作。
右左失衡: 是 的右子树, 且 。当发生右左失衡时,需要执行右左旋操作。
左右失衡: 是 的左子树, 且 。当发生左右失衡时,需要执行左右旋操作。
# 附录
提出AVL树的论文原文:https://www.docin.com/p-349163097.html
可供有兴趣的同学参考。
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01