二叉搜索树每比较一次,就能排除其中一棵子树,从而回答有序集合的查询。这听起来很高效,但比较次数其实取决于树的高度。如果依次把 插入一棵普通的空搜索树,每个新键都会成为前一个键的右孩子。搜索 5 就需要访问全部五个节点。只有顺序规则,并不足以使树保持较小的高度。
AVL 树额外要求每个节点附近的两棵子树高度相差不多。它的价值在于:一个可以在更新路径上检查和修复的局部条件,能够保证整棵树的高度界。本节先证明这一点,再区分旋转的两项任务:保持树所存储的键,以及恢复高度条件。删除尤其需要小心,因为一次成功的修复可能使子树变矮,进而使更高的祖先失衡。
先说明有序集合的操作约定
假设所有键互不相同,并具有固定的全序。每个节点存储一个键、两个孩子指针,以及其子树高度。插入已存在的键时,集合不变;删除不存在的键时,集合也不变。映射还会存储与每个键关联的值,但我们先研究集合接口。
定义 15.1.1
(搜索顺序、高度与 AVL 平衡)
在键为 的节点,左子树的每个键都小于 ,右子树的每个键都大于 。两棵子树也分别递归满足相同条件。这就是二叉搜索树不变量。
高度按边数计算:空子树的高度为 ,叶节点的高度为 0。对于非空节点 ,
定义其平衡因子为
如果二叉搜索树的每个节点都满足 ,它就是一棵 AVL 树。
定义也不要求每一层都填满。在每个节点比较的是两棵子树的高度,而不是键的数量。
常见错误
(只检查根的平衡)
树 10(5(4(3,-),-),15(12,-)) 的根平衡因子为 ,因为左子树高度为 2、右子树高度为 1。它却不是 AVL 树:节点 5 的左高度为 1、右高度为 ,平衡因子为 2。
如果根的高度为 ,搜索最多访问 个非空节点,随后可能到达一个空孩子指针。因此,我们只需用存储的键数 来限制 。
为什么局部平衡能够保证对数高度
令 表示高度恰为 的 AVL 树所需的最少节点数。初始值为 、。高度为 的树,至少有一棵子树的高度为 ;平衡条件要求另一棵的高度至少为 。选择这两种高度各自最小的 AVL 子树,确实能达到最少节点数,因此对 ,
| 高度 | |||||||
|---|---|---|---|---|---|---|---|
| 最少节点数 |
这个递推式与 Fibonacci 递推式相似。不过,要证明对数高度,我们不必先求出它的闭式公式。
定理 15.1.2
(AVL 树的对数高度)
含 个键的 AVL 树,高度满足 。搜索最多访问 个节点。
证明
(不求解递推式,也能得到高度界)
设 。当 时,递推式变为
因为 随高度增加。初始值满足 、。每次将高度减少二进行归纳,可得
一棵有 个节点、高度为 的 AVL 树满足 ,因此
所以搜索时间为 。这个界有意取得比较宽松;目的是直接从平衡不变量证明高度呈对数增长。
证明透视
为什么要加一,又为什么一次减二
令 去掉了递推式中多出的常数,于是 成为纯加法关系。一次减二是由假设决定的:平衡只保证较矮的子树高度至少为 ,并不保证 ;如果把 用两次,就要求两棵子树的高度都是 ,这仅对完全平衡的形状成立。
平衡假设不能去掉。按 的递增顺序插入得到的搜索树是一条链,、高度为 ,而 AVL 树必须满足 。
证明也说明了更新必须保持什么。不能只凭某个小例子的树形看起来紧凑,就认定算法正确:高度界所依赖的不变量,必须在每个节点继续成立。
旋转保持整个有序集合
假设节点 的左孩子为 。用 表示整棵子树,其中可以有空子树。右旋转改变以下指针:
z y
/ \ / \
y C becomes A z
/ \ / \
A B B C
中间子树 从 的右侧移到 的左侧。不能将它丢失,也不能使它同时保留在两个位置。图中子树如果还有父节点,其指针现在必须改为指向新根 。
命题 15.1.3
(旋转保持搜索顺序)
设 是二叉搜索树的根,其左孩子为 , 如图所示。右旋转得到的仍是同一组键上的二叉搜索树,中序序列不变,并且可以取代任何更大搜索树内的原子树。
证明
(旋转前后的中序序列相同)
旋转前,搜索顺序给出
如果某棵子树为空,省略涉及其键的比较。这些不等式同样支持旋转后的每个位置: 应位于 左侧; 应位于 右侧、 左侧; 应位于 右侧。
也可以观察中序序列:两边都是 。没有增加、丢失或重复任何键,所以旋转后的子树表示同一个有序集合。它对外需要满足的键值上下界也不变,因此可以在一棵更大的搜索树中替换原子树。
这证明了搜索顺序得以保持。旋转是否恢复 AVL 平衡,仍取决于子树的高度;不能单靠顺序证明第二件事。
左旋转就是左右对称的操作。两者都只修改常数个指针。更新高度时,先更新位置较低的旧根,再更新新根;第二次计算要使用第一次更新后的高度。
根据孩子的平衡因子选择修复
经过一次插入或删除,并完成某节点下方的修复后,该节点的平衡因子只可能是 或 2。如果为 2,说明左孩子 过高。当 时,一次右旋转就足够;当 时,先左旋转 ,再右旋转原根。这个双旋转会把中间的键带到上方。右侧过高的情况则左右对称。
| 的平衡因子 | 较高孩子的平衡因子 | 修复方式 |
|---|---|---|
| 右旋转 | ||
| 先左旋转左孩子,再右旋转 | ||
| 左旋转 | ||
| 先右旋转右孩子,再左旋转 |
例题 15.1.4
(两种插入形状需要不同修复)
依次插入 30、20、10。在 30 处,左子树高度变为 1,右侧空子树高度为 ,所以平衡因子为 2。它的左孩子 20 的平衡因子为 1。一次右旋转得到根 20、左右叶节点 10 和 30,所有节点都平衡。
改为依次插入 30、10、20。30 的平衡因子仍为 2,但其孩子 10 的平衡因子为 。如果立即右旋转 30,新根 10 的右子树高度会是 1,左子树却为空,仍然失衡。应当先左旋转 10,将 20 移到它上方,再右旋转 30。最后同样得到根 20、左右孩子 10 和 30。
两例最终的有序集合相同。决定修复方式的是中间状态的孩子平衡因子,而不是存储的键集合。
命题 15.1.5
(插入后的修复恢复原有子树高度)
设 是新插入节点自底向上第一个平衡因子变为 的祖先(如果有的话)。按上表选择的单旋转或双旋转,使修复后子树的每个节点都平衡,而且其高度等于插入前以 为根的子树高度。因此 的祖先不会因这次插入而改变高度或平衡因子。
证明
(单旋转与双旋转之后的高度)
对于插入,设 是自底向上第一个失衡的祖先。插入前,它较高的子树高度为 ,另一棵为 。插入使较高子树升至 。在左左型情况下,沿用上方旋转图的记号:插入后 的高度为 , 和 的高度均为 。右旋转使 的高度变为 ,新根 的高度为 。
在左右型情况下,设 是插入后 的右子树的根。 的高度为 ,它的两个孩子高度均不超过 。外侧两棵子树,即 左方和 右方的子树,高度均为 。双旋转使 和 成为 的孩子。两者现在的高度均为 ,所以新根 的高度为 。右侧较高的情况则左右对称。
两种修复因此都恰好恢复插入前的子树高度。 上方的祖先看不到净高度增加。一次单旋转或双旋转修复就足够,但找到插入位置并更新高度,仍然需要经过一条对数长度的路径。
删除可能终止,也可能传递高度变化
普通搜索树的删除,最终会移除一个最多只有一个孩子的节点。如果指定节点有两个孩子,先把其中序后继的键复制过来,再从右子树删除这个后继。后继是右子树中最小的键,因此没有左孩子。搜索顺序仍然成立,而集合恰好失去指定的键。如果是映射,必须连同键一起复制其关联值。
沿真正被移除的节点到根的路径返回时,逐层修复。不能根据被删键的原位置判断旋转;必须检查目前较高孩子的平衡因子。
例题 15.1.6
(较高孩子的平衡因子为零时,应当单旋转)
最初根为 4;左子树的根为 2,两个叶子为 1 和 3;右子树的根为 6,右侧还有叶子 7。整棵树高度为 2。先删除 7,使 6 成为叶节点;根 4 的平衡因子为 1,仍然平衡。
现在删除 6。在根 4 处,子树高度为 1 和 ,平衡因子变为 2。它的左孩子 2 的平衡因子是零。右旋转 4:
4 2
/ / \
2 becomes 1 4
/ \ /
1 3 3
旋转后,节点 4 的高度为 1、平衡因子为 1;节点 2 的高度为 2、平衡因子为 。所有节点都平衡。修复后的子树高度仍为 2,等于删除 6 之前的高度。如果上方还有祖先,它不会看到高度下降,所以这次修复会终止高度变化的向上传递。
平衡因子为零的孩子会在删除中出现,因此修复表需要使用 和 。如果只记住插入时新键的方向,就容易漏掉这种情况。
其他删除修复会降低子树高度,于是祖先也可能失衡。
例题 15.1.7
(一次删除使两个祖先都要旋转)
记号 k(left,right) 表示根为 k,- 表示空孩子,单独一个键表示叶节点。初始树为
8(5(3(2(1,-),4),7(6,-)),11(10(9,-),12))
它是一棵包含键 1 至 12 的 AVL 树。左子树高度为 3、右子树高度为 2,根的高度为 4。删除叶节点 12。在节点 11 处,左高度为 1、右高度为 ;右旋转 11 后得到 10(9,11)。这棵子树的高度从 2 降至 1。根 8 现在的两棵子树高度为 3 和 1,也需要修复。它的左孩子 5 的平衡因子为 1;右旋转 8 后得到
5(3(2(1,-),4),8(7(6,-),10(9,11)))
最终高度为 3。一次删除使两个不同的祖先需要旋转。如果修复第一个节点后就停止,根 8 仍会失衡。
返回修复后的新根,并在局部维护高度
下面的 Python 程序明确写出指针和高度的更新规则。insert 和 erase 返回可能已经改变的根,调用者必须保留它,例如 root = erase(root, key)。键的比较必须构成一致的全序。程序不会递归遍历子树来重新计算高度;refresh 只读取两个孩子存储的高度。
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 0
def height(v):
return -1 if v is None else v.height
def refresh(v):
v.height = 1 + max(height(v.left), height(v.right))
def balance(v):
return height(v.left) - height(v.right)
def rotate_right(z):
y = z.left
z.left = y.right
y.right = z
refresh(z)
refresh(y)
return y
def rotate_left(z):
y = z.right
z.right = y.left
y.left = z
refresh(z)
refresh(y)
return y
def rebalance(v):
refresh(v)
if balance(v) == 2:
if balance(v.left) < 0:
v.left = rotate_left(v.left)
return rotate_right(v)
if balance(v) == -2:
if balance(v.right) > 0:
v.right = rotate_right(v.right)
return rotate_left(v)
return v
def insert(v, key):
if v is None:
return Node(key)
if key < v.key:
v.left = insert(v.left, key)
elif key > v.key:
v.right = insert(v.right, key)
else:
return v
return rebalance(v)
def erase(v, key):
if v is None:
return None
if key < v.key:
v.left = erase(v.left, key)
elif key > v.key:
v.right = erase(v.right, key)
else:
if v.left is None:
return v.right
if v.right is None:
return v.left
successor = v.right
while successor.left is not None:
successor = successor.left
v.key = successor.key
v.right = erase(v.right, successor.key)
return rebalance(v)
旋转过程要求图中相应的孩子存在;rebalance 的平衡条件保证了这一要求。此外,rebalance 假设两棵子树已经是 AVL 树、高度数据正确,而当前节点是经过一次普通更新后到达的状态。它修复的是这种情况,并不是用来平衡任意损坏的树。
常见错误
(丢掉返回的根)
对 20(10,30(-,40)) 执行 erase(root, 10),节点 20 失去左叶节点后,右子树比左子树高 2,所以会返回新根 30,得到 30(20,40)。如果调用者只写 erase(root, 10) 而不接收返回值,root 仍指向节点 20;它现在是 30 的左孩子,没有右子树,从它出发无法到达键 30 和 40。应写成 root = erase(root, 10)。
每个正在返回的递归栈帧只做常数工作,最多两次旋转。原树的高度为对数级,所以插入和删除的最坏时间都是 ,包括搜索后继所需的时间。递归栈使用 空间,全部节点占用 空间。删除可能修复多个祖先,但路径上总共只有对数个祖先。
反例模式
局部看起来正确,不代表整棵树正确
在两个祖先连锁修复的例子中,假设程序修复节点 11 后就停止。以 10 为根的右子树是一棵正确的 AVL 树。整个结构的中序遍历仍然有序,也恰好包含应有的键。然而,根 8 的平衡因子为 2。只检查键是否排序,就会漏掉这个错误。
必须分别检查三件事:键的顺序正确;每个存储高度等于一加两个孩子高度的最大值;每个平衡因子的绝对值不超过一。即使所有指针都正确,过期的高度仍可能掩盖失衡。这三个断言对应不同的数学责任。
练习与详解
快速检查
(1. 一致使用高度约定)
一棵 AVL 树存储十个键。它的高度可以是 4 吗?可以是 3 吗?使用最少节点数递推式,而不是比较宽松的对数上界。
解答 · 解答 1
高度 4 不可能,因为 。高度 3 则可以。完整的高度 2 树有七个节点,在下一层的可用位置加入三个孩子,并保持各处平衡即可。例如 4(2(1,3),8(6(5,7),9(-,10))) 有十个键、高度为 3,每个节点的平衡因子绝对值都不超过一。
快速检查
(2. 找出旋转中的中间子树)
右旋转前,根 40 的左孩子为 20,而 20 的右子树以 30 为根。旋转后,这棵子树应当接到哪里?哪些键值不等式支持这个移动?
解答 · 解答 2
它成为 40 的左子树,而 40 成为 20 的右孩子。被移动子树的每个键都严格介于 20 与 40 之间,所以旋转前后都应位于 20 右侧、40 左侧。如果仍把它留在原来的孩子指针位置,又把 40 接到同一位置,就会丢失子树或破坏树的连接。
快速检查
(3. 跟踪右左型插入)
向空 AVL 树依次插入 10、30、20。指出第一个失衡节点、两个相关的平衡因子、旋转顺序和最终高度。
解答 · 解答 3
节点 10 的平衡因子为 ,它的右孩子 30 的平衡因子为 1。先右旋转 30,再左旋转 10。最终根为 20,叶子为 10 和 30,高度为 1。只在原根进行一次左旋转并不足够。
快速检查
(4. 删除有两个孩子的节点)
在 20(10,30(25,40)) 中,用中序后继方法删除 20。用哪个键替换它?真正被移除的是哪个节点?完成所需的平衡检查后,树形如何?
解答 · 解答 4
后继为 25。把 25 复制到根,再从右子树移除原来的叶节点 25。结果是 25(10,30(-,40)),高度为 2。根 25 的平衡因子为 ,节点 30 的平衡因子为 ,叶节点的平衡因子都是 0,因此不需要旋转。集合失去 20,而 25 仍恰好只出现一次。
快速检查
(5. 为什么一次删除修复未必完成任务?)
在十二个键的删除例子中,刚修复节点 11 后,根 8 的两棵子树高度分别是多少?为什么递归返回时必须继续对根 8 进行平衡修复?
解答 · 解答 5
左高度仍为 3,修复后的右子树高度为 1,因此根 8 的平衡因子为 2。第一次旋转保持了顺序,也修复了自己的子树,但同时使这棵子树变矮,没有修复祖先因此出现的失衡。第二次右旋转才在那里恢复 AVL 平衡,得到最终根 5。
快速检查
(6. 区分常数时间的高度更新与递归测量)
为什么程序在每个节点存储高度?如果 refresh 改为每次返回时递归计算整棵当前子树的高度,仅凭对数高度界还能证明更新时间为对数级吗?
解答 · 解答 6
读取已经存储的孩子高度,使每次更新只需常数时间;返回栈帧数量为对数级,总工作量才是对数级。如果在根上递归测量高度,单是这次测量就可能访问全部 个节点。因此,树高为对数级将不足以推出更新时间为对数级。结构界限制栈帧数量;实现还必须限制每个栈帧内的工作量。