在二叉搜索树中删除一个键,不能只保证中序输出仍然有序:所有保留下来的子树都必须仍然可达,而基于指针的实现还必须遵守其关于节点身份与内存所有权的约定。
1. 不变量与双孩子障碍
假设各键互不相同,并考虑普通的二叉搜索树(BST):节点左子树中的每个键都小于该节点的键,右子树中的每个键都大于该节点的键。两棵子树也都满足同样的规则。查找在每次比较后沿一个孩子前进;其代价由树高控制,而不会自动等于节点数的对数。
叶节点可以直接删除。若一个节点恰有一个孩子,其父节点可以用这个孩子替换该节点;当该节点是根时,树的根必须随之改变。若节点有两个孩子,则任何一个孩子都不能在不顾及另一棵子树的情况下简单地取代该节点。一个有用的替换键是中序后继。
定义 17.1.1
(有两个孩子的节点的中序后继)
设 是各键互不相同的 BST 中有左、右孩子的节点。 的中序后继是存放 右子树最小键的节点。
引理 17.1.2
(后继节点的位置)
设 是双孩子节点 的中序后继。则 没有左孩子; 左子树中的每个键都小于 的键; 右子树中其余的每个键都大于 的键。
证明
(右子树最小值的最小性)
若 有左孩子,该孩子就是同一右子树中更小的键,与最小性矛盾,所以 没有左孩子。左子树的每个键都小于 的键,而 的键又小于右子树的每个键,尤其小于 的键。右子树其余的键不小于最小值,又因各键互不相同而不等于它,所以更大。
概念视角结构
删除即与排序中的下一个键交换
通过中序序列来读这棵树,它按递增顺序列出所有键。后继就是该序列中 之后的下一个键。由引理,它没有左孩子,所以把 的键与它交换,双孩子的删除便化为较容易的情形:移除至多有一个孩子的节点。
然而,后继可能有右孩子,并且这个右孩子必须在后继原来的位置上取代它。如果在追踪过程中假定最小节点总是叶节点,就很容易漏掉这种情况。
反例模式
后继节点不一定是叶节点
断言:要删除有两个孩子的节点,只需把后继的键复制进去,再把后继的父节点的左指针设为 null 以拆下后继。取根 ,左孩子 ,右孩子 ,其中 有孩子 和 ,而 有右孩子 。 的后继是 ,它不是叶节点。把 复制到根并把 的左指针设为 null 后,节点 便无法到达,尽管 从未被删除,中序序列也丢失了 。修正办法是用后继的右孩子(这里是 )取代后继,下面的算法正是这样做的。
2. 返回新的子树根
下面是一种递归设计。它使用左/右孩子指针,不使用父指针,并在每次删除后返回可能已改变的根。所存储的 record 包含键和负载数据,不包含节点的孩子链接。在伪代码中,t.key 是 t.record.key 的简写。假设复制一条记录会得到一个独立的值,在源节点被释放后仍然有效;在使用拥有所有权指针的实际程序中,需要明确的深拷贝或所有权转移策略。
pop_min(t): // precondition: t != null
if t.left == null:
record = copy(t.record)
replacement = t.right
free(t)
return (record, replacement)
(record, t.left) = pop_min(t.left)
return (record, t)
delete(t, key):
if t == null: return null
if key < t.key:
t.left = delete(t.left, key)
else if key > t.key:
t.right = delete(t.right, key)
else:
if t.left == null:
replacement = t.right; free(t); return replacement
if t.right == null:
replacement = t.left; free(t); return replacement
(record, t.right) = pop_min(t.right)
t.record = record
return t
pop_min 同时返回一条复制出的记录以及剩余部分的根。在递归回退时,每个调用者都把自己的左孩子重新连接到该剩余部分。删除操作的调用者必须对返回的根进行赋值,包括在最顶层:root = delete(root, key)。删除不存在的键时会到达空指针,并保持已有链接不变。如果某个实现保留父指针或对外可见的节点引用,则需要额外的更新,或者采用不同的身份策略。
常见错误
(忽略返回的根)
设一棵树的根 只有右孩子 。调用 delete(root, 5) 会释放根节点并返回 。若调用者只写 delete(root, 5) 而保留旧的 root 变量,它现在持有的是悬空指针。结果必须赋值回去:root = delete(root, 5)。
常见错误
(取右子树的最大值而不是最小值)
在下面第一个删除示例的树中,目标 的右子树含键 。若代码把最大值 复制到根并删去该叶节点,根变成 ,但 仍在其右子树中,比根小。次序因而被破坏:查找 时与 比较后向左进入 的子树,结果失败。只有右子树的最小值才小于该子树其余所有的键。
3. 删除示例
例题 17.1.3
(后继节点不是叶节点)
取根 40,其左孩子为 20(孩子为 10,30),右孩子为 70(孩子为 50,80)。节点 50 有右孩子 60。使用上述值复制规则删除键 40。
右子树中的最小值是 50,经由 70 -> 50 到达;它没有左孩子,但有右孩子 60。pop_min 把记录 50 和子树 60 返回给其调用者,于是 70.left 变为 60。把该记录复制到原来的根节点。最终的根键为 50,左子树以 20 为根、孩子为 10 和 30,右子树以 70 为根、孩子为 60 和 80。其中序序列为 10,20,30,50,60,70,80:它恰好包含除 40 以外的所有原有键。
原先存放 40 的节点得以保留,但记录已改变;原先存放 50 的节点被释放。如果客户端把节点地址视为稳定的身份,就不能想当然地认为复制键等同于删除所请求的那个节点。基于移植(transplant)的设计则可以改为移动后继节点本身,但必须修复其原父节点与新父节点的链接,并说明哪些引用仍然有效。
例题 17.1.4
(后继是右孩子,以及不存在的键)
取根 40,左孩子 20(孩子为 10,30),右孩子 70,其中 70 只有右孩子 80。删除键 40。右子树的根没有左孩子,所以 pop_min(70) 走第一个分支:复制记录 70,返回 replacement 80,并释放节点 70。调用者令 40.right = 80,并把记录 70 复制到根,得到根 70,左子树为 20(孩子 10,30),右孩子为 80。中序序列为 10,20,30,70,80,即原有的键去掉 40。从原来的树删除键 99 时,依次与 40、70、80 比较,到达 null,各节点原封不动地返回。
例题 17.1.5
(删除只有一个孩子的根)
设树的根 5 只有右孩子 8。delete(root, 5) 在根处找到相等,看到 t.left == null,保存 replacement = t.right,释放根并返回 8。新的根是 8,其下的子树不变。若根只有左孩子,则第二个分支会返回该孩子。两种情况下树的根变量都会改变,这就是 delete 的结果要赋值回去的原因。
4. 正确性与代价
定理 17.1.6
(删除的正确性)
设 是各键互不相同的 BST 的根。当 null,pop_min(t) 返回最小键的记录,以及恰好存放其他键的 BST 的根。而 delete(t, key) 返回一棵 BST 的根,该 BST 恰好存放 中除 key 以外的键;若 key 不存在,键集合不变。
证明
(对树高作归纳)
对 pop_min:若 t.left 为 null,最小值就是 t.key,因为右边的键都更大,而剩余部分 t.right 是存放其他键的 BST。否则 的最小值就是左子树的最小值,因为所有左边的键都小于 t.key;由归纳,pop_min(t.left) 返回它以及存放其余左键的 BST,把该 BST 重新连为左孩子,其所有键仍小于 t.key。
对 delete,按高度作归纳。null 的情形返回 null,正确,因为键不存在。若键小于 t.key,它只可能在左子树中;由归纳,左子树成为存放相同键(去掉它)的 BST,其键仍全部小于 t.key,所以 是 BST。键更大的情形对称。若键等于 t.key 且有一个孩子为 null,另一棵子树本身就是存放其余键的 BST。有两个孩子时,设 为后继。由引理,左边的键都小于 的键,而 pop_min 留下的右边剩余部分存放其余右键,全都大于它。把 的记录复制进 ,所得 BST 的键就是 的键去掉旧键。每种情形下,返回的子树只是少了一个键,其键仍在旧子树的界限之内,所以祖先的界限仍然成立。
证明透视
互不相同与最小性用在哪里
后继的最小性用了两次:使复制的键大于左子树的一切,并使右边剩余部分的每个键都大于复制的键。互不相同把“不小于最小值”变成 BST 规则所要求的“严格更大”。返回根的约定使单孩子情形和根的情形可以共用同一个证明:每次递归调用都返回键集合已知的子树,所以父节点只需把它重新连接。归纳得以完成,因为每次调用都向下一层。
令 h 表示最长的根到叶路径上的节点数。查找目标、再下降到其后继并将其删除,总共访问 O(h) 个节点;沿递归返回使用 O(h) 个栈帧。在链状树上,h 可以等于 n,因此最坏情况时间为 O(n)。要得到平衡的高度界,需要额外的平衡保证;普通 BST 并不提供这种保证。这些代价假设键比较、记录复制和指针更新都是常数时间的,并且输入是一棵有效的无环树。
5. 检查
快速检查
(在第一个删除示例的树中, 仍在,删除 。所得的树及其中序序列是什么?)
找出 的右子树的最小值。
解答 · 答案
的右子树只有节点 ,所以后继是 ,pop_min 返回记录 及空的剩余部分。原来存放 的节点现在存放 ,左孩子为 ,没有右孩子。中序序列为 10,30,40,50,60,70,80。
快速检查
(在同一棵树中删除 。哪个节点成为后继,右边部分的形状是怎样的?)
的右子树是节点 。
解答 · 答案
后继是 ,是叶节点。原来存放 的节点现在存放 ,保留左孩子 (其右孩子为 ),失去右孩子。中序序列为 10,20,30,40,50,60,80。
快速检查
(为何调用者必须写 root = delete(root, key),而不是只调用 delete(root, key)?)
想一想删除唯一的节点,或只有一个孩子的根。
解答 · 答案
根节点本身可能被释放,并由其孩子或 null 取代。只有返回值才标示新的根;旧变量会悬空。
快速检查
(按 的次序把它们插入空的普通 BST。 是多少?delete(root, 4) 访问多少个节点?)
先画出这棵树,再计算。
解答 · 答案
这棵树是由右孩子组成的链 ,所以 个节点。调用依次与 比较,然后以返回其 null 右孩子的方式删去叶节点 ,所以访问 个节点,与 成线性。