编辑“︁二叉搜索树”︁

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

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

=== 示例结构 ===  
<mermaid>  
graph TD  
    8((8)) --> 3((3))  
    8 --> 10((10))  
    3 --> 1((1))  
    3 --> 6((6))  
    6 --> 4((4))  
    6 --> 7((7))  
    10 --> 14((14))  
    14 --> 13((13))  
</mermaid>  
*图中展示的BST满足：每个节点的左子树值更小，右子树值更大。*

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

<syntaxhighlight lang="python">  
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)  
</syntaxhighlight>  

=== 插入 ===  
类似查找，但需在空位置创建新节点：  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

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

<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

== 时间复杂度分析 ==  
- 平衡BST（如[[AVL树]]或[[红黑树]]）的操作时间复杂度为 <math>O(\log n)</math>。  
- 最坏情况（退化为链表）时间复杂度为 <math>O(n)</math>。  

== 实际应用案例 ==  
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. 分析删除操作中“右子树最小节点”替换法的正确性。  

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]