二分搜索树（建议收藏）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程与算法领域，数据结构的选择直接影响代码的效率与可维护性。二分搜索树（Binary Search Tree，BST）作为一种经典的树形数据结构，因其直观的逻辑和高效的查询特性，成为许多开发者入门进阶的必学内容。无论是数据库索引优化、实时数据排序，还是算法竞赛中的高频考点，二分搜索树的身影无处不在。本文将从零开始，通过比喻、代码示例和实际案例，帮助编程初学者与中级开发者系统掌握这一核心工具。

二分搜索树的基本概念

树形结构的直观比喻

想象一座图书馆的书架：每本书都有一个唯一的编号，且按照从小到大的顺序从左到右排列。二分搜索树的结构与此类似，每个节点（Node）代表一个“书的位置”，其左子树的所有节点值均小于当前节点值，右子树则均大于当前节点值。这种“左小右大”的特性，使得二分搜索树能够高效完成插入、搜索和删除等操作。

核心定义与特性

二分搜索树的每个节点包含三个关键部分：

1. 值（Value）：存储的具体数据（如整数、字符串等）。
2. 左子节点（Left Child）：指向左子树的指针。
3. 右子节点（Right Child）：指向右子树的指针。

其核心特性可总结为：

• 左子树规则：所有左子树的节点值均小于根节点值。
• 右子树规则：所有右子树的节点值均大于根节点值。
• 递归性：每个子树本身也是一棵二分搜索树。

例如，若根节点为 50，则左子树可能包含 30、20 等节点，而右子树可能包含 70、65 等节点。

核心操作详解

1. 插入操作：寻找合适的位置

操作逻辑

插入新值时，需从根节点开始，通过“左小右大”规则逐步定位插入位置：

1. 若当前节点值大于目标值，则向左子树递归查找。
2. 若当前节点值小于目标值，则向右子树递归查找。
3. 当找到空节点时，插入新值。

形象比喻

插入操作如同在图书馆中放置一本新书：

• 从书架最左侧开始，若新书编号小于当前书的编号，则向左侧区域移动；反之则向右侧移动。
• 直到找到空位，将新书放入。

代码实现（Python）

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

class BinarySearchTree:  
    def __init__(self):  
        self.root = None  

    def insert(self, value):  
        if self.root is None:  
            self.root = TreeNode(value)  
        else:  
            self._insert_recursive(self.root, value)  

    def _insert_recursive(self, node, value):  
        if value < node.value:  
            if node.left is None:  
                node.left = TreeNode(value)  
            else:  
                self._insert_recursive(node.left, value)  
        elif value > node.value:  
            if node.right is None:  
                node.right = TreeNode(value)  
            else:  
                self._insert_recursive(node.right, value)  
        # 若值相等，可选择不插入或扩展逻辑处理重复值  

2. 搜索操作：快速定位目标值

操作逻辑

搜索与插入类似，但最终目标是找到或确认目标值是否存在：

1. 从根节点开始比较，若值匹配则返回节点。
2. 若目标值小于当前节点值，则向左子树递归搜索。
3. 若目标值大于当前节点值，则向右子树递归搜索。
4. 若到达空节点，则目标值不存在。

效率分析

• 平均时间复杂度：O(log n)，假设树是平衡的。
• 最坏时间复杂度：O(n)，若树退化为链表（如插入数据已排序）。

代码实现（Python）

    def search(self, value):  
        return self._search_recursive(self.root, value)  

    def _search_recursive(self, node, value):  
        if node is None:  
            return None  
        if value == node.value:  
            return node  
        elif value < node.value:  
            return self._search_recursive(node.left, value)  
        else:  
            return self._search_recursive(node.right, value)  

3. 删除操作：灵活应对三种场景

删除操作是二分搜索树中最复杂的部分，需分情况讨论：

场景分类与处理策略

1. 叶子节点（无子节点）：直接删除该节点。
2. 单子节点（仅左或右子节点）：用子节点替代被删除节点。
3. 双子节点（同时有左右子节点）：
   • 找到右子树中的最小值节点（或左子树的最大值节点）。
   • 将该最小值节点的值替换到被删除节点的位置。
   • 删除原最小值节点（此时该节点必为叶子或单子节点）。

