1. 基本定义与记号

设 $T$ 为一棵元素两两不同二叉搜索树，所有键值两两不同。对任意键 $u$（上下文无歧义时亦指代其所在物理节点），定义删除操作如下。

定义 1.1（删除类型）
在树 $T$ 中删除键 $u$ 时：

  • 若 $u$ 对应的物理节点同时拥有左孩子和右孩子，则称删除类型为类型1，记为 $\operatorname{type}_T(u)=1$。
  • 否则（$u$ 至多有一个孩子），称删除类型为类型2，记为 $\operatorname{type}_T(u)=2$。

类型1的具体操作过程为：找到 $u$ 的后继 $s$（即 $u$ 右子树中的最小键），将 $s$ 的键值复制到 $u$ 的物理节点中，然后物理删除原 $s$ 节点，并用 $s$ 的右孩子（若存在）填补其位置。类型2的具体操作为：直接物理删除 $u$ 所在节点，并用其存在的唯一子节点（若存在）补位。

定义 1.2（影响）
在树 $T$ 中删除键 $u$ 时，若键 $v$（$v\neq u$）在操作后改变了所属的物理节点，则称删除键 $u$ 影响了键 $v$。

由删除操作的具体过程立即可得：

推论 1.1（不同删除类型的影响）
记键 $u$ 的后继为键 $v$（若存在），则在树 $T$ 中删除键 $u$ 时：

  • 若 $\operatorname{type}_T(u)=1$，则删除键 $u$ 仅影响键 $v$（键 $v$ 从原节点移至 $u$ 的节点位置）；
  • 若 $\operatorname{type}_T(u)=2$，则删除键 $u$ 不影响任何其他键（仅键 $u$ 本身被移除）。

定义 1.3（删除操作的可交换性）
对于两个不同的键 $a,b$，称在 BST $T$ 上删除 $a$ 与删除 $b$ 可交换，当且仅当在 $T$ 上先删 $a$ 后删 $b$ 得到的最终树，与先删 $b$ 后删 $a$ 得到的最终树形状完全相同（包括结构及每个节点存储的键值）。

由对称性，不妨考察先删 $a$ 对后删 $b$ 的影响。

记原树为 $T$，在 $T$ 上删除 $a$ 后的树为 $T’$。我们通过比较 $\operatorname{type}_T(b)$ 与 $\operatorname{type}_{T’}(b)$ 的四种可能组合进行分类讨论。

2. 分类论证

