二分搜索树节点删除
关键点
- 研究表明，二分搜索树节点删除有三种主要情况：删除叶子节点、删除有单子节点的节点和删除有双子节点的节点。
- 证据倾向于通过替换后继节点或前驱节点来处理双子节点删除，但具体选择可能因实现而异。
- 删除操作需确保树的性质不变：左子树节点小于当前节点，右子树节点大于当前节点。
删除叶子节点
如果要删除的节点是叶子节点（没有子节点），可以直接删除该节点，因为它不会影响其他节点的结构。例如，在树中删除一个孤立的节点，只需将其父节点的指针设置为 null。
删除有单子节点的节点
如果节点只有一个子节点（左子节点或右子节点），则用其子节点替换该节点的位置。例如，如果删除的节点有右子节点，则父节点指向该右子节点，删除原节点。
删除有双子节点的节点
如果节点有两个子节点（左子节点和右子节点），需要找到后继节点（右子树的最小节点）或前驱节点（左子树的最大节点），用其值替换要删除的节点，然后删除后继或前驱节点（此时该节点最多只有一个子节点，可简化为前两种情况）。
详细报告
背景与定义
二分搜索树（Binary Search Tree，BST）是一种满足特定条件的二叉树：每个节点的左子树中所有节点的值都小于该节点，右子树中所有节点的值都大于该节点，且左右子树本身也是二分搜索树。删除节点是 BST 的一项核心操作，需确保删除后树的性质不变。
根据研究，删除节点通常分为三种情况：删除叶子节点、删除有单子节点的节点和删除有双子节点的节点。以下是详细分析和解释，涵盖所有相关信息。
删除节点的三种情况
- 删除叶子节点（没有子节点）：
– 如果要删除的节点是叶子节点（即没有左子节点也没有右子节点），可以直接删除该节点。
– 操作：将父节点的指针指向 null，删除该节点。
– 例如，在树中删除一个孤立的节点（如值为 2 的叶子节点），只需将其从树中移除，不会影响其他节点。
– 这种情况下，树的结构变化最小，删除操作简单。 - 删除有单子节点的节点：
– 如果节点只有一个子节点（左子节点或右子节点），则用其子节点替换该节点的位置。
– 操作：将父节点指向该子节点，删除原节点。
– 如果该节点是根节点，则新的根节点为该子节点。
– 例如，假设节点值为 5，有右子节点 6，删除 5 后，父节点指向 6，树结构调整为以 6 为根。
– 这种情况下，需确保替换后仍满足 BST 的性质，即子节点的取值范围正确。 - 删除有双子节点的节点：
– 如果节点有两个子节点（左子节点和右子节点），直接删除会破坏树的结构。
– 解决方案：找到该节点的后继节点（右子树中的最小节点）或前驱节点（左子树中的最大节点），用其值替换要删除的节点，然后删除后继或前驱节点。
– 后继节点的选择：遍历右子树，找到最左边的节点（最小值），因为它是右子树中第一个大于当前节点的值。
– 前驱节点的选择：遍历左子树，找到最右边的节点（最大值），因为它是左子树中最后一个小于当前节点的值。
– 删除后继或前驱节点时，由于它们最多只有一个子节点（因为它们是极值节点），可以简化为前两种情况。
– 例如，假设节点值为 5，左子树为 3，右子树为 6，删除 5 时，可用 6（后继）替换，然后删除 6（此时 6 可能为叶子或有单子节点）。
特殊情况
- 删除根节点： 如果要删除的节点是根节点，则需更新树的根节点。例如，删除根节点后，如果有单子节点，新的根为该子节点；如果有双子节点，则需找到后继或前驱节点作为新根。
- 节点不存在： 如果树中不存在要删除的节点，则操作无效，树保持不变。
示例分析
为了更直观地理解，以下是一个具体示例。假设树的结构如下：
5
/ \
3 6
/ \ \
2 4 7- 删除节点 3（有两个子节点）：
– 找到后继节点：右子树（以 4 为根）的最小节点为 4。
– 将节点 3 的值替换为 4。
– 然后删除节点 4（此时 4 是叶子节点）。
– 结果树为：
5 / \ 4 6 / \ 2 7 - 删除节点 2（叶子节点）：
– 直接删除节点 2。
– 结果树为：
5 / \ 3 6 \ \ 4 7 - 删除节点 6（只有一个子节点）：
– 将节点 6 的父节点（即根节点 5）指向节点 6 的右子节点（即 7）。
– 结果树为：
5 / \ 3 7 / \ 2 4
实现与特性
删除操作可以通过递归或迭代实现。递归方式通常更直观，但可能因栈深度导致空间复杂度较高。迭代方式使用栈或队列，适合内存受限的场景。研究表明，删除操作的时间复杂度为 O(h)，其中 h 是树的高度，平均情况下为 O(log n)，最坏情况下为 O(n)（当树退化为链表时）。
应用场景与争议
证据倾向于后继节点法（用右子树最小值替换）在实现中更常见，因为它直观且易于理解。前驱节点法（用左子树最大值替换）也同样有效，但使用较少。关于哪种方法更优，研究表明这取决于具体实现和性能需求，目前没有绝对共识。选择后继节点法时，需注意右子树可能为空；选择前驱节点法时，需注意左子树可能为空。
表格总结
以下表格总结了三种删除情况的特点与操作：
| 删除情况 | 操作描述 | 示例 | 复杂度 |
|---|---|---|---|
| 叶子节点（无子节点） | 直接删除，父节点指针设为 null | 删除节点 2 | O(h) |
| 单子节点（一个子节点） | 用子节点替换，父节点指向子节点 | 删除节点 6，替换为 7 | O(h) |
| 双子节点（两个子节点） | 用后继/前驱替换值，然后删除后继/前驱节点 | 删除节点 3，用 4 替换 | O(h) |
注：h 为树的高度，n 为节点总数。
参考资料
总结
二分搜索树节点删除分为三种情况：删除叶子节点、删除有单子节点的节点和删除有双子节点的节点。删除操作需确保树的性质不变，通常通过替换后继节点或前驱节点来处理双子节点情况。研究表明，删除操作的时间复杂度为 O(h)，平均为 O(log n)，最坏为 O(n)。选择后继或前驱节点法可能因实现而异，但后继节点法更常见。