形象比喻

删除操作如同整理书架：

• 若要移走一本位于中间的书，需找到其左邻或右邻的替代者，确保书架仍保持有序。

代码实现（Python）

    def delete(self, value):  
        self.root = self._delete_recursive(self.root, value)  

    def _delete_recursive(self, node, value):  
        if node is None:  
            return node  
        if value < node.value:  
            node.left = self._delete_recursive(node.left, value)  
        elif value > node.value:  
            node.right = self._delete_recursive(node.right, value)  
        else:  
            # 情况1：无子节点  
            if node.left is None and node.right is None:  
                return None  
            # 情况2：仅有一个子节点  
            elif node.left is None:  
                return node.right  
            elif node.right is None:  
                return node.left  
            # 情况3：有两个子节点，寻找右子树最小值  
            else:  
                min_node = self._find_min(node.right)  
                node.value = min_node.value  
                node.right = self._delete_recursive(node.right, min_node.value)  
        return node  

    def _find_min(self, node):  
        current = node  
        while current.left is not None:  
            current = current.left  
        return current  

实际案例与代码演示

案例：学生成绩管理系统

假设需要管理学生考试成绩，要求支持快速查询、插入和删除操作。使用二分搜索树可高效实现：

示例数据

学生学号与成绩如下：
| 学号（Key） | 成绩（Value） |
|------------|---------------|
| 101 | 85 |
| 105 | 92 |
| 103 | 78 |
| 107 | 88 |

构建二分搜索树

插入顺序为 101 → 105 → 103 → 107：

• 根节点为 101，105 插入右子树。
• 103 小于 105，插入其左子树。
• 107 大于 105，插入右子树。

查询操作

搜索学号 103：

1. 从根节点 101 开始，103 > 101 → 进入右子树 105。
2. 103 < 105 → 进入左子树，找到目标节点。

删除操作

删除学号 105（双子节点）：

1. 找到右子树最小值 107。
2. 替换 105 的值为 107，并删除原 107 节点。

二分搜索树的应用场景与局限性

典型应用场景

1. 实时数据排序：动态插入/删除元素时保持有序。
2. 数据库索引优化：如 B+ 树的底层实现思想与 BST 类似。
3. 算法竞赛中的中位数问题：结合其他结构（如堆）实现高效查询。

局限性与优化方向

1. 不平衡问题：若数据有序插入，BST 可退化为链表，导致时间复杂度退化为 O(n)。
2. 解决方式：引入平衡树（如 AVL 树、红黑树）强制保持树高为 O(log n)。

常见问题与进阶思考

Q1：BST 是否允许重复值？

• 默认情况下，BST 可以拒绝插入重复值，或将其插入左/右子树。需根据具体需求调整代码逻辑。

Q2：如何判断一个二叉树是否为 BST？

• 可通过中序遍历验证是否为递增序列，或使用递归方法传递上下界范围限制。

Q3：BST 与平衡树的区别？

• 平衡树（如 AVL 树）通过旋转操作强制保持树高平衡，确保最坏情况下的时间复杂度为 O(log n)。

结论

二分搜索树以其简洁的逻辑和直观的性能优势，成为开发者工具箱中的重要一员。通过本文的解析，读者应能掌握其核心操作的实现原理，并理解其在实际场景中的应用价值。对于编程初学者，建议通过手动模拟插入/删除过程加深理解；中级开发者则可尝试结合平衡树算法，探索更高效的实现方式。掌握二分搜索树不仅是技术能力的提升，更是培养树形思维的关键一步。

附录：关键术语表
| 术语 | 解释 |
|------|------|
| 二分搜索树（BST） | 通过左小右大规则组织节点的树形结构。 |
| 中序遍历 | 按左→根→右顺序访问节点，BST 中序遍历结果为升序序列。 |
| 平衡树 | 通过旋转操作强制保持树高的数据结构（如 AVL 树）。 |