CodeGuide 图解数据结构：二分搜索树 Binary Search Tree 原理与 Java 实现

文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本文出自 CodeGuide 仓库《倚天村 · 图解数据结构》系列完整讲解二叉搜索树Binary Search Tree的历史由来、结构定义、插入/索引/删除三大核心操作的 Java 实现并结合测试用例验证删除单节点与双节点的完整过程。读完本文你将掌握 BST 的时间复杂度特性、退化风险以及它与 AVL 树、2-3 树、红黑树等自平衡树之间的演进关系为后续学习更复杂的树形结构打下坚实基础。一、前言二叉搜索树的历史二叉搜索树算法是由包括 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在内的几位研究人员独立发现的。该算法归功于 Conway Berners-Lee 和 David Wheeler他们在 1960 年使用它在磁带中存储标记数据。最早且流行的二叉搜索树算法之一是Hibbard 算法。这段历史告诉我们BST 并不是某个单一发明者的作品而是在 1960 年代为解决有序数据的快速存取这一实际问题而逐步成型的经典算法。理解历史有助于我们理解它的定位它是树形结构体系的地基后续的 AVL 树、2-3 树、红黑树都是在它之上解决平衡问题的演化产物。二、二叉搜索树的数据结构二叉搜索树Binary Search Tree也称二叉查找树。如果你看见有序二叉树Ordered Binary Tree、排序二叉树Sorted Binary Tree那么说的都是一个东西。BST 的核心定义由三条递归性质构成左子树约束若任意节点的左子树不空则左子树上所有节点的值均小于它的根节点的值右子树约束若任意节点的右子树不空则右子树上所有节点的值均大于它的根节点的值递归性任意节点的左、右子树也分别为二叉查找树。正是这三条性质使得 BST 在查找、插入、删除时都可以通过逐层比较向左走还是向右走把规模缩小一半从而获得近似O(logn)的时间复杂度。1. 使用场景二叉搜索树在日常开发中的使用场景比较多例如基于组合模式实现的规则引擎它就是一棵二叉搜索树。但类似这样的开发中用到的二叉树场景都是基于配置生成的所以组合出来的节点也更加方便控制树高和平衡性。这与 Java APIHashMap中的红黑树——为了在插入节点后仍保持树的平衡性——是有所不同的。所以二叉搜索树也是一棵没有经过调衡的基础性数据结构在一定概率下它完全有可能退化成链表也就是从近似O(logn)的时间复杂度退化到O(n)。关于二叉搜索树的平衡解决方案包括 AVL 树、2-3 树、红黑树等在 CodeGuide 仓库中均有对应的实现章节平衡二叉树 AVL通过记录树高、计算平衡因子并旋转调衡2-3 树B 树家族的基础形态红黑树只保证黑色节点平衡用染色 旋转减少平衡操作被HashMap冲突桶、Linux CFS、Epoll 等底层使用。2. 复杂度一览操作平均时间复杂度最坏时间复杂度退化为链表时索引searchO(logn)O(n)插入insertO(logn)O(n)删除deleteO(logn)O(n)最坏情况出现在元素按升序或降序插入时树结构退化为单向链表此时 BST 的二分优势完全丧失——这正是后续自平衡树要解决的痛点。三、二叉搜索树结构实现二叉搜索树是整个树结构中最基本的树同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构主要是因为使用数据结构就是对数据的存放和读取。为了提高吞吐效率则需要尽可能平衡元素的排序体现在树上则需要进行一系列操作所以会有不同的结构树实现。而实现二叉搜索树是最好的基础学习了解基本的数据结构后才更容易扩展学习其他树结构。1. 树枝定义public Integer value; public Node parent; public Node left; public Node right;用于组成一棵树的节点需要包括值和与之关联的三角结构——一个父节点、两个孩子节点。从源码结构看这里的value使用Integer包装类型是为了在遍历时通过node.value ! null判断节点是否为空这也与后续search方法的判空逻辑相呼应。如果是 AVL 树节点还需要**树高height**属性用于计算平衡因子如果是红黑树节点还需要**染色color**标记用于平衡操作。这正是基础树结构 增量属性的演进思路先学懂最朴素的三指针节点再逐步叠加属性理解 AVL、红黑树。2. 插入节点public Node insert(int e) { if (null root) { root new Node(e, null, null, null); size; return root; } // 索引出待插入元素位置也就是插入到哪个父元素下 Node parent root; Node search root; while (search ! null search.value ! null) { parent search; if (e search.value) { search search.left; } else { search search.right; } } // 插入元素 Node newNode new Node(e, parent, null, null); if (parent.value newNode.value) { parent.left newNode; } else { parent.right newNode; } size; return newNode; }插入过程分三步判空建根首先判断插入元素时是否有树根没有则会把当前节点创建出一棵树的树根遍历定位如果当前树已有树根则对插入元素与当前树进行节点遍历操作找到元素可以插入的索引位置parent即挂到哪个父节点下。这就是search搜索过程——每次比较e与当前节点值的大小小于则走左子树大于等于则走右子树挂链插入最后为插入值创建一个Node节点绑定它的父元素并把新元素挂到索引到的parent节点下同时size维护节点总数。插入操作始终是在叶子节点处新增节点不会破坏 BST 的三条性质因此无需任何调衡操作——这也是 BST 实现简单的原因。3. 索引节点public Node search(int e) { Node node root; while (node ! null node.value ! null node.value ! e) { if (e node.value) { node node.left; } else { node node.right; } } return node; }值查找的过程就是对二叉搜索树的遍历不断循环节点按照节点值的左右匹配找出最终值相等的节点。循环终止条件有三个node ! null已经遍历到空节点说明树中不存在该值node.value ! null跳过占位空节点node.value ! e当前节点值等于目标值时终止循环返回该节点。由于每次比较都能排除掉一半的子树理想情况下查找次数等于树高即O(logn)。4. 删除节点删除是 BST 中最复杂的操作因为被删除节点可能拥有 0、1、2 个孩子节点情况各异public Node delete(int e) { Node delNode search(e); if (null delNode) return null; return delete(delNode); } private Node delete(Node delNode) { if (delNode null) return null; Node result null; if (delNode.left null) { result transplant(delNode, delNode.right); } else if (delNode.right null) { result transplant(delNode, delNode.left); } else { // 因为删除的节点有2个孩子节点这个时候找到这条分支下最左侧做小的节点。用它来替换删除的节点 Node miniNode getMiniNode(delNode.right); if (miniNode.parent ! delNode) { // 交换位置用miniNode右节点替换miniNode transplant(miniNode, miniNode.right); // 把miniNode 提升父节点设置右子树并进行挂链。替代待删节点 miniNode.right delNode.right; miniNode.right.parent miniNode; } // 交换位置删除节点和miniNode 可打印测试观察System.out.println(this); transplant(delNode, miniNode); // 把miniNode 提升到父节点设置左子树并挂链 miniNode.left delNode.left; miniNode.left.parent miniNode; result miniNode; } size--; return result; } private Node getMinimum(Node node) { while (node.left ! null) { node node.left; } return node; } private Node transplant(Node delNode, Node addNode) { if (delNode.parent null) { this.root addNode; } // 判断删除元素是左/右节点 else if (delNode.parent.left delNode) { delNode.parent.left addNode; } else { delNode.parent.right addNode; } // 设置父节点 if (null ! addNode) { addNode.parent delNode.parent; } return addNode; }删除逻辑的骨架可以概括为删除单节点左孩子为空或右孩子为空直接用唯一的孩子节点顶替被删节点的位置删除双节点左右孩子都存在需要从右子树中找到最小节点最左侧节点来替换被删节点保证替换后仍然满足 BST 的性质。这里有两个关键辅助方法transplant(delNode, addNode)嫁接/移植函数负责把addNode挂到delNode的位置上。先处理根节点特例delNode.parent null时直接更新root再判断被删节点是父节点的左孩子还是右孩子最后回填addNode的父指针。注意transplant只负责替换位置不处理孩子节点的挂链具体孩子关系由调用方补齐getMinimum(node)从指定节点出发不断向左走找到子树中最小的节点。可以推断删除双节点分支中调用的getMiniNode与这里定义的getMinimum对应同一逻辑即取右子树最小节点。4.1 删除单节点以删除节点 14只有一个右孩子 18为例完整步骤如下待删除节点 14判断此节点的父节点的孩子节点哪个等于 14找出左右把待删节点的右孩子节点 18挂到删除节点的位置父节点的右孩子位给待删节点的右孩子节点 18设置上父节点完成三角关系的更新。对应代码中delNode.left null分支transplant(delNode, delNode.right)一步完成顶替与父指针回填被删节点 14 即从树中被移除。4.2 删除双节点以删除节点 64右孩子为 89左孩子为 63为例完整步骤如下待删除节点 64 含有双子节点则需要根据第一个右子节点89查找最小左子节点从 89 到 72如果有比 72 还小的左子节点继续排查排查到节点 72将 72 这个准备替换待删元素的节点与右子节点 73 进行位置交换过程与 4.1 删除单节点 相同使用交换函数transplant最后进行节点 72 与待删节点 64 的交换过程更换三角关系父节点、左子节点、右子节点。对应代码中else分支的两段transplant当miniNode.parent ! delNode时先用transplant(miniNode, miniNode.right)把最小值节点的右子树提升上来再让miniNode接管delNode的右子树随后transplant(delNode, miniNode)把miniNode顶到待删节点位置并让miniNode接管delNode的左子树。这个用右子树最小节点替换被删节点的策略是 BST 删除算法的经典做法其正确性在于右子树最小节点一定大于被删节点的所有左子树节点、且小于右子树其余所有节点用它顶替后整棵树依然满足 BST 性质。四、二叉搜索树功能测试为了方便观察树结构的变化小傅哥的测试代码通过程序打印树形结构类似大家之前打印 99 乘法表的方式直观看到每一次插入、删除后的树形态。1. 随机插入元素Test public void test_binary_search_tree() { BinarySearchTree tree new BinarySearchTree(); for (int i 0; i 10; i) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }测试结果/----- 91 | \----- 78 /----- 74 | \----- 67 61 | /----- 51 \----- 40 | /----- 28 \----- 14 \----- 7 Process finished with exit code 0因为测试时的随机数不同可能会出现很多不同结构的二叉搜索树也可能是一个类似链表结构的退化树。这个测试恰好印证了前文的分析随机插入 10 个 0~99 的整数树的形态完全取决于插入顺序。如果运气不好插入了有序序列BST 就会退化成链表复杂度从O(logn)恶化到O(n)——这正是后续章节引入 AVL、2-3 树、红黑树等自平衡树的根本动机。2. 插入并且删除Test public void test_insert_delete(){ BinarySearchTree tree new BinarySearchTree(); tree.insert(32); tree.insert(7); tree.insert(64); tree.insert(63); tree.insert(89); tree.insert(72); tree.insert(94); tree.insert(6); tree.insert(14); tree.insert(18); tree.insert(73); System.out.println(tree); // 删除单节点只有一个孩子的父节点 // tree.delete(14); // 删除双节点拥有二个孩子的父节点 tree.delete(64); System.out.println(tree); }测试结果/----- 94 /----- 89 | | /----- 73 | \----- 72 /----- 64 | \----- 63 32 | /----- 18 | /----- 14 \----- 7 \----- 6 /----- 94 /----- 89 | \----- 73 /----- 72 | \----- 63 32 | /----- 18 | /----- 14 \----- 7 \----- 6 Process finished with exit code 0这个案例就是上文 4.2 删除双节点 的案例删除了节点 64 以后节点 72 被提取上来使用。对比删除前后的两次打印输出可以清楚看到72 顶替了 64 的位置72 的右子树 73 挂在了 89 之下63 成为 72 的左孩子整棵树依然满足 BST 性质。读者伙伴也可以尝试删除其他节点测试验证例如注释掉tree.delete(64)而打开tree.delete(14)观察单节点删除时 18 顶替 14 的过程。五、常见面试题二叉搜索树结构简述以及变形可能面试官也可能让你手写二叉搜索树的插入、删除、索引的时间复杂度二叉搜索树删除含有双子节点的元素过程叙述二叉搜索树的节点都包括了哪些信息为什么 JavaHashMap中说过红黑树而不使用二叉搜索树。其中最后一题是高频考点HashMap的哈希桶在链表长度达到阈值后会将链表转为红黑树正是因为元素碰撞后按顺序插入会形成近似有序链表此时 BST 会退化为O(n)查询而红黑树通过染色与旋转维持黑色节点平衡把最坏时间复杂度重新拉回O(logn)。如果你想深入学习这棵进化版的 BST可以继续阅读仓库中的 红黑树章节以及它的前置章节 2-3 树 和 AVL 树。完整的数据结构学习路线与全书章节大纲可查看 《倚天村 · 图解数据结构》总览。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐解决NPU推理延迟难题Intel® NPU Acceleration Library预编译技术实战解决NPU推理延迟难题Intel® NPU Acceleration Library预编译技术实战 在AI模型部署过程中推理延迟一直是开发者面临的核心挑战。文档教程后端LeetCode 0700 二叉搜索树搜索Search in a Binary Search Tree多语言题解递归与迭代两种实现LeetCode 0700 二叉搜索树搜索Search in a Binary Search Tree多语言题解递归与迭代两种实现 本文围绕 LeetCo示例工程教程LeetCode-Go 题解 669修剪二叉搜索树 Trim a Binary Search TreeLeetCode Go 题解 669修剪二叉搜索树 Trim a Binary Search Tree 导读 本文基于 LeetCode Go 仓库中的第 6示例工程上一篇React-Select无障碍文本替代为非文本内容提供描述下一篇终极指南Nginx Proxy Manager服务发现集成与微服务架构部署创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考