二叉搜索树（BST）的查找、插入与删除操作
字数 2051 2025-11-03 00:19:05

二叉搜索树（BST）的查找、插入与删除操作

二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。这个性质使得二叉搜索树在查找、插入和删除操作上非常高效。

1. 查找操作

  • 目标：在二叉搜索树中查找一个特定的值。

  • 过程：利用BST的性质，我们可以快速缩小搜索范围。

    1. 从根节点开始：将目标值与根节点的值进行比较。
    2. 如果相等：恭喜，查找成功。
    3. 如果目标值小于根节点的值：说明目标值只可能存在于根节点的左子树中（如果存在的话）。于是，我们递归地在左子树中继续查找。
    4. 如果目标值大于根节点的值：说明目标值只可能存在于根节点的右子树中。于是，我们递归地在右子树中继续查找。
    5. 遇到空节点：如果在查找过程中，我们根据比较结果需要进入一个子节点，但这个子节点是空的（null），则说明树中不存在我们要找的值，查找失败。

  • 示例：在下图的BST中查找值 8。

          10
    /    \
   5      15
  / \    /  \
 3   7  12  18
    /
   8
    • 从根节点 10 开始，8 < 10，进入左子树。
    • 当前节点是 5，8 > 5，进入右子树。
    • 当前节点是 7，8 > 7，进入右子树。
    • 当前节点是 8，相等，查找成功。

2. 插入操作

  • 目标：将一个不存在于树中的新值插入到BST的正确位置，并保持BST的性质。

  • 过程：插入操作与查找操作非常相似。我们首先要找到新节点应该被放置的位置。这个位置必然是某个叶子节点的空子节点位置。

    1. 从根节点开始比较：将新节点的值与当前节点比较。
    2. 如果新值小于当前节点的值：
      • 如果当前节点的左子节点为空，就将新节点作为左子节点插入。
      • 如果左子节点不为空，则递归地在左子树中继续执行插入操作。
    3. 如果新值大于当前节点的值：
      • 如果当前节点的右子节点为空，就将新节点作为右子节点插入。
      • 如果右子节点不为空，则递归地在右子树中继续执行插入操作。
    4. 注意：如果新值等于当前节点的值，根据具体实现，可以选择不允许重复值（忽略插入），或将新节点插入为右子节点（或左子节点）等。通常BST不包含重复值。

  • 示例：向一个空树中依次插入 10, 5, 15, 3, 7, 12, 18, 8，最终形成的树就是上面示例中的树。

3. 删除操作

  • 目标：从BST中删除一个指定的节点，并保持BST的性质。这是三个操作中最复杂的一个，因为被删除的节点可能有零个、一个或两个子节点。我们需要分三种情况讨论。

  • 过程：

    1. 定位要删除的节点：首先，使用查找算法找到要删除的节点，记为 node。
    2. 根据 node 的子节点情况处理：

      • 情况一：node 是叶子节点（没有子节点）

        • 这是最简单的情况。直接将其父节点指向它的指针设置为 null 即可。
        • 示例：删除节点 3。只需将节点 5 的左指针设为 null。

      • 情况二：node 只有一个子节点

        • 让 node 的父节点绕过 node，直接指向 node 的唯一那个子节点。
        • 示例：删除节点 7（它有一个左子节点 8）。
          • 找到节点 7 的父节点 5。
          • 让 5 的右指针（原来指向 7）改为指向 7 的左子节点 8。
          • 这样，节点 7 就被从树中移除，它的子节点 8 接替了它的位置。

      • 情况三：node 有两个子节点

        • 这是最复杂的情况。我们不能简单地删除它，因为会留下两个子树需要连接。我们的策略是：
          a. 寻找替代者：在 node 的右子树中，找到值最小的节点（这个节点称为 node 的中序遍历后继节点）。根据BST的性质，这个节点是大于 node 值的最小节点。同样，你也可以选择 node 的左子树中值最大的节点（中序遍历前驱节点）。
          b. 复制值：将找到的这个后继节点（或前驱节点）的值复制到 node 中，覆盖掉 node 原来的值。
          c. 删除后继节点：现在，问题转化为删除那个后继节点（或前驱节点）。而这个节点最多只有一个子节点（因为它是右子树中的最小节点，所以它不可能有左子节点；同理，左子树的最大节点不可能有右子节点），这就回到了情况一或情况二，我们可以轻松删除它。
        • 示例：删除根节点 10。
          • 节点 10 有两个子节点。
          • 在它的右子树（以 15 为根）中寻找最小的节点。这个节点是 12（它没有左子节点）。
          • 将 10 的值替换为 12。
          • 现在，原树中出现了两个 12。我们需要删除右子树中原来的那个 12。这个节点只有一个右子节点（或者没有，本例中没有），按照情况二删除它即可。最终，树的结构仍然满足BST的性质。

