二叉搜索树删除操作：选后继还是前驱节点替换？

删除是二叉搜索树（Binary Search Tree，简称BST）中实现复杂度最高的操作，编码时需要覆盖三类处理场景：

• 待删除节点为叶子节点：直接移除节点即可，无需额外调整树结构
• 待删除节点仅有一个子节点：直接将子节点挂载到待删节点的父节点对应位置，替换待删节点即可
• 待删除节点同时拥有左右子节点：需要选取符合BST排序性质的节点替换待删节点，是整个删除逻辑的核心难点

对于第三类双孩子节点的删除场景，绝大多数入门教材和公开资料给出的标准方案是后继节点替换法：定位到待删节点右子树中的最小值节点——也就是待删节点的中序后继（Successor），用该节点的值覆盖待删节点的存储值，再递归从右子树中删除这个被移走值的最小值节点。

常见疑问解答 #

1. 用前驱节点替换是否可行？
   完全可行。待删节点的中序前驱（Predecessor）是其左子树中的最大值节点，选取前驱节点覆盖待删节点值、再从左子树中删除该最大值节点的逻辑，完全满足BST的中序有序性质，和后继替换法的逻辑有效性没有差异。以《数据结构与算法分析：C语言描述》（Data structure and algorithm analysis in C）中删除值为2的节点的示例来说，用后继节点3替换、用前驱节点1替换，得到的都是合法的BST结构。
2. 为什么多数资料很少提及前驱替换方案？
   不存在技术层面的排他性原因，只是入门教学阶段为了降低理解成本，通常会统一选取一种方案作为标准示例讲解，两种方案没有行业通用的强制约定。
3. 单次删除存在两种合法结果时，如何保证实现一致性？
   只要在同一份BST实现中固定使用同一种替换策略即可——要么全程采用后继替换，要么全程采用前驱替换，固定策略后就不会破坏BST的核心性质，也能保证所有操作逻辑自洽。

补充说明：如果长期执行O(n²)量级的随机插入、删除操作，且始终固定使用同一种替换策略，会逐步导致树结构失衡。比如始终采用后继替换策略，长期操作后树的左子树深度会明显大于右子树，最终让BST的操作时间复杂度从理想的O(logn)退化到接近O(n)。这个缺陷正是平衡搜索树（balanced search tree）概念提出的核心动因，AVL树就是这类平衡搜索树的典型实现。

内容的提问来源于stack exchange，提问作者Chris Bao