⭐️博主此生决int-CSDN博客速胜派就是最大的投降派热门专栏深入理解 C 系列算法系列快速复习系列Java 速通系列文章目录上期回顾一. 二叉搜索树1. 二叉搜索树的概念**2为什么**我们要引入二叉搜索树它的优势是什么2. 二叉搜索树的性能分析关于搜索总结二叉搜索树的模拟实现1. 插入insert主播的实现代码需要注意的点2.查找find主播的实现代码3. 二叉搜索树的删除⭐️⭐️⭐️⭐️⭐️实现要点1左右都为空2左为空或者右为空3左右都有孩子最复杂交换删除法主播的实现代码4主播在这次模拟实现时犯的几个错误其中在实现删除函数接口时犯的错误7. 二叉搜索树 key 和 key/value 使用场景⭐️⭐️⭐️7.3 key/value 二叉搜索树代码实现下期预告map/set的使用结语上期回顾上一篇我们主要学习了C模版的一些进阶内容学习了非类型模版参数函数模版的特化类模版的特化等等相较于模版初阶的内容模版进阶引入了更多的模版的一些知识这些在我们接下来学习的STL里面都有非常多的应用那么今天就让我们开始学习进阶STL的第一节二叉搜搜树吧可以回顾一下数据结构篇二叉树的相关知识但是这里采用的是链式结构哦一. 二叉搜索树1. 二叉搜索树的概念顾名思义就是一颗主要用于搜索的特殊的二叉树所以它肯定具有二叉树的所有性质我们这里的二叉树就不是用数组来模拟了而是链式结构与普通二叉树的区别就是它具有一下的性质对于每一个根节点形成的一颗树左边的所有节点小于等于根节点右边的所有节点大于等于根节点2关于这里的等于这一点他们是两种不同的我们后面学习的map/set不支持等于用的多multimap/multiset支持等于2为什么我们要引入二叉搜索树它的优势是什么首先我们想要一个可以快速频繁查找的结构我们这后面学的数据结构主要就是围绕这一点来学习那么我们之前学习了二分查找也非常快但是它要求数组并且是有序的数组这就导致了它的缺点很明显数组会导致它的插入删除非常不方便所以就设计了二叉搜索树这一个结构那么它的查找效率是多少呢2. 二叉搜索树的性能分析最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其高度为log_2 底N最差情况下二叉搜索树退化为单支树或者类似单支其高度为N所以综合而言二叉搜索树增删查改时间复杂度为O(N)那么这样的效率显然是无法满足我们需求的我们后续课程需要继续讲解二叉搜索树的变形平衡二叉搜索树 AVL 树和红黑树才能适用于我们在内存中存储和搜索数据。关于搜索总结1二分查找——效率logN但是有两大缺陷需要存储在支持下标随机访问的结构中并且有序。插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。2二叉搜索树——N插入删除方便优化后可以达到logN优化后的结构AVL树红黑树等3哈希表——O1二叉搜索树的模拟实现接下来我们来模拟实现一个最普通的二叉搜索树的一些关键接口函数主要是删除接口函数的实现是本文的重点。1. 插入insert插入的具体过程如下树为空则直接新增结点赋值给 root 指针树不空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走可以利用下面的图片自己模拟一下插入16的过程还是比较简单的主播的实现代码// 插入判断插入是否成功即可boolInsert(constKkey){Node*newnodenewNode(key);if(_rootnullptr){_rootnewnode;returntrue;}//肯定要先找到你要插入的位置肯定是插入到叶子节点Node*parentnullptr;Node*cur_root;while(cur){parentcur;//if (key cur-_key)保证parent和cur是链接起来的if(keyparent-_key){curparent-_left;}elseif(keyparent-_key){curparent-_right;}else{//return false;防止内存泄露deletenewnode;returnfalse;}}//找到了插入位置//cur newnode;if(keyparent-_key)parent-_leftnewnode;if(keyparent-_key)parent-_rightnewnode;returntrue;}需要注意的点记得delete 节点2.查找find过程从根开始比较查找 xx 比根的值大则往右边走查找x 比根值小则往左边走查找。最多查找高度次走到到空还没找到这个值不存在。如果不支持插入相等的值找到 x 即可返回如果支持插入相等的值意味着有多个 x 存在一般要求查找中序的第一个 x。如下图查找 3要找到 1 的右孩子的那个 3 返回但是下面主播的代码主要实现不含重复元素的插入主播的实现代码// 查找,找到在不在即可boolFind(constKkey){if(_rootnullptr)returnfalse;Node*cur_root;while(cur){if(keycur-_key)curcur-_left;elseif(keycur-_key)curcur-_right;elsereturntrue;}returnfalse;}3. 二叉搜索树的删除⭐️⭐️⭐️⭐️⭐️醋包饺这节最有价值的就是这个删除最重要的也是这个删除实现要点首先查找要删除的元素是否在二叉搜索树中如果不存在直接返回 false。如果查找元素存在则分以下四种情况分别处理假设要删除的结点为 N要删除结点 N 左右孩子均为空要删除的结点 N 左孩子位空右孩子结点不为空要删除的结点 N 右孩子位空左孩子结点不为空要删除的结点 N 左右孩子结点均不为空其中我们实现的时候大体可以分为两种情况1N有两个孩子2其他但是2其他这种情况更简单处理对于2其他我们只需要N的父母的指向N的指针指向N的左右里面的一个非空指针即可如果左右都为空那就自己指向空对于1我们采用了一种十分巧妙的方式替换删除法即找到一个可以接替N位置的节点X把X的值给N然后删除X即可。这里有一个二叉搜索树的性质可以接替N的节点要么是N的左子树的最大节点要么是N右子树的最小节点其中N左子树的最大节点就是左子树的最右节点N右子树的最小节点就是右子树的最左节点。1左右都为空2左为空或者右为空3左右都有孩子最复杂交换删除法主播的实现代码// 删除boolErase(constKkey){if(_rootnullptr)returnfalse;//根节点单独处理if(_root-_keykey){if(_root-_leftnullptr){Node*tmp_root;_root_root-_right;deletetmp;returntrue;}elseif(_root-_rightnullptr){Node*tmp_root;_root_root-_left;deletetmp;returntrue;}}//难点//先找到要删除的节点的位置//节点位置有两种情况//1至少有一边没有孩子那么就把另一边链接给父亲即可// 2该节点左右都有孩子——交换删除法//先找到该节点Node*targetnodenullptr;Node*cur_root;//Node* curparent nullptr;//非常关键啊//Node* curparent cur;//非常关键啊//while (cur)//{// curparent cur;// if (key cur-_key)// cur cur-_left;// else if (key cur-_key)// cur cur-_right;// else// {// targetnode cur;// break;// }//}//没有判断是否找到Node*curparentcur;while(cur){if(keycur-_key){curparentcur;curcur-_left;}elseif(keycur-_key){curparentcur;curcur-_right;}else{targetnodecur;break;}}//if (targetnode ! cur)return false;不能这么写if(targetnodenullptr)returnfalse;//先处理第一种情况;/*if (curparent-_left targetnode) { if (targetnode-_left nullptr) curparent-_left targetnode-_right; else curparent-_left targetnode-_left; }不能这么写*/if(targetnode-_leftnullptr){if(curparent-_lefttargetnode){curparent-_lefttargetnode-_right;}elsecurparent-_righttargetnode-_right;deletetargetnode;returntrue;}elseif(targetnode-_rightnullptr){if(curparent-_lefttargetnode){curparent-_lefttargetnode-_left;}elsecurparent-_righttargetnode-_left;deletetargetnode;returntrue;}else//左右都不为空第二种情况{//找到左边最大的那个节点或者右边最小的节点//左边最大也就是左边最靠右的节点//右边最小也就是右边最靠左的节点//我这里找右子树里面最靠左的节点//Node* swapnode targetnode;Node*swapnodetargetnode-_right;Node*swapnodeparentswapnode;while(swapnode-_left){swapnodeparentswapnode;swapnodeswapnode-_left;}//找到了先赋值targetnode-_keyswapnode-_key;//删除//swapnodeparent-_left swapnode-_right;//虽然是去右子树里面找最左边的节点但是不要以为全都是往左走所以swapnode一定是他父母的左节点有一个特殊情况就是第一步第一步他去右子树里面找他就是先往右走if(swapnodeparent-_leftswapnode)swapnodeparent-_leftswapnode-_right;else//swapnodeparent.rightswapnodeswapnodeparent-_rightswapnode-_right;deleteswapnode;returntrue;}}4主播在这次模拟实现时犯的几个错误1修改局部指针 ≠ 修改树结构记住改变局部指针只改变变量改变节点成员指针才改变数据结构2父节点的移动要和子节点的移动同时进行其中在实现删除函数接口时犯的错误⭐ 第一父节点必须在 cur 移动之前保存。⭐ 第二找右子树最小节点时虽然搜索路径是“向左”但它第一次可能是从父节点向右走所以替代节点不一定是父节点左孩子。⭐️ 第三第二种情况要特别注意N有两个孩子删除N时去右子树找最左边的那个孩子的时候找到的是N的右孩子的情况所以这里要把swapnode的parent设为N.7. 二叉搜索树 key 和 key/value 使用场景⭐️⭐️⭐️这里我们就要介绍两种二叉搜索树的使用场景也可以说是两种不同的二叉搜索树一种是key搜索场景即传入一个key判断里面有没有即可就是我们的后面要学习的set还有一种是key/value搜索场景即每一个key都有一个value和这个key绑定就是我们后面要学习的map我们刚刚实现的就是key场景的二叉搜索树,我们接下来就来实现key/value的二叉搜索树7.3 key/value 二叉搜索树代码实现其实非常简单就是在刚刚的基础上在Node节点里面多存入一个值value即可,注意其中的eraser和find是不用加value的因为与他无关templateclassK,classVstructBSTNode{// pairK, V _kv;K _key;V _value;BSTNodeK,V*_left;BSTNodeK,V*_right;BSTNode(constKkey,constVvalue):_key(key),_value(value),_left(nullptr),_right(nullptr){}};templateclassK,classVclassBSTree{typedefBSTNodeK,VNode;public:...boolInsert(constKkey,constVvalue){...}.......Node*Find(constKkey);boolErase(constKkey);private:Node*_rootnullptr;};下期预告map/set的使用结语本文到此结束感谢大家的阅读如果觉得本文对你有所帮助欢迎点赞、收藏、关注也欢迎在评论区一起交流讨论。也欢迎订阅我的深入理解 C系列从语法入门到底层原理系统掌握现代 C算法系列从入门到精通蓝桥杯、ACM、LeetCode 与面试算法全路线快速复习系列知识梳理、查漏补缺考前冲刺必备Java 速通系列已学 C 语言快速上手 Java轻松备战期末考试愿每一次敲下键盘都比昨天更进一步愿每一行代码落下都让未来多一种可能