动机
二叉搜索树（binary search tree, BST）的形状记录了比较结果。在键为 x
的节点，只需一次比较，就能排除整棵不可能包含目标的子树：较小的键只能
在左侧，较大的键只能在右侧。因此，搜索、最小值、最大值、插入、中序
后继及删除并非六套无关技巧，而是同一个次序不变式的推论。
这个观点也能避免把 BST 操作一律写成 O(log n)。操作沿根到叶的路径
前进，直接控制成本的是树高 h。形状匀称的树可以有对数高度；插入顺序
不理想时，树也可能退化成链。这里所说的“平衡”只是在描述树高为
O(log n) 的形状，不代表任何维护算法。本节只处理课程资料支持的核心 BST，不讲授
AVL、红黑树、旋转或其他平衡算法。
定义
定义
二叉搜索树不变式
本节的 BST 是一棵键可比较且互不相同的二叉树。对每个节点 v，
v.left 中的每一个键都严格小于 v.key，v.right 中的每一个键都
严格大于 v.key；左右子树本身也必须满足同一条件。
“每一个键”是重点。只检查直接子节点并不充分；孙节点即使与父节点的 大小关系正确，也可能越过祖先规定的界限。递归验证时，可以把允许区间 传入子树：左子树新增上界，右子树新增下界。
课程来源采用键唯一的约定。如果插入已经存在的键，实现可以拒绝插入， 或像课堂 ADT 一样替换该键所存的数据，但不能建立第二个同键节点。
定义
树高约定
树高 h 是从根向下到叶的最长路径所含的节点数。空树高度为 0，
单节点树高度为 1；非空树的高度等于左右子树高度的最大值再加一。
搜索、最小值与最大值
搜索把目标键与当前节点比较；相等就成功，较小走左，较大走右。每轮开始
时维持以下不变式：如果目标仍存在，它必在当前子树。到达 NIL 时，所有
合法方向都已用尽，因此能证明目标不存在，而不只是“暂时没有找到”。
SEARCH(root, key):
v = root
while v != NIL:
if key == v.key: return v
if key PRECEDES v.key: v = v.left
else: v = v.right
return NIL
最小值持续走左，直到没有更小的左子树；最大值则持续走右。两者要求起点
非空，否则接口应返回“不存在”，不能解引用 NIL。最小节点不一定是
叶：它仍可有右子节点；最大节点也可有左子节点。
MINIMUM(v): MAXIMUM(v):
while v.left != NIL: while v.right != NIL:
v = v.left v = v.right
return v return v
插入
插入其实是一次失败搜索：记住最后一个非空节点，并按最后比较把新叶连接到 左侧或右侧。下面的版本拒绝重复键。
INSERT(root, key):
if root == NIL: return NEW_NODE(key)
parent = NIL
v = root
while v != NIL:
parent = v
if key == v.key: return root
if key PRECEDES v.key: v = v.left
else: v = v.right
if key PRECEDES parent.key: parent.left = NEW_NODE(key)
else: parent.right = NEW_NODE(key)
return root
旧节点的位置完全不变，新键只占据第一个空位置。递归版本必须把返回的 子树根重新存入父节点；向空树插入会产生新根，忽略返回值就会丢失更新。
中序后继
定义
中序后继
节点 x 的中序后继，是中序遍历时紧接 x 被访问的节点。在键唯一的
BST 中，它也是严格大于 x.key 的最小键；全树最大节点没有后继。
结构上只有两种情况：如果右子树非空，答案是右子树最小节点；否则向上走，
跳过所有从右分支到达的祖先，第一个从其左分支到达的祖先就是答案。如果
不存在，就返回 NIL。
SUCCESSOR(x):
if x.right != NIL: return MINIMUM(x.right)
p = x.parent
while p != NIL and x == p.right:
x = p
p = p.parent
return p
从右分支到达的祖先早已在中序遍历中出现，故必须跳过；第一个从左分支 到达的祖先尚未被访问。这个做法需要教程指出的 parent 指针，或从根搜索 时保存的完整路径；只有左右子节点指针无法向上移动。
删除
删除先搜索目标，再按子节点数处理：叶由 NIL 取代；只有一个子节点时，
由该子树取代；有两个子节点时，由右子树最小值（后继）取代，再删除后继
原来的位置。对称地使用左子树最大值（前驱）也正确。
DELETE(t, key):
if t == NIL: return NIL
if key PRECEDES t.key:
t.left = DELETE(t.left, key)
else if t.key PRECEDES key:
t.right = DELETE(t.right, key)
else:
if t.left == NIL: return t.right
if t.right == NIL: return t.left
s = MINIMUM(t.right)
t.record = COPY(s.record)
t.right = DELETE(t.right, s.key)
return t
右子树最小节点不可能有左子节点，否则该左节点会是同一子树中更小的键； 所以移除后继只会落入零或一个子节点的简单情况。程序实现还须分开处理 内存所有权：释放正确节点、不能释放后继后再读取它，也要说明复制数据是 深复制还是只复制指针。
定理 / 命题
定理
搜索路径排除原理
在 BST 节点 v，如果目标键小于 v.key，它不可能在 v.right；如果
目标键较大，它不可能在 v.left。所以每次比较都可安全排除整棵子树。
定理
核心更新保持 BST 不变式
如果输入树的键互异并满足 BST 不变式，把新键插入第一个空搜索位置会保持 不变式；按照零子节点、一子节点或后继／前驱的两子节点规则删除，也会 保持不变式。
定理
依树高计算的成本
如果比较、指针读写及数据替换都是常数时间，搜索、极值、插入、后继及
删除均为 O(h)。在所有含 n 个节点的可能 BST 形状中，最坏情况为
O(n)。
证明思路
先证搜索。若目标小于当前键，不变式指出右子树所有键都更大，因此右侧 不可能相等；较大的情况对称。反复应用后，找到相等键自然正确，而在唯一 可行路径到达空树则证明键不存在。
插入不改动任何旧子树。此前每次比较都把新键限制在所有祖先传下来的正确 区间；最后一次比较又把新叶接到父节点的正确一侧，因此同时符合父节点及 所有祖先的界限。
删除零或一子节点时，只移走目标，存活键的相对顺序不变。两子节点时，令
s 为右子树最小值。原左子树所有键小于被删键，因而也小于 s；删除
s 的旧位置后，右子树余下所有键都严格大于新根键。前驱版本完全对称。
注意“复制后继”后还必须删除原后继，否则会破坏唯一性。
成本方面，每个程序只沿常数条祖先或后代路径前进，每条最多含 h 个
节点。两子节点删除虽然先找目标再到右子树找最小值，两段仍只是一条根到
叶路径的分段，总成本是 O(h)，不是 O(h²)。BST 不变式限制键的相对
位置，却不限制两侧高度；因此“是 BST”本身不保证对数高度。
例题详解
例题
建立教程中的 BST 并追踪搜索
依次插入 11, 6, 8, 19, 1, 13, 17, 42, 16。根为 11；左子树以
6 为根，左右为 1、8；右子树以 19 为根，右侧是 42，左侧是
以 13 为根、其右子节点为 17，而 17 的左子节点为 16。搜索 16 的路径为
11 -> 19 -> 13 -> 17 -> 16，方向依次右、左、右、左。最小值路径是
11 -> 6 -> 1，最大值路径是 11 -> 19 -> 42。成本由节点深度决定，
不是由键的数值距离决定。
例题
追踪三种后继结果
同一棵树中，13 有右子树，其最小节点 16 是后继。8 没有右子树；
向上先从 6 的右侧到达，须继续，再从 11 的左侧到达，所以后继为
11。42 没有右子树，也没有合格祖先，故后继是 NIL。
例题
用两种来源支持的策略删除 19
19 有两个子节点。使用前驱时，左子树最大值是 17；用 17 取代
19，再移走原来的 17，其左子节点 16 接到 13 的右侧。使用后继
时，右子树最小值是 42；用 42 取代 19，再移走原叶 42。两个
结果形状不同，但中序键序列都从 13, 16, 17, 19, 42 变为
13, 16, 17, 42：只删除目标，两者都保持不变式。
例题
相同键集合可以有完全不同的高度
插入 4, 2, 6, 1, 3, 5, 7，所得形状匀称，n = 7 而 h = 3。改为
插入 1, 2, 3, 4, 5, 6, 7，每个新键都成为右子节点，故 h = 7。
算法没有改变，但前一类形状的成本可以是 O(log n)，退化链则为 O(n)。
这只是比较树形，并没有假设或讲授平衡算法。
常见错误
常见错误
只检查直接子节点
左子节点较小、右子节点较大，不足以验证整棵 BST；每个后代都要满足所有 祖先界限。
常见错误
假设后继总在右子树
只有右子树非空时才取其最小值；否则答案可能是祖先，而最大节点没有后继。
常见错误
复制后继后忘记删除旧位置
两子节点删除不是复制数据就完成。如果不移走原后继或前驱，同一键会出现 两次。
常见错误
没有条件就声称 O(log n)
无条件结论是 O(h)；只有树高为对数级时才可改写为 O(log n)，退化树
有 h = n。
其他常见实现问题包括：递归后没有接回新的子树根、在空树上求极值、没有 定义重复键策略，以及删除时错误释放指针。
总结
- BST 不变式约束整棵子树，而不只约束相邻节点。
- 搜索每次排除一棵不可能的子树；极值沿最左或最右路径取得。
- 插入在失败搜索的第一个空位加入新叶。
- 后继是右子树最小值，或第一个从左分支到达的祖先。
- 删除分零、一、两个子节点；两子节点情况取后继或前驱并删除其旧位置。
- 每次更新都要证明祖先传下来的键值界限仍然成立。
- 核心操作为
O(h)：形状匀称时可为对数级，退化时为线性；本节不假设 平衡算法。
练习
思考检查
根为 20，左右子节点为 10、30，而 10 的右子节点是 25。为什么这不是 BST？
指出嵌套节点违反了哪一个祖先界限。
思考检查
节点 15 的右子树根为 20，且 20 的左子节点为 18。15 的后继是什么？
先判断结构情况，再比较候选键。
思考检查
在教程 BST 中追踪搜索 14 失败的路径，并指出插入位置。
从根开始记录每次比较，直至 NIL。
思考检查
为什么两子节点删除所取的右子树最小节点不可能有左子节点？
直接使用“最小”的定义论证。
思考检查
把 n 个互异键按严格递增顺序插入；求 h 及搜索最大值的成本。
先描述所得树形。
答案与解答
解答 · 解答 1
25 位于 20 的左子树，所以祖先界限要求它小于 20，但事实并非如此。
它大于直接父节点 10 并不能修补对根造成的违反。
解答 · 解答 2
15 有右子树，故取该子树最小值。从 20 向左到 18，答案是 18，
不是直接右子节点 20。
解答 · 解答 3
比较顺序为：14 大于 11、小于 19、大于 13、小于 17、再小于
16，然后到达 16 的空左子树。完整路径是
11 -> 19 -> 13 -> 17 -> 16 -> NIL，所以 14 应接成 16 的左子节点。
解答 · 解答 4
如果右子树最小节点 s 有左子节点，该左节点的键就比 s.key 更小，又仍
在同一右子树中，与 s 为最小值矛盾。
解答 · 解答 5
递增插入使每个新节点成为前一节点的右子节点，形成长链，故 h = n。
搜索最大值要访问全部 n 个节点，成本是 Theta(n)，符合一般 O(h)
上界。