目录

  1. 删除操作的基本概念
  2. 删除操作的步骤
  3. 时间复杂度分析
  4. 代码示例（伪代码）
  5. 参考资料

1. 删除操作的基本概念

在二分搜索树中，删除操作的目标是移除指定值的节点，同时保持 BST 的性质（左子树值 < 当前节点值 < 右子树值）。删除操作比插入和查找复杂，因为需要处理不同的节点情况，并确保树结构完整。

2. 删除操作的步骤

删除一个值 value 的过程如下：

  1. 查找目标节点：
  • 从根节点开始，比较 value 与当前节点值，进入左子树（若小于）或右子树（若大于），直到找到目标节点或确认不存在。
  1. 处理三种情况：
  • 情况 1：无子节点（叶子节点）：
    • 直接删除该节点，将父节点的对应指针置为 null。
  • 情况 2：只有一个子节点：
    • 用子节点替换当前节点（将子节点链接到父节点）。
  • 情况 3：有两个子节点：
    • 找到右子树的最小节点（后继，通常是最左节点）或左子树的最大节点（前驱）。
    • 用后继/前驱的值替换当前节点值。
    • 递归删除后继/前驱

节点（通常是情况 1 或 2）。

  1. 返回更新后的树：
  • 调整指针后返回根节点。

示例

删除值 3：

    5
   / \
  3   7
 / \
1   4
  • 找到节点 3，有两个子节点（1 和 4）。
  • 取右子树 4 的最小值（即 4 本身）。
  • 用 4 替换 3，删除 4。
  • 结果：
    5
   / \
  4   7
 /
1

3. 时间复杂度分析

  • 平均情况：O(log n)
  • 当树较平衡时，高度约为 log n，查找和调整都在此范围内。
  • 最差情况：O(n)
  • 当树退化为线性结构，高度为 n，需遍历整棵树。
  • 空间复杂度：O(h)
  • 递归实现需要栈空间，h 为树高，平均 O(log n)，最差 O(n)。

4. 代码示例（伪代码）

class Node:
    value         // 节点值
    left          // 左子节点
    right         // 右子节点

class BST:
    root          // 根节点

    // 删除
    function delete(value):
        root = deleteRec(root, value)

    function deleteRec(node, value):
        if node is null:
            return null
        if value < node.value:
            node.left = deleteRec(node.left, value)
        else if value > node.value:
            node.right = deleteRec(node.right, value)
        else:
            // 情况 1：无子节点
            if node.left is null and node.right is null:
                return null
            // 情况 2：只有一个子节点
            else if node.left is null:
                return node.right
            else if node.right is null:
                return node.left
            // 情况 3：有两个子节点
            else:
                successor = minValue(node.right)
                node.value = successor.value
                node.right = deleteRec(node.right, successor.value)
        return node

    function minValue(node):
        current = node
        while current.left is not null:
            current = current.left
        return current

5. 参考资料

如果你需要特定语言的实现代码（如 Python、Java）或对删除操作有进一步疑问，请告诉我！