二叉搜索树（BST）的插入操作详解

知识点描述
二叉搜索树（Binary Search Tree, BST）是一种经典的数据结构，它在二叉树的基础上增加了有序性约束。其核心特性是：对于树中的任意节点，其左子树中的所有节点值都小于该节点的值，其右子树中的所有节点值都大于该节点的值。BST 的插入操作是在保持这一性质的前提下，将新节点添加到树中的合适位置，使得插入后树仍是一棵二叉搜索树。理解插入操作是掌握 BST 各种操作（如搜索、删除、遍历）的基础。

详细解题过程
我们按照从核心概念到具体步骤，再到边界情况与复杂度的顺序，逐步讲解 BST 的插入操作。

1. 回顾 BST 的基本性质

• 每个节点包含：值（key）、指向左子节点的指针、指向右子节点的指针。
• 有序性：对于节点 node，有 node.left.key < node.key < node.right.key（假设所有值互异，若存在重复值，可约定左子树 ≤ 或右子树 ≥，但标准 BST 通常不允许重复）。
• 中序遍历 BST 会得到一个升序序列。

2. 插入操作的核心思想
插入新节点时，需要从根节点开始，将新节点的值与当前节点比较，根据比较结果决定向左子树还是右子树移动，直到找到一个“空位”（即到达一个空节点，本应作为某个节点的子节点的位置），将新节点作为该空位的子节点插入。这个过程本质上是“搜索”插入位置。

3. 插入步骤详解
假设我们要插入一个新值 val，树可能为空（即根节点为 null）。

步骤 1：处理空树
如果当前树为空（没有根节点），则直接创建一个新节点作为根节点，插入完成。这是最简单的情况。

步骤 2：递归（或迭代）寻找插入位置
如果树不为空，我们从根节点开始，将 val 与当前节点的值比较：

• 如果 val 小于当前节点的值，那么新节点应插入当前节点的左子树中。
  • 如果左子节点为空，则创建新节点作为左子节点，插入完成。
  • 如果左子节点不为空，则以左子节点为新的当前节点，重复此比较过程（即递归或迭代进入左子树）。
• 如果 val 大于当前节点的值，那么新节点应插入当前节点的右子树中。
  • 如果右子节点为空，则创建新节点作为右子节点，插入完成。
  • 如果右子节点不为空，则以右子节点为新的当前节点，重复此比较过程（即递归或迭代进入右子树）。
• 如果 val 等于当前节点的值，根据具体实现决定：可以不允许插入（直接返回），或将重复值插入到左子树（或右子树）中（但需注意，这会破坏严格的有序性，通常不推荐）。

步骤 3：递归实现示例
递归实现代码清晰，易于理解。递归函数 insert(node, val) 表示在以 node 为根的子树中插入 val，并返回插入后子树的根节点。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    # 步骤1：如果当前子树为空，创建新节点并返回
    if root is None:
        return TreeNode(val)
    
    # 步骤2：根据比较结果，递归插入到左子树或右子树
    if val < root.val:
        # 递归插入左子树，并将返回的新左子树根节点连接回来
        root.left = insert(root.left, val)
    elif val > root.val:
        # 递归插入右子树，并将返回的新右子树根节点连接回来
        root.right = insert(root.right, val)
    # 如果 val == root.val，这里选择不做任何操作（不允许重复值）
    
    # 返回当前子树的根节点（可能是原来的 root，也可能是新创建的节点）
    return root

步骤 4：迭代实现示例
迭代实现避免了递归的调用栈开销，通常效率稍高，但代码稍复杂。我们需要手动维护当前节点指针，并记录当前节点的父节点，以便在找到空位时能正确连接。

def insert_iterative(root, val):
    new_node = TreeNode(val)
    
    # 步骤1：空树情况
    if root is None:
        return new_node
    
    current = root
    parent = None
    
    # 步骤2：迭代寻找插入位置
    while current is not None:
        parent = current
        if val < current.val:
            current = current.left
        elif val > current.val:
            current = current.right
        else:
            # 值已存在，直接返回原树（不允许重复）
            return root
    
    # 此时 current 为 None，parent 是待插入位置的父节点
    if val < parent.val:
        parent.left = new_node
    else:
        parent.right = new_node
    
    return root

4. 插入操作的边界情况与注意事项

• 空树：如步骤1，直接创建根节点。
• 重复值：需明确处理策略。常见做法是禁止插入（保持值唯一），或允许插入但定义好顺序（如插入右子树，但后续搜索、删除会复杂）。
• 插入顺序影响树形状：如果插入的序列是有序的（如 1, 2, 3, 4, 5），BST 会退化成一条链（类似链表），此时插入、搜索的时间复杂度退化为 O(n)。理想情况下，随机插入序列形成的树是平衡的，时间复杂度为 O(log n)。因此，在实际应用中，常使用平衡二叉搜索树（如 AVL 树、红黑树）来保证性能。

6. 时间复杂度与空间复杂度分析

• 时间复杂度：平均情况 O(log n)，最坏情况（退化成链） O(n)，其中 n 是树中节点数。每次插入都需要从根节点走到一个叶子节点的空位，路径长度即比较次数。
• 空间复杂度：
  • 递归实现：平均 O(log n) 的递归栈空间，最坏 O(n)。
  • 迭代实现：O(1) 额外空间（只用了几个指针）。

总结
BST 的插入操作是基础且重要的操作，核心在于利用有序性，通过比较值的大小逐步向下搜索，直到找到合适空位插入。递归实现简洁，迭代实现高效。理解插入操作是后续学习 BST 删除、平衡调整等高级主题的基石。实际应用中，需注意插入顺序可能导致的树不平衡问题，必要时需使用自平衡 BST 变种。