编辑“︁二叉搜索树”︁

{{Note|本条目讲解二叉搜索树的基本概念、操作及实际应用，适合编程初学者和需要巩固知识的开发者。}}

== 二叉搜索树简介 ==
'''二叉搜索树'''（Binary Search Tree, BST）是一种基于[[二叉树]]的数据结构，满足以下性质：
* 任意节点的左子树仅包含'''小于'''该节点键值的元素
* 任意节点的右子树仅包含'''大于'''该节点键值的元素
* 左右子树也必须各自是二叉搜索树

这种结构使得查找、插入、删除操作的平均时间复杂度为<math>O(\log n)</math>，最坏情况下（树退化为链表）为<math>O(n)</math>。

== 基本操作 ==
=== 查找 ===
从根节点开始递归比较：
* 若目标值等于当前节点值 → 找到
* 若目标值较小 → 进入左子树
* 若目标值较大 → 进入右子树

<syntaxhighlight lang="python">
def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)
</syntaxhighlight>

=== 插入 ===
遵循查找逻辑找到合适位置插入新节点，保持BST性质：

<syntaxhighlight lang="java">
TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val) 
        root.left = insert(root.left, key);
    else if (key > root.val)
        root.right = insert(root.right, key);
    return root;
}
</syntaxhighlight>

=== 删除 ===
分三种情况处理：
* '''无子节点'''：直接删除
* '''有一个子节点'''：用子节点替代
* '''有两个子节点'''：用右子树的最小节点替代

<syntaxhighlight lang="cpp">
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* minNode = findMin(root->right);
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}
</syntaxhighlight>

== 可视化示例 ==
<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>

== 时间复杂度分析 ==
{| class="wikitable"
|-
! 操作 !! 平均情况 !! 最坏情况
|-
| 查找 || <math>O(\log n)</math> || <math>O(n)</math>
|-
| 插入 || <math>O(\log n)</math> || <math>O(n)</math>
|-
| 删除 || <math>O(\log n)</math> || <math>O(n)</math>
|}

== 平衡二叉搜索树 ==
为防止退化为链表，衍生出'''自平衡BST'''：
* [[AVL树]]：通过旋转保持左右子树高度差≤1
* [[红黑树]]：通过颜色标记和旋转保持平衡
* [[B树]]：多路平衡搜索树

== 实际应用案例 ==
1. '''数据库索引'''：MySQL的InnoDB使用B+树（BST的扩展）
2. '''文件系统'''：ext文件系统使用B树管理目录结构
3. '''游戏开发'''：场景管理中快速查找对象
4. '''网络路由'''：路由器使用Trie树（BST变种）进行IP查找

== 练习题 ==
<quiz>
{二叉搜索树的中序遍历结果是什么性质？
|type="()"}
+ 升序排列
- 降序排列
- 随机顺序
- 按层次排列

{在最坏情况下，二叉搜索树的时间复杂度会退化到？
|type="()"}
- O(1)
- O(log n)
+ O(n)
- O(n log n)
</quiz>

== 进阶技巧 ==
* '''迭代实现'''：所有递归操作都可改为用栈实现的迭代版本
* '''线程化BST'''：添加指向前驱/后继节点的指针加速遍历
* '''持久化BST'''：修改时保留历史版本

{{DataStructure-stub}}

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:数据结构基础]]