通过掌握查找、插入和删除这三个核心操作，你就掌握了二叉搜索树的基本工作原理。这些操作的平均时间复杂度都是 O(log n)，其中 n 是树中节点的个数，这使得BST成为一种非常实用的数据结构。

二叉搜索树（BST）的查找、插入与删除操作 二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。这个性质使得二叉搜索树在查找、插入和删除操作上非常高效。 1. 查找操作 目标 ：在二叉搜索树中查找一个特定的值。 过程 ：利用BST的性质，我们可以快速缩小搜索范围。 从根节点开始 ：将目标值与根节点的值进行比较。 如果相等 ：恭喜，查找成功。 如果目标值小于根节点的值 ：说明目标值只可能存在于根节点的左子树中（如果存在的话）。于是，我们递归地在左子树中继续查找。 如果目标值大于根节点的值 ：说明目标值只可能存在于根节点的右子树中。于是，我们递归地在右子树中继续查找。 遇到空节点 ：如果在查找过程中，我们根据比较结果需要进入一个子节点，但这个子节点是空的（ null ），则说明树中不存在我们要找的值，查找失败。 示例 ：在下图的BST中查找值 8 。 从根节点 10 开始， 8 < 10 ，进入左子树。 当前节点是 5 ， 8 > 5 ，进入右子树。 当前节点是 7 ， 8 > 7 ，进入右子树。 当前节点是 8 ，相等，查找成功。 2. 插入操作 目标 ：将一个不存在于树中的新值插入到BST的正确位置，并保持BST的性质。 过程 ：插入操作与查找操作非常相似。我们首先要找到新节点应该被放置的位置。这个位置必然是某个叶子节点的空子节点位置。 从根节点开始比较 ：将新节点的值与当前节点比较。 如果新值小于当前节点的值 ： 如果当前节点的左子节点为空，就将新节点作为左子节点插入。 如果左子节点不为空，则递归地在左子树中继续执行插入操作。 如果新值大于当前节点的值 ： 如果当前节点的右子节点为空，就将新节点作为右子节点插入。 如果右子节点不为空，则递归地在右子树中继续执行插入操作。 注意 ：如果新值等于当前节点的值，根据具体实现，可以选择不允许重复值（忽略插入），或将新节点插入为右子节点（或左子节点）等。通常BST不包含重复值。 示例 ：向一个空树中依次插入 10, 5, 15, 3, 7, 12, 18, 8 ，最终形成的树就是上面示例中的树。 3. 删除操作 目标 ：从BST中删除一个指定的节点，并保持BST的性质。这是三个操作中最复杂的一个，因为被删除的节点可能有零个、一个或两个子节点。我们需要分三种情况讨论。 过程 ： 定位要删除的节点 ：首先，使用查找算法找到要删除的节点，记为 node 。 根据 node 的子节点情况处理 ： 情况一： node 是叶子节点（没有子节点） 这是最简单的情况。直接将其父节点指向它的指针设置为 null 即可。 示例 ：删除节点 3 。只需将节点 5 的左指针设为 null 。 情况二： node 只有一个子节点 让 node 的父节点绕过 node ，直接指向 node 的唯一那个子节点。 示例 ：删除节点 7 （它有一个左子节点 8 ）。 找到节点 7 的父节点 5 。 让 5 的右指针（原来指向 7 ）改为指向 7 的左子节点 8 。 这样，节点 7 就被从树中移除，它的子节点 8 接替了它的位置。 情况三： node 有两个子节点 这是最复杂的情况。我们不能简单地删除它，因为会留下两个子树需要连接。我们的策略是： a. 寻找替代者 ：在 node 的 右子树 中，找到 值最小的节点 （这个节点称为 node 的 中序遍历后继节点 ）。根据BST的性质，这个节点是大于 node 值的最小节点。同样，你也可以选择 node 的 左子树中值最大的节点 （中序遍历前驱节点）。 b. 复制值 ：将找到的这个后继节点（或前驱节点）的值 复制 到 node 中，覆盖掉 node 原来的值。 c. 删除后继节点 ：现在，问题转化为删除那个后继节点（或前驱节点）。而这个节点 最多只有一个子节点 （因为它是右子树中的最小节点，所以它不可能有左子节点；同理，左子树的最大节点不可能有右子节点），这就回到了情况一或情况二，我们可以轻松删除它。 示例 ：删除根节点 10 。 节点 10 有两个子节点。 在它的右子树（以 15 为根）中寻找最小的节点。这个节点是 12 （它没有左子节点）。 将 10 的值替换为 12 。 现在，原树中出现了两个 12 。我们需要删除右子树中原来的那个 12 。这个节点只有一个右子节点（或者没有，本例中没有），按照情况二删除它即可。最终，树的结构仍然满足BST的性质。 通过掌握查找、插入和删除这三个核心操作，你就掌握了二叉搜索树的基本工作原理。这些操作的平均时间复杂度都是 O(log n)，其中 n 是树中节点的个数，这使得BST成为一种非常实用的数据结构。