二叉搜索树的概念二叉搜索树又称二叉排序树它或者是一颗空树或者是具有以下性质的二叉树●若它的左子树不为空则左子树上所有节点的值都小于等于根节点的值●若它的右子树不为空则右子树上所有节点的值都大于等于根节点的值●它的左右子树也分别为二叉搜索树●二叉搜索树可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义当我们使用map/set/multimap/multiset系列容器时它们的底层就是二叉搜索树其中map/set不支持插入相等的值multimap/multiset支持插入相等值因为这个“左小右大”的规则二叉搜索树拥有了非常高效的查找能力。同时对它进行中序遍历得到的结果就是从小到大有序的。这一点在我们后面的代码中会直接体现出来。二叉搜索树的性能特征任何数据结构的操作效率都和它的形状强相关。最优情况树长得像一棵“完全二叉树”或者说非常平衡树的高度 h 约等于 log₂N。此时插入、删除、查找的时间复杂度都是 O(log N)。最差情况插入的序列本身是有序的一直往右或一直往左树就退化成了一条“单链表”高度等于 N。此时复杂度退化为 O(N)。因此综合而言二叉搜索树增删查改的时间复杂度是O(N)。这显然不能满足工程要求所以后来才衍生出了 AVL 树和红黑树这样的“平衡二叉搜索树”。你可能会想二分查找也是 O(log N)为什么还要搞这么复杂的树结构二分查找虽然查找快但有两个致命缺陷数据必须存储在支持随机访问的结构如数组中并且要提前排好序插入和删除数据时数组需要挪动大量元素代价很高。平衡二叉搜索树则解决了“动态数据”的高效增删查问题。我们下面的代码实现的就是普通的二叉搜索树虽然它可能不平衡但其思想是后续一切平衡树的根基。二叉搜索树的实现节点结构体templateclassKstructBSTNode{K _key;BSTNodeK*_left;BSTNodeK*_right;BSTNode(constKkey):_key(key),_left(nullptr),_right(nullptr){}};节点包含三个成员_key、左孩子指针 _left、右孩子指针 _right。构造函数用初始化列表把所有成员初始化好左右指针初始为空。这里使用了模板 template让节点可以存任意类型的 keyint、string 等。BSTNode节点不需要拷贝构造。节点只存储数据和子节点指针不负责子节点内存释放编译器默认拷贝即可。二叉搜索树类的基本框架templateclassKclassBSTree{// 类型别名方便在类中使用//这里用到了 using Node BSTNodeK;等价于 typedef BSTNodeK Node;usingNodeBSTNodeK;public:// 默认构造编译器生成即可BSTree()default;// 拷贝构造BSTree(constBSTreet){_rootCopy(t._root);}// 赋值运算符重载BSTreeoperator(BSTree tmp){swap(_root,tmp._root);return*this;}// 析构函数~BSTree(){Destroy(_root);_rootnullptr;}// 核心操作增、查、删、遍历boolInsert(constKkey);boolfind(constKkey);boolErase(constKkey);voidInorder();private:// 内部递归辅助函数void_Inorder(Node*root);//私有成员函数BSTree类里面templateclassKBSTNodeK*Copy(BSTNodeK*root){//递归终止条件空节点直接返回nullptrif(rootnullptr){returnnullptr;}//复制当前节点new全新节点不是复用旧节点BSTNodeK*newNodenewBSTNodeK(root-_key);//递归拷贝左子树接到新节点左指针newNode-_leftCopy(root-_left);//递归拷贝右子树接到新节点右指针newNode-_rightCopy(root-_right);returnnewNode;}templateclassKvoidDestroy(BSTNodeK*root){if(rootnullptr)return;//后序遍历先销毁左、再销毁右最后销毁自己Destroy(root-_left);Destroy(root-_right);deleteroot;rootnullptr;}};BSTree树管理类必须实现拷贝构造做深拷贝。因为树拥有全部节点析构要销毁全部堆节点拷贝时递归Copy每一个节点都 new 出新对象得到完全独立的新树。深拷贝发生在树这一层递归遍历所有节点逐个新建而不是单个节点层面。插入操作 (Insert)(写在类里面)思路若树为空直接让根指向新节点。若树不空从根开始比较 插入值 大于 当前节点 → 往右走插入值 小于 当前节点 → 往左走若相等- 说明节点已存在插入失败我们实现的代码中不允许重复 key。 走到某个位置发现下一步是 nullptr那里就是该插入的位置。如果支持插入相等的值插入的值和当前结点的值相等可以往右走也可以往左走找到空位置插入新结点。要注意的是要保持逻辑一致性插入相等的值不要一会往右走一会往左走出于维护树结构需要我们在查找过程中要留下“父节点”的痕迹这样才能把新节点挂到父节点的左/右指针.boolInsert(constKkey){// 1. 空树直接成为根if(_rootnullptr){_rootnewNode(key);returntrue;}Node*parentnullptr;// 记录当前节点的父亲Node*cur_root;// 从根开始查找// 2. 找到插入位置while(cur){if(cur-_keykey){parentcur;curcur-_right;// 去右边找}elseif(cur-_keykey){parentcur;curcur-_left;// 去左边找}else{returnfalse;// 相等不允许重复插入失败}}// 3. 出来时 cur 为空parent 是待插入位置的父节点curnewNode(key);if(parent-_keykey){parent-_rightcur;// 比父亲大挂右边}else{parent-_leftcur;// 比父亲小挂左边}returntrue;}注parent 必须记录不然新节点不知道挂到哪个节点下。判断挂在左还是右取决于新 key 与 parent-_key 的大小关系。由于我们确认过 key 不等于 parent-_key否则早已返回 false所以只可能是大于或小于。查找操作 (find)查找逻辑和插入的“定位”过程几乎一模一样从根开始比当前节点大就往右小就往左等于就找到了。走到空还没找到说明不存在。如果支持插入相等的值意味着有多个相等的值存在一般要求查找 中序 的第一个相等的值。如下图查找3要找到1的右孩子的那个3返回。boolfind(constKkey){Node*cur_root;while(cur){if(cur-_keykey){curcur-_right;}elseif(cur-_keykey){curcur-_left;}else{returntrue;// 找到了}}returnfalse;// cur 为空没找到}查找是不修改树结构的所以不需要记录父节点只用跟着指针一路向下即可。时间复杂度为 O(高)删除操作 (Erase) —— 最复杂的部分删除操作是二叉搜索树里逻辑最繁重的一环。先整体梳理步骤1.先查找要删除的节点 cur同时记录它的父亲 parent。2.若没找到直接返回 false。3.若找到了分三种大情况处理其实可以归并为四种但代码实现时通常合并前两种情况分析假设待删节点为 N即代码里的 cur情况1N 是叶子节点左右孩子全为空直接把父节点指向它的指针置空然后 delete N。情况2N 只有一个孩子若 N 只有右孩子让 N 的父节点原来指向 N 的指针改为指向 N 的右孩子delete N。若 N 只有左孩子让 N 的父节点原来指向 N 的指针改为指向 N 的左孩子delete N。代码实现时我们把情况一和情况二进行了合并情况3N 有两个孩子这是最棘手的情况。我们不能直接删掉 N因为它的两个孩子无处安放。解决办法是替换法找一个“替身”节点 R将它的值赋给 N覆盖掉 N 的 key然后改为删除 R。R 必须满足放在 N 的位置上不会破坏二叉搜索树的性质。通常选 N 的右子树中的最小节点即右子树最左侧节点或者 N 的左子树中的最大节点即左子树最右侧节点。本文代码的实现选择的是右子树最小节点。这样选择的节点 R 必然最多只有一个孩子右孩子这样就可以转化为情况1或情况2来删除。代码分布拆解boolErase(constKkey){Node*parentnullptr;Node*cur_root;// 1. 查找待删节点while(cur){if(cur-_keykey){parentcur;curcur-_right;}elseif(cur-_keykey){parentcur;curcur-_left;}else// 找到了执行删除{// 进入具体删除逻辑...}}returnfalse;// 查找失败}找到之后,进入删除逻辑左孩子为空包括了叶子节点和只有右孩子的情况if(cur-_leftnullptr){if(parentnullptr)// 要删的是根节点且根没有左子树{_rootcur-_right;}else{if(parent-_leftcur)// cur 是父亲的左孩子parent-_leftcur-_right;else// cur 是父亲的右孩子parent-_rightcur-_right;}deletecur;returntrue;}当 cur-_left 为 nullptr 时无论右孩子是否为空处理方法都是把右孩子交给父亲。右孩子若为空那父亲就指向了空也就是删除叶子逻辑完全正确。特殊判断 parent nullptr当要删除的节点恰好是整棵树的根时父亲不存在只能直接修改 _root。右孩子为空对称情况elseif(cur-_rightnullptr){if(parentnullptr){_rootcur-_left;}else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}deletecur;returntrue;}原理和上面一样不再赘述。注意这里用的是 else if能够走到这里说明 cur-_left ! nullptr也就是该节点有左孩子但无右孩子。左右孩子都不为空 —— 替换法else{// 选右子树的最小节点作为替身Node*replaceParentcur;// 注意不能初始化为 nullptrNode*replacecur-_right;// 右子树的根// 一路向左找到最左节点while(replace-_left){replaceParentreplace;replacereplace-_left;}// 将替身节点的值赋给待删节点覆盖cur-_keyreplace-_key;// 现在需要删除 replace 这个节点// replace 一定没有左孩子因为已经是“最左”了// 但它可能有右孩子需要将 replace 的父亲指向它的右孩子if(replaceParent-_leftreplace)replaceParent-_leftreplace-_right;elsereplaceParent-_rightreplace-_right;deletereplace;returntrue;}几个关键问题为什么 replaceParent 不能初始化为 nullptr而必须是 cur因为要找的是要删除节点的右子树的最小节点。如果右子树的根节点指的是cur的右孩子节点 cur-_right 就没有左孩子那么它本身就是最小节点不会进入while循环。这时候 replaceParent 如果还是 nullptr后面删除 replace 时会出现空指针访问。用 cur 作为初始父节点就涵盖了“最小节点就是右子树根”的情况此时 while 循环不会进入replaceParent 就是 curreplace 是 cur-_right后续的链接逻辑仍然正确.为什么可以直接覆盖 cur-_key我们只是把“替身”的值拷贝给了待删节点树的结构并没有被破坏。而替身节点本身的结构位置、子树关系将被移除。删除替身节点时的父子关系处理replace 必然没有左孩子但可能有右子树。需要正确地将 replaceParent 的左或右指针连接到 replace-_right。如果 replace 是 replaceParent 的左孩子就接左指针否则即 replace 就是 replaceParent 的右孩子这种情况发生在最小节点就是 cur-_right 时就接右指针。这个判断非常关键不能想当然地认为 replace 一定是左孩子。至此删除操作全部完成。完整删除函数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*replaceParentcur;Node*replacecur-_right;while(replace-_left){replaceParentreplace;replacereplace-_left;}cur-_keyreplace-_key;if(replaceParent-_leftreplace)replaceParent-_leftreplace-_right;elsereplaceParent-_rightreplace-_right;deletereplace;returntrue;}}}returnfalse;// 没找到要删除的元素}中序遍历与有序输出二叉搜索树的中序遍历会得到一个升序序列这时我们可以通过中序验证树结构的正确性。voidInorder(){_Inorder(_root);coutendl;}private:void_Inorder(Node*root){if(rootnullptr){return;}_Inorder(root-_left);// 左coutroot-_key ;// 根_Inorder(root-_right);// 右}为什么需要一个公有的 Inorder 和私有的 _Inorder 呢因为二叉树的很多操作都需要传入节点指针 Node* root但这个指针是树的私有成员 _root用户无法直接获取。因此对外接口就是无参的内部调用带参的私有函数这种设计称为 “接口与实现分离”。对外接口 Inorder() 封装了递归函数外部不用关心根节点只需调用。二叉搜索树key和key/value的使用场景key搜索场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的只搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。场景1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在则抬杆不在则提示非本小区车辆无法进入。场景2检查一篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不在则波浪线标红提示。intmain(){BSTreeintt;inta[]{8,3,1,10,6,4,7,14,13};for(autoe:a){t.Insert(e);}t.Inorder();// 1 3 4 6 7 8 10 13 14// 依次删除所有节点每删一个就遍历一次观察是否仍然有序for(autoe:a){t.Erase(e);t.Inorder();}return0;}key/value搜索场景每一个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中节点除了需要存储还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的valuekey/value的搜索场景实现的二叉搜索树支持修改但是不支持修改key修改key破环搜索树性质了可以修改value。比如电子词典英文单词为 key中文释义为 value。车库计费车牌号为 key入场时间为 value。单词统计单词为 key出现次数为 value。在 KV 模型中key 依然负责比较定位value 只负责存储关联数据。增、删、查操作仍然按照 key 的大小规则进行。KV 模型节点定义templateclassK,classVstructBSTNode{K _key;V _value;BSTNodeK,V*_left;BSTNodeK,V*_right;BSTNode(constKkey,constVvalue):_key(key),_value(value),_left(nullptr),_right(nullptr){}};多了一个模板参数 V节点中多了 _value 成员。KV 模型的 BSTree 类框架这里的拷贝控制和我们上面实现的K模型相同templateclassK,classVclassBSTree{usingNodeBSTNodeK,V;public:BSTree()default;// 默认构造BSTree(constBSTreet)// 拷贝构造{_rootCopy(t._root);}BSTreeoperator(BSTree tmp)// 赋值运算符{swap(_root,tmp._root);return*this;}~BSTree()// 析构{Destroy(_root);_rootnullptr;}// ... 其他操作private:Node*_rootnullptr;};KV 模型的 Insert、find、Erase 与 K 模型的逻辑相同只是节点多了 value查找返回的是节点指针而不是 bool以便获取 value。Insert 示例boolInsert(constKkey,constVvalue){if(_rootnullptr){_rootnewNode(key,value);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_keykey)// 比当前 key 大向右{parentcur;curcur-_right;}elseif(cur-_keykey)// 小向左{parentcur;curcur-_left;}else{returnfalse;// 相等不插入}}curnewNode(key,value);if(parent-_keykey)parent-_rightcur;elseparent-_leftcur;returntrue;}find 返回指针Node*find(constKkey){Node*cur_root;while(cur){if(cur-_keykey)curcur-_right;elseif(cur-_keykey)curcur-_left;elsereturncur;// 返回节点指针可通过它修改 value}returnnullptr;}删除逻辑 Erase 与 K 模型完全一致。KV 模型应用场景统计水果出现次数intmain(){string arr[]{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};key_value::BSTreestring,intcountTree;for(constautostr:arr){autoretcountTree.find(str);if(retnullptr)// 第一次出现{countTree.Insert(str,1);}else// 已经存在次数1{ret-_value;}}countTree.Inorder();// 输出苹果:6 西瓜:3 香蕉:2// 测试拷贝功能key_value::BSTreestring,intcopycountTree;copy.Inorder();return0;}代码的工作原理每读到一个水果先查找它是否已在树中。如果不存在插入 水果, 1。如果存在将对应节点的 _value 加一。代码中的细节尽管我们在上面逐段分析过但想真正吃透下面几点需要特别牢记删除有两个孩子节点的 replaceParent 初始化Node* replaceParent cur; 而不是 nullptr。这是防止 cur-_right 没有左子树时循环完全不执行replaceParent 若为 nullptr后面判断 replaceParent-_left 就会挂掉 !!删除 replace 节点时的链接判定if(replaceParent-_leftreplace)replaceParent-_leftreplace-_right;elsereplaceParent-_rightreplace-_right;不能因为“反正是最左节点”就只写 _left必须判断。查找与插入中的 key 比较一致性整个逻辑统一左小右大比较时只用 _key 。KV 模型通过 key 查找并修改 value绝不会修改 key否则会破坏二叉搜索树结构。递归中序遍历是理解 BST 的关键二叉搜索树的中序序列一定是升序这为我们验证程序正确性或调试提供了极大的便利。任何时候对树进行增删后执行一次 Inorder观察输出是否仍有序基本就能判断逻辑是否出错