目录

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

1. 插入操作的基本概念

在二分搜索树中，插入操作的目标是将一个新节点添加到树中，同时保持 BST 的性质：

  • 左子树的所有节点值小于当前节点值。
  • 右子树的所有节点值大于当前节点值。

插入操作通常从根节点开始，通过比较新值与当前节点值，递归或迭代地找到合适的插入位置。新节点总是作为叶子节点插入。

2. 插入操作的步骤

插入一个值 value 到 BST 的过程如下：

  1. 从根节点开始：
  • 如果树为空（根节点为 null），直接创建新节点作为根节点。
  1. 比较值：
  • 如果 value 小于当前节点值，进入左子树。
  • 如果 value 大于当前节点值，进入右子树。
  • 如果允许重复值，可约定放入左子树或右子树（通常假设无重复值）。
  1. 递归或迭代：
  • 重复步骤 2，直到找到一个空位置（即当前节点为 null）。
  1. 插入新节点：
  • 在空位置创建新节点，并将其链接到父节点。

示例

插入序列 [5, 3, 7, 1, 4]：

  • 插入 5：树为空，5 成为根节点。
  • 插入 3：3 < 5，插入到 5 的左子节点。
  • 插入 7：7 > 5，插入到 5 的右子节点。
  • 插入 1：1 < 5，进入左子树，1 < 3，插入到 3 的左子节点。
  • 插入 4：4 < 5，进入左子树，4 > 3，插入到 3 的右子节点。

结果树：

    5
   / \
  3   7
 / \
1   4

3. 时间复杂度分析

  • 平均情况：O(log n)
  • 当树较平衡时，高度约为 log n，每次比较将搜索范围减半。
  • 最差情况：O(n)
  • 当树退化为线性结构（如有序插入 [1, 2, 3, 4, 5]），高度为 n，插入需遍历整棵树。
  • 空间复杂度：O(h)
  • 递归实现需要栈空间，h 为树高。

4. 代码示例（伪代码）

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

class BST:
    root          // 根节点

    // 插入（递归实现）
    function insert(value):
        root = insertRec(root, value)

    function insertRec(node, value):
        if node is null:
            return new Node(value)
        if value < node.value:
            node.left = insertRec(node.left, value)
        else if value > node.value:
            node.right = insertRec(node.right, value)
        return node

    // 插入（迭代实现）
    function insertIter(value):
        if root is null:
            root = new Node(value)
            return
        current = root
        while true:
            if value < current.value:
                if current.left is null:
                    current.left = new Node(value)
                    break
                current = current.left
            else if value > current.value:
                if current.right is null:
                    current.right = new Node(value)
                    break
                current = current.right

5. 参考资料

如果你需要特定语言的实现代码或对插入操作有进一步疑问，请告诉我！