前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏上篇博客中解析了集合类Map和Set的使用方法Map的实现类有TreeMap和HashMapSet的实现类有TreeSet和HashSetTreeMap和TreeSet的的底层实现就是二叉搜索树这篇博客就会解析二叉搜索树和概念以及如何实现二叉搜素树二叉搜索树属于是一种特殊的二叉树严格来说是要放到二叉树部分的之所以放到MapSet部分来解析是因为在数据结构基础中只有Map和Set的底层实现这里会用到二叉搜索树欢迎想复习二叉树的铁汁来访问该专栏前面的二叉树博客这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1二叉搜索树简介二叉搜索树的英文是binarySearchTree每个首字母的简写就是BST最大度为2的树就是二叉树二叉搜索树在这个的基础上还有两个要求如果左子树不为空那么左子树的所有的key都应小于根节点的key如果右子树不为空那么右子树的所有的key都应大于根节点的key二叉搜索树跟堆都是特殊的二叉树也都有“大小关系”的要求二叉搜索树存在左右关系的要求左 根 右堆存在上下关系的要求父节点 子节点在二叉搜索树中对数据的查找其实是类似于二分查找的如下图例如查找1先判断要查找的元素比根节点小还是大如果比根节点小到左子树查找再比较与左子树的根节点3的大小仍然比3小就到3的左子树去找然后就找到了。二叉搜索树中插入数据也是类似的道理拿一个数据跟根结点比大小如果比根结点大就往左子树中插入比根结点小就往左子树中插入比根结点大就往右子树中插入接着再和左子树的根结点或者右子树的根结点比较大小依次类推因此左子树中的元素都小于根结点右子树中的所有元素都大于根结点标准定义的二叉搜索树中默认不允许重复值在数组的二分查找中分出来的两个部分都是均匀的但是对于二叉搜索树来说就不一定了比较的次数是跟树的高度相关的。一个二叉树有N个节点如果左右高度比较均衡那么高度就是logN如果出现极端的情况比如单枝树的情况那么高度就变成N了那么这时候的查找就跟普通链表的遍历差不多时间复杂度就是O(N)了。二叉搜索树的时间复杂度最坏ON理想OlogN针对平衡的二叉搜索树来说时间复杂度就是O(logN)还有两种平衡度比较强的二叉搜索树就是AVL树和红黑树AVL树要求严格的平衡代码并不是特别复杂但是这种树的实用性很低虽然查找的时候时间复杂度会比较理想但是一旦删除插入元素这个树的平衡就会被打破就需要调整频繁的调整也是会影响效率的。红黑树的实用价值比较高它的要求比较均衡但是代码实现特复杂即使是简单的删除也要考虑5种不同的情况。这两种树属于数据结构部分进阶的内容在面试还有工作中的实用是没有数据结构基础部分性价比高但是肯定也是有用的JavaSE、数据结构基础、JavaEE、数据库等都学习完的铁汁有时间可以学习下这些进阶数据结构后面博主大概会出个进阶数据结构的专栏2元素删除分析删除元素是二叉搜索树中比较复杂的一件事情了首先需要找到要删除节点所在的位置同时也要记录该节点的父节点的位置也需要考虑各种各样的情况需要铁汁们细品这里就先来单独解析下元素删除操作为什么要额外记录父节点的位置呢因为在学校或者面试中普遍使用的是孩子表示法就是可以通过一个节点找出它的子节点但是没法找出它的父节点因此这里要额外的去记录父节点的位置。把要删除的元素称为curcur的父节点称为parent那cur的位置有四种情况cur没有左右子树cur只有左子树cur只有右子树cur左右子树都有接下来会结合代码来解析这四种情况分别要怎么处理①cur没有子树这是最简单的一种情况因为cur没有子树直接删除掉cur即可修改cur的父节点parent的left或者right的指向这时候没有引用指向curcur就会被自动删除//1,cur没有子树if(cur.rightnullcur.leftnull){//1.1,如果cur就是root就需要对root进行调整if(curroot){//这时候整个树只有一个root节点把root删除后相当于树就成了空树rootnull;return;}//1.2 cur不是root同时cur是parent的左子树if(curparent.left){//这时候直接删除cur即可parent.leftnull;return;}//1.3 cur不是root,同时是parent的右子树if(curparent.right){parent.rightnull;return;}//这里我们最后还是加个return虽然理论上来说是不会走到这里的但是为了稳妥还是加个。return;}②cur只有左子树没有右子树这里同样也分三种情况cur是根节点要删除cur那么cur的左子树的第一个节点就变成了根节点这个比较好理解就不画图了cur是parent的左子树要删除cur让parent.left等于cur.left即可如图一要删除这个元素4那么把5的左子树连上2就可以了cur是parent的右子树要删除cur把parent.right改为cur.left即可如图2要删除7把5的右子树连上6即可代码如下//2.cur只有左子树if(cur.left!nullcur.rightnull){//2.1 cur为rootif(curroot){//cur的左子树的第一个节点就变成了根节点了rootcur.left;return;}//2.2 cur不是root同时cur是parent的左子树if(curparent.left){parent.leftcur.left;return;}//2.3 cur不是root同时cur是parent的右子树if(curparent.right){parent.rightcur.left;return;}return;}③cur只有右子树还是分三种情况cur是根节点让他的右子树的第一个节点变成根节点即可cur是parent的左子树parent.left cur.right如图一要删除cur是parent的右子树parent.left cur.right如图二 要删除8让7的右子树连上10即可代码如下if(cur.right!nullcur.leftnull){//3.1 cur是根节点if(curroot){rootcur.right;return;}//3.2 cur不是根节点且cur是parent的左子树if(curparent.left){parent.leftcur.right;return;}//3.3 cur不是根节点且cur是parent的右子树if(curparent.right){parent.rightcur.right;return;}return;}④cur左右子树都有前面3种比较简单第4种就稍微有点复杂了如下图要删除5这个结点但是5左右子树都有那么显然就没有办法直接删除了就可以使用“替罪羊法”那就是把cur(要删除的结点)的左子树的最右侧元素 或者 右子树的最左侧元素当作替罪羊把cur的值改为替罪羊元素的值接着把替罪羊元素删除即可用左子树的最大值最右侧元素或者右子树中的最小值最左侧元素来当替罪羊都可以如下图用右子树的最左侧元素6来当替罪羊右子树的最左侧结点的值是6把这个结点的值赋值给cur再删除这个替罪羊结点即可步骤如下图因为左子树的所有元素都是小于根结点的右子树的所有元素都是大于根结点的把左子树的最大值或者右子树的最小值换到根结点上仍然是满足二叉搜索树的性质的分析清楚后代码逻辑就分为以下三步这里用右子树的最小值当作替罪羊结点利用while循环找到替罪羊进行移花接木把cur的值换成替罪羊的值删除替罪羊结点替罪羊结点要不就是左右都为null要不就是只有右子树不可能有左子树因为已经跳出了while循环那么就直接goatParent.left goat.right;即可// 4.cur有两个子树if(cur.left!nullcur.right!null){//第一步先找到替罪羊Nodegoatcur.right;NodegoatParentcur;while(goat.left!null){goatParentgoat;goatgoat.left;}//这个while循环结束之后goat指向的就是cur的右子树的最左侧节点//第二步移花接木把替罪羊的值赋值到cur节点中cur.keygoat.key;//第三步删除goat节点goat是没有左子树的让goatParent直接连上goat的右子树即可//即使goat的右子树是空的也不影响goatParent.leftgoat.right;}第三步删除替罪羊结点其实漏掉了一种情况铁汁们可以细品一下看能不能品出来如下图这种情况下右子树没有左侧元素分支这时候根本就不会进入while循环我们预期是这样的但是按照代码的操作goatParent.left goat.right操作后就变成了下图这样这时候该删除的goat结点没有删除也把左子树上的数据给覆盖掉了因此第三步还要再加上一个判断判断goat是否等于goatParent.left来判断goatParent有没有在while循环中移动如果移动了就按正常流程来如果没移动就说明右子树没有左侧元素分支就goatParent.right goat.right;//第三步删除goat节点goat是没有左子树的让goatParent直接连上goat的右子树即可//即使goat的右子树是空的也不影响//这里还有一个坑那就是没有触发while这段代码那么goat就是goatParent的右子树goatParent.leftgoat.right;if(goatgoatParent.left){goatParent.leftgoat.right;}else{goatParent.rightgoat.right;}}3代码实现1插入操作元素删除操作搞懂了二叉搜索树代码就比较好写了首先写个Node类left和right引用默认为nullpublicclassNode{publicintkey;Nodeleftnull;Noderightnull;publicNode(intkey){this.keykey;}}接着创建BinarySearchTree类里面写个插入方法前序遍历方法中序遍历方法再写个print方法来打印遍历的结果insert方法逻辑如下传入元素key创建结点判断当前二叉树是否为空如果为空root newHead如果当前二叉树不为空那就创建个cur和parentcur初始时在root的位置比较cur.key和key的大小关系如果key cur.keycur就往左子树走如果key cur.keycur就往右子树走用parent计算cur的上一步位置一直在while循环中重复该过程直到cur的值为null出while循环后parent就是newNode的父结点要判断key和parent.key的大小关系确定newNode是加到parent的左边还是右边publicclassBinarySearchTree{//表示当前树的根节点privateNoderootnull;//把新的元素插入到树中publicvoidinsert(intkey){NodenewNodenewNode(key);//如果当前树是空树的话就直接用root指向新节点即可if(rootnull){rootnewNode;return;}//如果是普通的树的话就需要找到要插入的位置再进行插入//cur用来找待插入元素的位置//parent 记录 cur 的父元素Nodecurroot;Nodeparentnull;while(cur!null){if(keycur.key){//比根节点的元素小就往左找parentcur;curcur.left;}elseif(keycur.key){//比根节点的元素大就往右找parentcur;curcur.right;}else{//对于相同的情况其实是存在许多不同的处理方式//我们这里是不允许重复的key出现的这里就直接return即可return;}}//这个while循环走完以后我们就得到了cur为null的情况,此时parent就是要插入元素的父节点//这就需要把newNode插入到parent的子节点上//这时候还要再判断一次新节点是插到parent的左子树还是右子树上if(keyparent.key){parent.leftnewNode;}else{parent.rightnewNode;}}publicvoidpreOrder(Noderoot){if(rootnull){return;}System.out.print(root.key );preOrder(root.left);preOrder(root.right);}publicvoidinOrder(Noderoot){if(rootnull){return;}inOrder(root.left);System.out.print(root.key );inOrder(root.right);}publicvoidprint(){System.out.println(前序遍历);preOrder(root);System.out.println();System.out.println(中序遍历);inOrder(root);}}2特征分析在main方法中测试下中序遍历的结果是从小到大排序的因为中序遍历的顺序是左—中—右在二叉搜索树中左边的元素小于根节点元素而右边的元素是大于根节点元素的。publicclassTest{publicstaticvoidmain(String[]args){int[]arr{1,3,2,6,5,7,8,9,10,0};BinarySearchTreetreenewBinarySearchTree();for(intkey:arr){tree.insert(key);}tree.print();}}通过先序和中序遍历来画出二叉搜索树的样子如下图前面的二叉树一博客中解析了通过序列还原出二叉树的技巧链接放在下面了感兴趣的铁汁可以复习一下二叉树一在IDEA中调试下在main方法的tree.print()这里打上一个断点执行到这里停下来时二叉搜索树就已经构建好了如果还是这些元素插入的顺序不同构建的二叉搜索树就也是不同的测试如下如下图左边是第一次构造的右面是第二次构造的因此二叉搜索树的是不稳定的。3查找操作查找操作也不复杂搞个cur从root开始判断要查找的值key和cur.key的大小关系如果key大于cur.keycur就往右子树上移动如果key大于cur.keycur就往左子树上移动如果key小于cur.keycur就往右子树上移动key等于cur.key就直接返回cur如果二叉搜索树为空或者没有匹配到就返回nullpublicNodefind(intkey){if(rootnull){returnnull;}Nodecurroot;while(cur!null){if(keycur.key){curcur.left;}elseif(keycur.key){curcur.right;}else{//相等找到了returncur;}}//如果while循环完都没有找到那么就没有查找到,说明不存在returnnull;}要在main方法中测试还要在Node类中重写一下toString()方法清楚的打印出是哪个节点publicclassNode{publicintkey;Nodeleftnull;Noderightnull;publicNode(intkey){this.keykey;}OverridepublicStringtoString(){returnNode{keykey, leftleft, rightright};}}publicclassTest{publicstaticvoidmain(String[]args){int[]arr{1,3,6,2,5,0,8,10,9,7};BinarySearchTreetreenewBinarySearchTree();for(intkey:arr){tree.insert(key);}System.out.println(tree.find(0));}}4删除操作删除操作还是比较复杂的前面第2部分已经解析过了这里就写下代码这里分为两个方法来实现在remove方法中传入key在while循环中进行匹配找到要删除的元素cur和该元素的父结点parentpublicvoidremove(intkey){if(rootnull){return;}Nodecurroot;Nodeparentnull;while(cur!null){if(keycur.key){//比根节点的值大就去根节点的右面找parentcur;//更新父节点的位置curcur.right;}elseif(keycur.key){parentcur;curcur.left;}else{//相等直接进行删除操作即可removeNode(parent,cur);return;}}}在remove方法中找到待删除元素cur和其父结点parent后就调用removeNode方法传入cur和parent在2.元素删除分析中已经分析过逻辑了这部代码要考虑的情况分支是非常多的需要铁汁们细品代码如下publicvoidremoveNode(Nodeparent,Nodecur){//共分为4大种情况//1,cur没有子树if(cur.rightnullcur.leftnull){//1.1,如果cur就是root就需要对root进行调整if(curroot){//这时候整个树只有一个root节点把root删除后相当于树就成了空树rootnull;return;}//1.2 cur不是root同时cur是parent的左子树if(curparent.left){//这时候直接删除cur即可parent.leftnull;return;}//1.3 cur不是root,同时是parent的右子树if(curparent.right){parent.rightnull;return;}//这里我们最后还是加个return虽然理论上来说是不会走到这里的但是为了稳妥还是加个。return;}//2.cur只有左子树if(cur.left!nullcur.rightnull){//2.1 cur为rootif(curroot){//cur的左子树的第一个节点就变成了根节点了rootcur.left;return;}//2.2 cur不是root同时cur是parent的左子树if(curparent.left){parent.leftcur.left;return;}//2.3 cur不是root同时cur是parent的右子树if(curparent.right){parent.rightcur.left;return;}return;}//3.cur只有右子树if(cur.right!nullcur.leftnull){//3.1 cur是根节点if(curroot){rootcur.right;return;}//3.2 cur不是根节点且cur是parent的左子树if(curparent.left){parent.leftcur.right;return;}//3.3 cur不是根节点且cur是parent的右子树if(curparent.right){parent.rightcur.left;return;}return;}// 4.cur有两个子树if(cur.left!nullcur.right!null){//这时候就无需考虑cur是不是根节点的情况了因为这里并没有真正删除cur指向的节点即使cur是root.//也无需修改root的指向因为实际找寻的是“替罪羊节点”//首先要找到右子树中的最小值 替罪羊//后续删除替罪羊同时把替罪羊的父节点记录一下//第一步先找到替罪羊Nodegoatcur.right;NodegoatParentcur;while(goat.left!null){goatParentgoat;goatgoat.left;}//这个while循环结束之后goat指向的就是cur的右子树的最左侧节点//第二步移花接木把替罪羊的值赋值到cur节点中cur.keygoat.key;//第三步删除goat节点goat是没有左子树的让goatParent直接连上goat的右子树即可//即使goat的右子树是空的也不影响//这里还有一个坑那就是没有触发while这段代码那么goat就是goatParent的右子树if(goatgoatParent.left){goatParent.leftgoat.right;}else{goatParent.rightgoat.right;}}}结语二叉搜索树实现这里也没有用到复杂的递归主要是删除操作比较复杂需要分多种情况讨论写这个删除操作是非常考验代码能力的TreeSet和TreeMap的底层是红黑树也就是改进版本的二叉搜索树能够保证增删查的时间复杂度为O(logN)当需要元素/key有序时就用TreeSet/TreeMap.以上就是今天的所有内容啦完结撒花