情形一：$\operatorname{type}_T(b)=\operatorname{type}_{T'}(b)=2$

此时 $b$ 在 $T$ 和 $T’$ 中均至多有一个孩子。

  • 若 $\operatorname{type}_T(a)=2$，由推论1.1，删除 $a$ 不影响任何其他键。因此 $b$ 的物理节点与结构完全未变，操作显然可交换。
  • 若 $\operatorname{type}_T(a)=1$，设 $a$ 的后继为 $s$。由推论1.1，删除 $a$ 仅影响 $s$，不影响其他键。于是：
    • 若 $b\neq s$，则 $b$ 不受任何影响，结构不变，操作可交换。
    • 若 $b=s$，则 $b$ 是被影响的唯一键。删除 $a$ 会将 $b$ 的键复制到 $a$ 处，并物理删除原 $b$ 节点。在 $T’$ 中，键 $b$ 位于原 $a$ 的物理位置，其左孩子为原 $a$ 的左子树（非空，因 $\operatorname{type}_T(a)=1$），右孩子为原 $a$ 右子树删除 $b$ 后的剩余部分。要使 $\operatorname{type}_{T’}(b)=2$，必须保证该节点至多一个孩子。由于左孩子非空，右孩子必须为空，这要求原 $a$ 的右子树仅由 $b$ 一个节点构成（且 $b$ 无右孩子）。此时 $b$ 恰为 $a$ 的右孩子且无子节点。

在此特定结构下，我们直接验证两种删除顺序的最终结果：

  • 先删 $a$ 后删 $b$：
    1. 删除 $a$（类型1）：将 $b$ 的键复制到 $a$ 的节点，并物理删除原 $b$ 节点（因 $b$ 无子节点，直接移除）。此时树中键 $b$ 位于原 $a$ 位置，其左孩子为原 $a$ 的左子树（记作 $L$），右孩子为空。
    2. 删除 $b$（此时键 $b$ 在 $T’$ 中类型为2，仅有一个左孩子 $L$）：直接删除该节点，并用其左孩子 $L$ 补位。最终树仅保留 $L$。
  • 先删 $b$ 后删 $a$：
    1. 删除 $b$（类型2，无孩子）：直接物理删除 $b$ 节点。此时 $a$ 的右孩子变为空，$a$ 成为仅有一个左孩子 $L$ 的节点（类型变为2）。
    2. 删除 $a$（此时类型为2）：直接删除 $a$ 节点，并用其左孩子 $L$ 补位。最终树同样仅保留 $L$。

两种顺序得到完全相同的树，故操作可交换。

综上，情形一中删除操作恒可交换。

情形二：$\operatorname{type}_T(b)=\operatorname{type}_{T'}(b)=1$

此时 $b$ 在 $T$ 和 $T’$ 中均有两个孩子。设 $c$ 为 $b$ 在 $T$ 中的后继（必在右子树中）。

  • 若 $a=c$，则删除 $a$ 时（由推论1.1）仅影响 $a$ 的后继（记为 $d$）。因 $\operatorname{type}_{T’}(b)=1$，$T’$ 中 $b$ 依然有右子树且后继为 $d$（否则 $b$ 的类型会改变）。无论先删 $a$ 后删 $b$，还是先删 $b$ 后删 $a$，最终物理移除的节点均为 $d$（或其等价节点），树形状一致，故可交换。
  • 若 $a\neq c$ 且 $a\neq b$，由推论1.1可知，删除 $a$ 仅可能影响 $a$ 的后继。因 $a$ 的后继不是 $b$ 也不是 $c$，故 $b$ 与 $c$ 均不受任何影响。加之 $\operatorname{type}_{T’}(b)=1$ 已保证 $b$ 的结构与后继均未改变，两种删除顺序互不干扰，可交换。

因此，情形二中删除操作恒可交换。

情形三：$\operatorname{type}_T(b)=2$，$\operatorname{type}_{T'}(b)=1$

即删除 $a$ 使 $b$ 从至多一个孩子变为有两个孩子。这只有在 $a$ 的删除操作为 $b$ “创造”了一个新的子树时才可能发生。由推论1.1，类型1的删除仅影响其后继；类型2的删除不影响任何键。因此，要使 $b$ 获得新的子树，唯一可能是：

$$ \operatorname{type}_T(a)=1 \quad \text{且} \quad b \text{ 恰为 } a \text{ 的后继}. $$

此时删除 $a$ 将 $b$ 的键复制到 $a$ 处，并物理删除原 $b$ 节点。在 $T’$ 中，键 $b$ 处于原 $a$ 的位置，继承了原 $a$ 的左子树（非空）和右子树删去 $b$ 后的剩余部分（因 $b$ 是后继，该剩余部分至少包含 $b$ 的右子树，故非空），从而获得两个孩子，类型变为1。

设 $c$ 为 $T$ 中 $b$ 的后继（此处 $b$ 在 $T’$ 中类型为1，故在 $T’$ 中 $b$ 有后继）。由结构可知，$c$ 必位于原 $a$ 的右子树中（否则 $T’$ 中 $b$ 的右子树为空，矛盾）。

比较两种删除顺序：

  • 先删 $a$ 后删 $b$：
    1. 删除 $a$：用 $b$ 覆盖 $a$ 并物理删除 $b$。
    2. 删除键 $b$（此时位于原 $a$ 处，类型1）：复制其后继 $c$ 的键并物理删除 $c$。
  • 先删 $b$ 后删 $a$：
    1. 删除 $b$（类型2）：直接物理删除并用子节点补位。此时 $a$ 的右子树失去 $b$（可能由 $b$ 的右子代替）。由于 $b$ 在 $T$ 中为 $a$ 右子树的最小键，且至多一个孩子，删除 $b$ 后 $a$ 的右子树剩余部分的最小键依然是 $c$。
    2. 删除 $a$（仍为类型1）：其后继仍为 $c$，于是复制 $c$ 的键并物理删除 $c$。

两种顺序最终物理删除的节点均为 $c$，树形状相同。故此情况操作可交换。

情形四：$\operatorname{type}_T(b)=1$，$\operatorname{type}_{T'}(b)=2$

即删除 $a$ 使 $b$ 从有两个孩子变为至多一个孩子。这要求删除 $a$ 的过程物理移除了 $b$ 的恰好一个孩子节点，且该孩子节点为单节点子树（即无子节点）。分两种子情形：

子情形4.1：被移除的是 $b$ 的右子树（唯一节点）

此时被删除的节点恰为 $b$ 的后继。要使删除 $a$ 能移除此节点，只能有 $a$ 就是该节点（即 $a$ 是 $b$ 的后继）。与情形三的镜像分析类似，两种删除顺序最终物理删除节点一致，操作可交换。

子情形4.2：被移除的是 $b$ 的左子树（唯一节点）

此时 $b$ 的左孩子 $L$ 为叶子节点，且 $a$ 的删除导致 $L$ 被物理删除（即 $a=L$ 或 $a$ 的后继为 $L$）。删除 $a$ 后，$b$ 失去左子树，仅剩右子树，类型变为2。

考察可交换性：在 $T$ 中 $b$ 为类型1，其后继 $s$ 必在右子树中。删除 $b$ 时将复制 $s$ 的键并物理删除 $s$。在先删 $a$ 后删 $b$ 的顺序中，$b$ 变为类型2，直接物理删除并用右孩子补位。为使两顺序结果相同，必须要求 $s$ 恰为 $b$ 的右孩子，且 $s$ 在物理删除后恰好占据 $b$ 的位置。这是因为：

  • 若 $s$ 不是右孩子（即右孩子有左子树），则先删 $b$ 会复制后继并物理删除 $s$ 的某个后裔，与先删 $a$ 后直接删除 $b$ 的效果不同（后者仅移除 $b$ 本身，右孩子直接上移）。
  • 若 $s$ 是右孩子，则类型1删除退化为：用右孩子的键覆盖 $b$ 并物理删除右孩子。这与先删 $a$ 使 $b$ 失去左孩子后再直接删除 $b$（用右孩子补位）的最终效果一致。

因此，在子情形4.2中，删除操作可交换当且仅当 $b$ 的后继恰为 $b$ 的右孩子。

综合子情形4.1（恒可交换）与子情形4.2（条件可交换），情形四中删除操作不可交换的充要条件是：

$$ \operatorname{type}_T(b)=1,\quad \operatorname{type}_{T'}(b)=2,\quad \text{且 } b \text{ 的后继不是 } b \text{ 的右孩子}. $$

3. 充要条件总结

综合以上四种情形的论证，得到本文的核心定理。

定理 3.1（两删除操作可交换的充要条件）
设 $T$ 为元素两两不同的 BST，$a,b$ 为两个不同键，记 $T’$ 为在 $T$ 上删除 $a$ 后所得之树。则删除 $a$ 与删除 $b$ 不可交换当且仅当：

  1. $\operatorname{type}_T(b)=1$；
  2. $\operatorname{type}_{T’}(b)=2$；
  3. 在 $T$ 中，$b$ 的中序后继不是 $b$ 的右孩子。

此时，删除 $a$ 的操作最终物理删除的节点恰为 $b$ 的左孩子（该左孩子为叶子节点，且是 $b$ 左子树中的唯一节点）。

推论 3.1（不可交换性的结构特征）
上述条件等价于：在 $T$ 中存在一个节点 $x$（对应 $b$）满足：

  • $x$ 有两个孩子；
  • $x$ 的左子树仅包含一个叶子节点 $y$（对应 $a$），且 $y$ 是 $x$ 的直接左孩子；
  • $x$ 的右孩子不是 $x$ 的后继（即右孩子有左子树）。

4. 树上删除操作可交换判定准则

在给出判定准则之前，我们需要两个关于二叉搜索树先序遍历的基本事实。

引理 4.1（BST 的先序唯一确定性）
设 $T_1$ 和 $T_2$ 是两棵元素两两不同的二叉搜索树。若 $T_1$ 与 $T_2$ 的先序遍历序列相同，则两棵树的结构完全相同（即对应节点位置一致，键值也相同）。

证明：对先序遍历序列的长度施归纳。空序列对应空树，唯一确定。对于非空序列 $x, L_{\text{pre}}, R_{\text{pre}}$，其中 $x$ 是根节点键值。根据 BST 的性质，先序序列中紧随 $x$ 之后且连续小于 $x$ 的一段为左子树的先序遍历 $L_{\text{pre}}$，剩余大于 $x$ 的一段为右子树的先序遍历 $R_{\text{pre}}$。这一划分由键值大小关系唯一确定。由归纳假设，左、右子树分别被 $L_{\text{pre}}$ 和 $R_{\text{pre}}$ 唯一确定。因此整棵树被先序序列唯一确定。∎

引理 4.2（先序遍历的子树隔离性质）
设 $T$ 为元素两两不同的 BST，$u$ 为 $T$ 中任意节点，记以 $u$ 为根的子树先序遍历序列为 $S$。则在 $T$ 的先序遍历中，紧接在 $S$ 之后出现的任意键值 $w$ 均满足 $w > \max(S)$。

证明：考虑 $T$ 的先序遍历过程：当访问节点 $u$ 时，进入以 $u$ 为根的子树，并按照“根-左-右”顺序完整遍历该子树后，递归返回至 $u$ 的某个祖先节点，随后转向该祖先的右子树继续遍历。设该祖先为 $v$（可能是 $u$ 自身或更高祖先），且 $u$ 位于 $v$ 的左子树中。则 $S$ 之后的第一个节点恰为 $v$ 的右孩子（若存在），或更远祖先的右子树节点。由于 BST 性质，$v$ 的右子树中所有键值均大于 $v$ 的键值，而 $v$ 的键值又大于其左子树（包含 $u$ 子树）中所有键值。因此，$S$ 之后的键值 $w$ 必然大于 $S$ 中的每一个键值。∎

基于推论3.1的结构特征以及上述引理，我们现在可以用先序遍历的后缀形式给出简洁判定。

定理 4.1（基于先序遍历的树上删除操作可交换判定准则）
在元素两两不同的 BST $T$ 中，存在两个键使得删除操作不可交换，当且仅当 $T$ 的先序遍历序列存在一个形如

$$ x,\ y,\ s_1,\ s_2,\ \dots,\ s_n $$

的后缀，满足：

  1. 对所有 $i=1,\dots,n$，有 $s_i > x > y$；
  2. $x$ 的中序后继在集合 ${s_1,\dots,s_n}$ 中；
  3. $s_1$ 不是 ${s_1,\dots,s_n}$ 中的最小值。

证明：

  • 必要性：若存在不可交换的删除对，由推论3.1，树中含有节点 $x$（即 $b$）满足：$x$ 有左叶子 $y$，右子树非空且右孩子 $s_1$ 不是后继。在先序遍历中，访问顺序为“根 → 左子树 → 右子树”。因此 $y$ 紧接 $x$ 之后访问；随后是右子树的先序序列 $s_1,s_2,\dots,s_n$。由引理4.2，$S = {x, y, s_1,\dots,s_n}$ 是 $x$ 子树的先序遍历，其后继元素均大于 $x$，特别地 $s_i > x$；而 $y$ 是 $x$ 的左孩子，故 $x > y$，因此条件1成立。$x$ 的后继必为右子树中最小键，故在 ${s_i}$ 中，条件2成立。而 $s_1$ 不是最小值等价于右孩子存在左子树，即右孩子不是后继，条件3成立。
  • 充分性：若先序序列存在满足条件的后缀 $x,y,s_1,\dots,s_n$。根据 BST 先序遍历的性质（引理4.1保证了由先序序列可唯一还原树结构）：紧接在 $x$ 之后且小于 $x$ 的元素 $y$ 必为 $x$ 的左孩子；由引理4.2，后续元素 $s_1,\dots,s_n$ 均大于 $x$，因此它们构成 $x$ 的右子树的先序遍历，其中 $s_1$ 为右孩子。条件2确保 $x$ 有后继且在右子树中；条件3表明 $s_1$ 不是最小值，故右孩子存在左子树，即后继非右孩子。此外，$y$ 后直接转入右子树序列，表明 $y$ 无左、右子树（否则其子树节点会插入在 $y$ 与 $s_1$ 之间），因此 $y$ 为叶子且为 $x$ 左子树唯一节点。取 $a=y$，$b=x$，则 $\operatorname{type}_T(b)=1$，$\operatorname{type}_{T’}(b)=2$，且后继非右孩子，由定理3.1知删除操作不可交换。∎

5. 删除策略采用前驱替代时的对应结论

若 BST 的删除操作在节点有两个孩子时采用中序前驱（即左子树中的最大键）替代被删节点，则前述结论有完全对称的版本。

记 $\operatorname{type}^*_T(u)$ 为使用前驱替代时的删除类型（定义与前述类似，仅将后继换为前驱）。对于两个不同键 $a,b$，删除操作不可交换的充要条件为：

  1. $\operatorname{type}_T(b)=1$（$b$ 原有两个孩子）；
  2. 在 $T$ 上删除 $a$ 后，$b$ 的类型变为 $2$（即 $b$ 失去恰好一个孩子）；
  3. 在 $T$ 中，$b$ 的中序前驱不是 $b$ 的左孩子。

此时，先删除 $a$ 的操作最终物理删除的节点恰为 $b$ 的右孩子（该右孩子为叶子节点，且是 $b$ 右子树中的唯一节点）。

相应地，基于后序遍历序列可给出类似的模式判据：存在不可交换对当且仅当后序遍历序列中存在形如 $s_1,\dots,s_n, y, x$ 的前缀，满足 $s_i < x < y$，且 $x$ 的前驱在 ${s_i}$ 中，且 $s_n$ 不是 ${s_i}$ 中的最大值。