二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种基于二叉树的非线性数据结构，具有高效的查找、插入和删除操作特性。其核心特点是：对于任意节点，其左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值。这一特性使得BST在动态数据管理中广泛应用，如数据库索引、内存分配等场景。

基本性质

二叉搜索树满足以下性质： 1. 有序性：若左子树非空，则左子树所有节点的值 $<$ 根节点的值；若右子树非空，则右子树所有节点的值 $>$ 根节点的值。 2. 递归性：左右子树也分别为二叉搜索树。 3. 无重复值（通常约定，部分实现允许重复需额外定义规则）。

示例结构

图中展示的BST满足：每个节点的左子树值更小，右子树值更大。*

核心操作

查找

从根节点开始，递归比较目标值与当前节点： - 若相等，返回节点； - 若目标值更小，进入左子树； - 若目标值更大，进入右子树； - 若子树为空，说明值不存在。

  
def search(root, target):  
    if not root or root.val == target:  
        return root  
    if target < root.val:  
        return search(root.left, target)  
    return search(root.right, target)

插入

类似查找，但需在空位置创建新节点：

  
def insert(root, val):  
    if not root:  
        return TreeNode(val)  
    if val < root.val:  
        root.left = insert(root.left, val)  
    else:  
        root.right = insert(root.right, val)  
    return root

删除

分三种情况处理： 1. 叶子节点：直接删除。 2. 单子节点：用子节点替换自身。 3. 双子节点：找到右子树的最小节点（或左子树的最大节点）替换自身，再递归删除该节点。

  
def delete(root, val):  
    if not root:  
        return None  
    if val < root.val:  
        root.left = delete(root.left, val)  
    elif val > root.val:  
        root.right = delete(root.right, val)  
    else:  
        if not root.left:  
            return root.right  
        if not root.right:  
            return root.left  
        min_node = find_min(root.right)  
        root.val = min_node.val  
        root.right = delete(root.right, min_node.val)  
    return root  

def find_min(node):  
    while node.left:  
        node = node.left  
    return node

时间复杂度分析

- 平衡BST（如AVL树或红黑树）的操作时间复杂度为 $O (\log n)$ 。 - 最坏情况（退化为链表）时间复杂度为 $O (n)$ 。

实际应用案例

1. 数据库索引：如MySQL的InnoDB引擎使用B+树（BST的扩展）加速查询。 2. 字典实现：编程语言中的`std::map`（C++）或`TreeMap`（Java）基于红黑树。 3. 游戏场景管理：如空间分区树（Quadtree的变种）快速定位对象。

平衡二叉搜索树

为避免退化为链表，需引入平衡机制： - AVL树：通过旋转严格保持左右子树高度差 ≤1。 - 红黑树：放宽平衡条件，通过颜色标记和旋转减少调整次数。

练习问题

1. 给定序列 `[5, 3, 7, 1, 4, 6, 8]`，构建BST并绘制结构。 2. 实现非递归版本的查找和插入操作。 3. 分析删除操作中“右子树最小节点”替换法的正确性。

总结

二叉搜索树结合了链表的灵活性和数组的快速查找特性，是算法设计中不可或缺的基础结构。理解其原理及变种（如平衡树）对深入掌握数据结构至关重要。