c++二叉搜索树

文章目录

一、二叉搜索树的概念

           1.二叉搜索树，是一个空树或者具有以下性质的二叉树：

              若左子树不为空，那么左子树上所有结点的值都小于等于<=根结点的值

              若右子树不为空，那么右子树上所有结点的值都大于等于>=根结点的值

              左右子树也分别为二叉搜索树

           2.二叉搜索树又称作二叉排序树，原因：

              当二叉搜索树进行中序遍历时，左根右，所遍历出来的结果是升序的

           3.二叉搜索树既可以支持插入相等的值，也可以不支持插入相等的值

              map/set/multimap/multiset的底层就是二叉搜索树

              其中map/set不支持插入相等的值，multimap/multiset支持插入相等的值

二、二叉搜索树性能分析

           1.最优情况下，二叉搜索树为完全二叉树（接近于完全二叉树）高度为logN

              此时查找的时间复杂度为logN

           2.最差情况下，二叉搜索树退化为单支树（或类似于单支）高度为N

              此时查找的时间复杂度为N

           3.结合1和2得出二叉搜索树的查找时间复杂度为N

           4.二叉搜索树的插入、删除、查找时间复杂度为N、

           5.为了解决二叉搜索树的查找时间复杂度为N的问题，也就是为了避免出现单支树的情况

              所以后续会引出平衡二叉搜索树（AVL树 or 红黑树）

              平衡二叉树就会使得查找的时间复杂度为logN

           6.另外，二分查找也可以使得查找的效率为logN，但是二分查找有两个显著缺陷：

           （1）二分查找要求存储在支持下标[]随机访问的结构中，并且有序

           （2）正因为二分查找存储在支持下标[]随机访问的结构中，所以当需要插入和删除数据时

                    效率低下，插入删除需要挪动数据               

三、二叉搜索树的插入

           1.二叉搜索树的结构              

           2.插入具体过程：

            （1）如果_root根结点为nullptr，那么直接在_root根节点位置进行插入

            （2）如果_root不为nullptr，那么根据二叉搜索树的性质与当前结点进行比较

                     如果插入的值小于当前结点，那么往当前结点的左子树走

                     如果插入的值大于当前结点，那么往当前结点的右子树走

                     找到空位置进行插入

            （3）如果支持插入相等的值，插入的值根当前结点的值一样，那么既可以往左走也可以往

                     右走找到空位置，插入新结点（要注意保持逻辑的一致性，插入相等的值不要一会

                     往左走，一会儿往右走）                

        3.当二叉搜索树插入之后，那么为了看到输出，需要写遍历，而二叉搜索树的遍历只有中序

           遍历才是有意义的

           但是中序遍历是递归，递归是需要传参的，而参数为_root也就是根结点私有成员

           在类外是无法访问到私有成员的，所以我们可以对这种情况进行封装            

四、二叉搜索树的查找

           1.从根结点开始比较，查找x，如果x比根的值小就往左查找，如果x比根的值大就往右查找

           2.最多查找高度次，如果走到空还没有找到，那么该值不存在

           3.如果不支持插入相等的值，那么查到到x就进行返回

           4.如果支持插入相等的值，意味着着有多个x存在，一般情况下查找到第一个就进行返回      

五、二叉搜索树的删除

           1.删除的结点为叶子结点，左右子树皆为空

              将该结点的父结点的指向改为nullptr，直接删除该结点

           2.删除的结点左子树为空，右子树不为空

              将该结点的父结点的指向改为该结点的右子树，然后删除该结点

           3.删除的结点右子树为空，左子树不为空

              将该结点的父结点的指向改为该节点的左子树，如果删除该结点

           4.根据2和3，就可以将1划为2or3中的其中一类

            （1）删除叶子结点，左右子树皆为空，就可以归为左子树为空/右子树为空

            （2）将删除的叶子结点的父结点的指向改为叶子结点的左子树or右子树也就是nullptr

           5.删除的结点左右子树皆不为空

            （1）找到左子树中最右的结点（最大结点）

                     该结点一定比整个左子树要大，但是比右子树要小，可以跟被删除的结点进行替换

            （2）或者找到右子树的最左结点（最小结点）

                     该结点一定比整个右子树要小，但是比左子树要大，可以跟被删除的结点进行替换

            （3）替换过后，此时需要删除的结点就在左子树的最右or右子树的最左

            （4）左子树的最右结点一定是可以直接删除的，因为该结点肯定没有右子树

                     无论是否有左子树，只需要将最右结点的父结点的指向改为该结点的左子树即可

            （5）右子树的最左结点一定是可以直接删除的，因为该结点肯定没有左子树

                     无论是否有右子树，只需要将最左结点的父结点的指向该为该结点的右子树即可        

六、二叉搜索树完整代码

           1.二叉搜索树深拷贝与析构

           （1）拷贝构造    

            （2）赋值运算符重载

            （3）析构函数                 

            2.完整代码

七、二叉搜索树key和key/value使用场景

           1.key场景

           （1）key场景就只是单纯的查找

           （2）例1：

                    小区停车场识别车辆进入

                    将购买车位的车辆的号码牌进行存储，然后当车辆进入时查找该车牌号是否在

                    二叉搜索树中，在就抬杆让车辆进入，不在就输出非小区车辆禁止入内                   

           （3）例2：

                    检查⼀篇英文文章单词拼写是否正确

                    将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，

                    不在则波浪线标红提示

          2.key/value场景

           （1）存储key时附带存储相关的value

           （2）查找key时可以顺带查找到value，通过key找到value

           （3）在二叉搜索树的核心逻辑中value不参与

           （4）二叉搜索树中是不支持key进行修改，因为会影响整个二叉搜索树的结构

                    但是在key_value的场景下，value是可以进行修改的

           （5）例1：

                    商场停车场是需要收费的，那么车辆在进入时不仅仅需要存储车辆的车牌号，还需要

                    车辆的入场时间，那么就可以使用key/value的场景，key存储车辆的车票号，value

                    存储入场时间

           （6）例2：

                     简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，

                     搜索时输入英文，则同时查找到了英文对应的中文

           （7）例3：

                    统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说

                    明第一次出现存储（单词，1），单词存在，则++单词对应的次数

                     key为单词，value为次数（key不可以改变，value可以改变）

           （8）key/value实现代码

                    只需要在实现关于入数据的代码时，添加value即可               

                    value不参与二叉搜索树的核心逻辑，二叉搜索树的核心逻辑都是根据key进行操作