目录1. 二叉搜索树的概念2. 二叉搜索树的性能分析3. 二叉搜索树的插入4. 二叉搜索树的查找5. 二叉搜索树的删除6. 二叉搜索树的实现代码7. 二叉搜索树 key 和 key/value 使用场景7.1 key 搜索场景7.2 key/value 搜索场景7.3 key/value 二叉搜索树代码实现1. 二叉搜索树的概念二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值。若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值。它的左右子树也分别为二叉搜索树。二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义。后续学习的map、set、multimap、multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值。2. 二叉搜索树的性能分析最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其高度为log_2(N)。最差情况下二叉搜索树退化为单支树或者类似单支其高度为N NN。所以综合而言二叉搜索树增删查改时间复杂度为O ( N ) O(N)O(N)。那么这样的效率显然是无法满足我们需求的我们后续课程需要继续讲解二叉搜索树的变形平衡二叉搜索树 AVL 树和红黑树才能适用于我们在内存中存储和搜索数据。另外需要说明的是二分查找也可以实现O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)级别的查找效率但是二分查找有两大缺陷需要存储在支持下标随机访问的结构中并且有序。插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。这里也就体现出了平衡二叉搜索树的价值。3. 二叉搜索树的插入插入的具体过程如下树为空则直接新增结点赋值给root指针。树不空按二叉搜索树性质插入值比当前结点大往右走插入值比当前结点小往左走找到空位置插入新结点。如果支持插入相等的值插入值跟当前结点相等的值可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走。inta[]{8,3,1,10,6,4,7,14,13};4. 二叉搜索树的查找从根开始比较查找x。x比根的值大则往右边走查找x比根值小则往左边走查找。最多查找高度次走到空还没找到这个值不存在。如果不支持插入相等的值找到x即可返回。如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回。5. 二叉搜索树的删除首先查找元素是否在二叉搜索树中如果不存在则返回false。如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N要删除结点N左右孩子均为空。要删除的结点N左孩子为空右孩子结点不为空。要删除的结点N右孩子为空左孩子结点不为空。要删除的结点N左右孩子结点均不为空。对应以上四种情况的解决方案把N结点的父亲对应孩子指针指向空直接删除N结点情况 1 可以当成情况 2 或者情况 3 处理效果是一样的。把N结点的父亲对应孩子指针指向N的右孩子直接删除N结点。把N结点的父亲对应孩子指针指向N的左孩子直接删除N结点。无法直接删除N结点因为N的两个孩子无处安放只能用替换法删除。找N左子树的值最大结点R最右结点或者N右子树的值最小结点R最左结点替代N因为这两个结点中任意一个放到N的位置都满足二叉搜索树的规则。替代N的意思就是N和R两个结点的值交换转而变成删除R结点R结点符合情况 2 或情况 3可以直接删除。6. 二叉搜索树的实现代码templateclassKstructBSTNode{K _key;BSTNodeK*_left;BSTNodeK*_right;BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}};// Binary Search TreetemplateclassKclassBSTree{typedefBSTNodeKNode;public:boolInsert(constKkey){if(_rootnullptr){_rootnewNode(key);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(key);if(parent-_keykey){parent-_rightcur;}else{parent-_leftcur;}returntrue;}boolFind(constKkey){Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;}}returnfalse;}boolErase(constKkey){Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{// 0-1个孩子的情况// 删除情况1、2、3均可以直接删除改变父亲对应孩子指针指向即可if(cur-_leftnullptr){if(parentnullptr){_rootcur-_right;}else{if(parent-_leftcur)parent-_leftcur-_right;elseparent-_rightcur-_right;}deletecur;returntrue;}elseif(cur-_rightnullptr){if(parentnullptr){_rootcur-_left;}else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}deletecur;returntrue;}else{// 2个孩子的情况// 删除情况4替换法删除// 假设这里我们取右子树的最小结点作为替代结点去删除// 这里尤其要注意右子树的根就是最小结点时的处理对应课件图中删除8的情况// 一定要把cur给rightMinP否则会报错。Node*rightMinPcur;Node*rightMincur-_right;while(rightMin-_left){rightMinPrightMin;rightMinrightMin-_left;}cur-_keyrightMin-_key;if(rightMinP-_leftrightMin)rightMinP-_leftrightMin-_right;elserightMinP-_rightrightMin-_right;deleterightMin;returntrue;}}}returnfalse;}voidInOrder(){_InOrder(_root);coutendl;}private:void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_key ;_InOrder(root-_right);}private:Node*_rootnullptr;};7. 二叉搜索树 key 和 key/value 使用场景7.1 key 搜索场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。场景 1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在则抬杆不在则提示非本小区车辆无法进入。场景 2检查一篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不在则波浪线标红提示。7.2 key/value 搜索场景每一个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中结点除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改但是不支持修改key修改key破坏搜索树性质了可以修改value。场景 1简单中英互译字典树的结构中结点存储key英文和value中文搜索时输入英文则同时查找到了英文对应的中文。场景 2商场无人值守车库入口进场时扫描车牌记录车牌和入场时间出口离场时扫描车牌查找入场时间用当前时间 - 入场时间计算出停车时长计算出停车费用缴费后抬杆车辆离场。场景 3统计一篇文章中单词出现的次数读取一个单词查找单词是否存在不存在这个说明第一次出现单词1单词存在则单词对应的次数。7.3 key/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:BSTree()default;BSTree(constBSTreeK,Vt){_rootCopy(t._root);}BSTreeK,Voperator(BSTreeK,Vt){swap(_root,t._root);return*this;}~BSTree(){Destroy(_root);_rootnullptr;}boolInsert(constKkey,constVvalue){if(_rootnullptr){_rootnewNode(key,value);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(key,value);if(parent-_keykey){parent-_rightcur;}else{parent-_leftcur;}returntrue;}Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returncur;}}returnnullptr;}boolErase(constKkey){Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else{if(cur-_leftnullptr){if(parentnullptr){_rootcur-_right;}else{if(parent-_leftcur)parent-_leftcur-_right;elseparent-_rightcur-_right;}deletecur;returntrue;}elseif(cur-_rightnullptr){if(parentnullptr){_rootcur-_left;}else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}deletecur;returntrue;}else{Node*rightMinPcur;Node*rightMincur-_right;while(rightMin-_left){rightMinPrightMin;rightMinrightMin-_left;}cur-_keyrightMin-_key;if(rightMinP-_leftrightMin)rightMinP-_leftrightMin-_right;elserightMinP-_rightrightMin-_right;deleterightMin;returntrue;}}}returnfalse;}voidInOrder(){_InOrder(_root);coutendl;}private:void_InOrder(Node*root){if(rootnullptr){return;}_InOrder(root-_left);coutroot-_key:root-_valueendl;_InOrder(root-_right);}voidDestroy(Node*root){if(rootnullptr)return;Destroy(root-_left);Destroy(root-_right);deleteroot;}Node*Copy(Node*root){if(rootnullptr)returnnullptr;Node*newRootnewNode(root-_key,root-_value);newRoot-_leftCopy(root-_left);newRoot-_rightCopy(root-_right);returnnewRoot;}private:Node*_rootnullptr;};字典示例intmain(){BSTreestring,stringdict;//BSTreestring, string copy dict;dict.Insert(left,左边);dict.Insert(right,右边);dict.Insert(insert,插入);dict.Insert(string,字符串);string str;while(cinstr){autoretdict.Find(str);if(ret){cout-ret-_valueendl;}else{cout无此单词请重新输入endl;}}return0;}统计单词出现次数示例intmain(){string arr[]{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};BSTreestring,intcountTree;for(constautostr:arr){// 先查找水果在不在搜索树中// 1、不在说明水果第一次出现则插入水果1// 2、在则查找到的结点中水果对应的次数//BSTreeNodestring, int* ret countTree.Find(str);autoretcountTree.Find(str);if(retNULL){countTree.Insert(str,1);}else{ret-_value;}}countTree.InOrder();return0;}