二叉搜索树可以按比较结果寻找键,但一般排序不变量不会直接告诉我们一个节点下面有多少个键。每个节点多存储一个数字,便可搜索第五小的键;但更新操作必须维持该数字的意义。
1. 定义扩充数据
定义 4.1.1
(子树大小与排名)
假设二叉搜索树有限且键值互不相同:左子树的每个键小于节点的键,右子树的每个键则较大。每个节点 存储其整棵子树(包括自身)的节点数 ;空子树记作 。局部规则为
键 在树中的排名是 加上树中小于 的键的个数;第 小的键就是排名为 的键。
排名从 1 开始。以下操作要求 ;搜索前须拒绝超出范围的排名。特别是空树没有有效排名。键值互异令“第 小的键”没有歧义;若允许重复值,须明确规定重数及相应计数,本节不暗中涵盖该情况。
2. 选取算法
在当前节点,令 为左子树的存储大小。该节点在其子树中恰有 个键排在它之前,所以局部排名是 。
select(root, k): // precondition: 1 <= k <= size(root)
x = root
while x is not empty:
L = size(x.left)
if k == L + 1: return x.key
if k <= L:
x = x.left
else:
k = k - (L + 1)
x = x.right
定理 4.1.2
(排名选取的正确性与成本)
设 是键值互异的二叉搜索树,其存储的大小满足局部规则,且 。则 select(root, k) 返回 中第 小的键。若 是以边数计的高度,它最多检查 个节点。
证明
(关于当前排名的循环不变量)
断言:每次进入循环时,x 非空、,且要返回的键是以 x 为根的子树中第 小的键。第一次进入时,由前置条件,这正是调用者的要求。
设断言在某次进入时成立,并令 。由排序性质,该子树的键依次是:左子树的 个键、x 的键、右子树的键。若 ,答案就是 x 的键,并被返回。若 ,则 ,左子节点非空,,而该子树第 小的键就是左子树第 小的键。若 ,则 ,且 ;所以右子节点非空,答案是它第 小的键。两种下降情形下,断言在下一次进入时对 x 的某个子节点成立。每一步下降一层,因此循环至多进入 次;又因为 x 一直非空,循环只能由 return 结束。
证明透视
为何循环不会离开这棵树
论证靠两件事。第一,二叉搜索树的次序使子树内的排名分成连续三块:左边的键、该节点、右边的键,所以排名可以换算成某个子节点中的排名。第二,存储的大小在证明中用了两次: 用来定位这三块,而 说明换算后的排名仍在范围内。若某个存储的大小已过时,第二个不等式可能失效,下降便可能到达空子节点。键值互异也有用:若有重复键,“第 小的键”就不能确定单一节点。
若高度 按最长根到叶路径的边数计算,最多检查 个节点。故选取时间为 、额外空间为 ;整棵 节点树的大小字段使用 存储空间。不平衡树可能有 ,因此对数时间还需要额外的平衡保证。
反例模式
不检查排名就执行 select
断言:无论 是什么,循环都会返回一个键。取下一节的七节点树及 。在 16, 且 ,所以 变成 , 变成 24。在 24, 且 ,所以 变成 , 变成 31。在 31, 且 ,所以 变成 , 变成空的右子节点;循环结束,却没有任何 return。对 ,路径 16、7、3 同样在 3 的空左子节点结束。修正办法就是所述前置条件:搜索开始前,拒绝所有 或 的排名。
3. 例子
考虑以下互异键树;括号内是存储的子树大小:
16(7)
/ \
7(3) 24(3)
/ \ / \
3(1) 11(1) 20(1) 31(1)
例题 4.1.3
(七节点树中的排名 5)
求排名 。在 16,左子树大小为 3,跳过这三个键及 16;接着在右子树寻找排名 。在 24,左子树大小为 1,故排名不变往左走。在 20,左子树大小为 0,,因此返回 20。中序序列为 3, 7, 11, 16, 20, 24, 31,可独立检查结果。
例题 4.1.4
(最小键、最大键与根)
:在 16,左子树大小为 3 且 ,向左;在 7,左子树大小为 1 且 ,向左;在 3,左子树大小为 0,,返回 3,即最小键。:在 16,,所以 变成 ,向右;在 24,,所以 变成 ,向右;在 31,,返回 31,即最大键。 时根节点立即回答,因为 ;中序序列也显示第四个键是 16。
4. 修改树后维持大小
把新互异键插入为叶节点后,令其大小为 1,再由下往上重新计算搜索路径上每个祖先的大小。若拒绝重复键插入,树与计数都不变。删除时同样要重新计算实际移除所影响的所有祖先。特别是双子节点删除若以复制中序后继的键、再移除后继节点实现,须由被移除节点的原父节点向上重新计算,适用时包括目标节点。后继恰为目标的直接右子节点也包括在内:此时其原父节点就是目标。这是单次操作的更新规则,不表示可让并发读取者看到复制键的中间状态。
旋转保留中序键序列,却会改变两棵局部子树包含的节点。对 x 及其右子节点 y 进行左旋后,先用新子节点重新计算 s(x),再算 s(y)。此局部旋转下,更高祖先的后代集合不变。平衡算法可以使用这些局部更新;本节没有证明任何平衡算法,也不保证对数高度。
例题 4.1.5
(在根作左旋后的大小)
在七节点树中,对 x = 16 及其右子节点 y = 24 左旋。于是 24 成为根,16 是其左子节点,24 原来的左子节点 20 成为 16 的右子节点;16 的左子节点 7(3) 不变。先重新计算 s(16)=1+3+1=5,再计算 s(24)=1+5+1=7。中序序列仍是 3, 7, 11, 16, 20, 24, 31。现在选取排名 5:在 24, 且 ,向左;在 16, 且 ,所以 变成 ,向右;在 20,,返回 20,与之前相同。
常见错误
(向右走时只跳过左边的键)
当 ,被跳过的键是左边 个键加当前键,所以新排名是 。只减去 会使排名大了一。在七节点树中取 ,根节点会带我们以排名 向右;在 24, 且 ,代码便会返回 24。正确答案是 20。
常见错误
(旋转后以错误的次序重新计算大小)
上述左旋之后,16 是较低的节点,24 是较高的节点。24 的大小取决于 16 的新大小。若先重新计算 s(24),就会用上已过时的 ,得出 ,而不是 。应先重新计算较低的节点,再算较高的节点。
5. 检查与练习
快速检查
(在例子树中插入 18 并更新大小。之后排名 6 返回什么?)
沿 18 的搜索路径,由下往上重新计算。
解答 · 答案
路径是 16 -> 24 -> 20;18 成为 20 的左子节点。20、24、16 的新大小分别是 2、4、8。此时排名 6 返回 20,因为中序序列是 3, 7, 11, 16, 18, 20, 24, 31。
快速检查
(原七节点树的排名 0 或 8 有什么意义?)
对照 select 的前置条件。
解答 · 答案
按从 1 开始的约定,两者均无效;应拒绝,而非返回可能被误认为键值的哨兵。
快速检查
(为何一般 BST 排序不变量不足以保证所述复杂度?)
想一想算法在每个节点必须知道什么。
解答 · 答案
没有存储大小时,求 可能要数遍很大的子树;有了大小,在一般指针模型下每层的排名决策只需常数工作。
快速检查
(解释为何同一组键可构成不同高度的 BST。)
想一想键的插入次序。
解答 · 答案
把已排序的互异键插入普通不平衡 BST 可能形成链;按排名选取仍正确,但可能逐一访问线性数量的节点。
局部不变量与成本分析假设计数初始化正确,且操作期间没有并发修改。