二叉搜索树：修订间差异

可视化wikitext

2025年5月12日 (一) 00:29的最新版本

模板:Note

二叉搜索树简介[编辑 | 编辑源代码]

二叉搜索树（Binary Search Tree, BST）是一种基于二叉树的数据结构，满足以下性质：

任意节点的左子树仅包含小于该节点键值的元素
任意节点的右子树仅包含大于该节点键值的元素
左右子树也必须各自是二叉搜索树

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

基本操作[编辑 | 编辑源代码]

查找[编辑 | 编辑源代码]

从根节点开始递归比较：

若目标值等于当前节点值 → 找到
若目标值较小 → 进入左子树
若目标值较大 → 进入右子树

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)

插入[编辑 | 编辑源代码]

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

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;
}

删除[编辑 | 编辑源代码]

分三种情况处理：

无子节点：直接删除
有一个子节点：用子节点替代
有两个子节点：用右子树的最小节点替代

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;
}

可视化示例[编辑 | 编辑源代码]

时间复杂度分析[编辑 | 编辑源代码]

操作	平均情况	最坏情况
查找	$O (\log n)$	$O (n)$
插入	$O (\log n)$	$O (n)$
删除	$O (\log n)$	$O (n)$

平衡二叉搜索树[编辑 | 编辑源代码]

为防止退化为链表，衍生出自平衡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

@@ 第1行： / 第1行： @@
-{{DISPLAYTITLE:二叉搜索树}}
+{{Note|本条目讲解二叉搜索树的基本概念、操作及实际应用，适合编程初学者和需要巩固知识的开发者。}}
-'''二叉搜索树'''（Binary Search Tree，BST）是一种基于[[二叉树]]的非线性数据结构，具有高效的查找、插入和删除操作特性。其核心特点是：对于任意节点，其左子树的所有节点值均小于该节点值，右子树的所有节点值均大于该节点值。这一特性使得BST在动态数据管理中广泛应用，如数据库索引、内存分配等场景。
-== 基本性质 ==
+== 二叉搜索树简介 ==
-二叉搜索树满足以下性质：
+'''二叉搜索树'''（Binary Search Tree, BST）是一种基于[[二叉树]]的数据结构，满足以下性质：
-. '''有序性'''：若左子树非空，则左子树所有节点的值 <math><</math> 根节点的值；若右子树非空，则右子树所有节点的值 <math>></math> 根节点的值。
+* 任意节点的左子树仅包含'''小于'''该节点键值的元素
-. '''递归性'''：左右子树也分别为二叉搜索树。
+* 任意节点的右子树仅包含'''大于'''该节点键值的元素
-. '''无重复值'''（通常约定，部分实现允许重复需额外定义规则）。
+* 左右子树也必须各自是二叉搜索树
-=== 示例结构 ===
+这种结构使得查找、插入、删除操作的平均时间复杂度为<math>O(\log n)</math>，最坏情况下（树退化为链表）为<math>O(n)</math>。
-<mermaid>
-graph TD
-((8)) --> 3((3))
---> 10((10))
---> 1((1))
---> 6((6))
---> 4((4))
---> 7((7))
---> 14((14))
---> 13((13))
-</mermaid>
-*图中展示的BST满足：每个节点的左子树值更小，右子树值更大。*
-== 核心操作 ==
+== 基本操作 ==
 === 查找 ===
-从根节点开始，递归比较目标值与当前节点：
+从根节点开始递归比较：
-- 若相等，返回节点；
+* 若目标值等于当前节点值 → 找到
-- 若目标值更小，进入左子树；
+* 若目标值较小 → 进入左子树
-- 若目标值更大，进入右子树；
+* 若目标值较大 → 进入右子树
-- 若子树为空，说明值不存在。
 <syntaxhighlight lang="python">
-def search(root, target):
+def search(root, key):
-     if not root or root.val == target:
+     if root is None or root.val == key:
          return root
-     if target < root.val:
+     if key < root.val:
-         return search(root.left, target)
+         return search(root.left, key)
-     return search(root.right, target)
+     return search(root.right, key)
 </syntaxhighlight>
 === 插入 ===
-类似查找，但需在空位置创建新节点：
+遵循查找逻辑找到合适位置插入新节点，保持BST性质：
-<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>
-=== 删除 ===
+<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="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):
+<syntaxhighlight lang="cpp">
-     while node.left:
+TreeNode* deleteNode(TreeNode* root, int key) {
-         node = node.left
+    if (!root) return nullptr;
-     return node
+     if (key < root->val) {
-</syntaxhighlight>
+        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>
-== 时间复杂度分析 ==
+== 可视化示例 ==
-- 平衡BST（如[[AVL树]]或[[红黑树]]）的操作时间复杂度为 <math>O(\log n)</math>。
+<mermaid>
-- 最坏情况（退化为链表）时间复杂度为 <math>O(n)</math>。
+graph TD
+((8)) --> 3((3))
+--> 10((10))
+--> 1((1))
+--> 6((6))
+--> 4((4))
+--> 7((7))
+--> 14((14))
+--> 13((13))
+</mermaid>
-== 实际应用案例 ==
+== 时间复杂度分析 ==
-. '''数据库索引'''：如MySQL的InnoDB引擎使用B+树（BST的扩展）加速查询。
+{| class="wikitable"
-. '''字典实现'''：编程语言中的`std::map`（C++）或`TreeMap`（Java）基于红黑树。
+|-
-. '''游戏场景管理'''：如空间分区树（Quadtree的变种）快速定位对象。
+! 操作 !! 平均情况 !! 最坏情况
+|-
+| 查找 || <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。
+* [[AVL树]]：通过旋转保持左右子树高度差≤1
-- '''红黑树'''：放宽平衡条件，通过颜色标记和旋转减少调整次数。
+* [[红黑树]]：通过颜色标记和旋转保持平衡
+* [[B树]]：多路平衡搜索树
-== 练习问题 ==
+== 实际应用案例 ==
-. 给定序列 `[5, 3, 7, 1, 4, 6, 8]`，构建BST并绘制结构。
+. '''数据库索引'''：MySQL的InnoDB使用B+树（BST的扩展）
-. 实现非递归版本的查找和插入操作。
+. '''文件系统'''：ext文件系统使用B树管理目录结构
-. 分析删除操作中“右子树最小节点”替换法的正确性。
+. '''游戏开发'''：场景管理中快速查找对象
+. '''网络路由'''：路由器使用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:面试技巧]]
-[[Category:非线性数据结构]]
+[[Category:数据结构基础]]