0
0

【初阶与进阶C++详解】第十六篇：AVL树-平衡搜索二叉树（定义+插入+旋转+验证）

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

  • C语言初阶和进阶
  • C项目
  • Leetcode刷题
  • 初阶数据结构与算法
  • C++初阶和进阶
  • 《深入理解计算机操作系统》
  • 《高质量C/C++编程》
  • Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector(vector接口介绍+vector模拟实现+vector迭代器区间构造/拷贝构造/赋值)

【初阶与进阶C++详解】第十篇：list(list接口介绍和使用+list模拟实现+反向迭代器和迭代器适配)

【初阶与进阶C++详解】第十一篇：stack+queue+priority_queue+deque（仿函数）

【初阶与进阶C++详解】第十二篇：模板进阶(函数模板特化+类模板特化+模板分离编译)

【初阶与进阶C++详解】第十三篇：继承(菱形继承+菱形虚拟继承+组合)

【初阶与进阶C++详解】第十四篇：多态（虚函数+重写（覆盖）+抽象类+单继承和多继承）

【初阶与进阶C++详解】第十五篇：二叉树搜索树（操作+实现+应用KVL+性能+习题）

文章目录

💎一、AVL树概念

二叉搜索树虽可以缩短查找的效率(logN)，但如果数据有序或接近有序二叉搜索树将退化为单支树(On)，查找元素相当于在顺序表中搜索元素，效率低下。

平衡树也是搜索二叉树，其引入了一个平衡因子的概念，用于控制搜索二叉树的平衡。它会保证左右子树的高度之差（绝对值）不超过1。当新插入节点导致高度之差超过1时，便会触发旋转，使得树的高度降低，稳定了二叉搜索树效率。

  • 它的左右子树都是AVL树
  • 左右子树高度之差的绝对值（也叫平衡因子）不超过1
  • 平衡因子= 右子树高度 - 左子树高度

在这里插入图片描述

💎二、AVL树节点的定义

这里节点是一个三叉链，里面存放了元素的数据和该节点此时的平衡因子。

  • 左右子树高度相同 0
  • 左子树高于右子树 -1
  • 右子树高于左子树 1
template<classK,classV>structAVLTreeNode{
    pair<K, V> _kv;//键值对
    AVLTreeNode<K, V>* _left;//左子树
    AVLTreeNode<K, V>* _right;//右子树
    AVLTreeNode<K, V>* _parent;//父节点// 右子树-左子树的高度差int _bf;// 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

💎三、AVL树插入

🏆1.平衡因子的调节

AVL需要控制高度，所以每次插入我们都需要更新判断树节点的平衡因子是否符合要求

思路：

  • 如果是空树，给root new一个新节点
  • 根据二叉搜索树的规则（左小右大规则）来找到新节点应该插入的位置，进行插入
  • 插入之后，需要向上更新平衡因子（可能包括多个祖先），如果该插入节点在父节点的右边，平衡因子+1，如果在该节点的左边，平衡因子-1。
  • parent更新后的平衡因子为1或-1，则说明在parent的右边或者左边新增了结点，从而影响了parent的父亲结点所以要继续往上更新平衡因子。在这里插入图片描述
  • parent更新后的平衡因子为0，说明插入前父亲的平衡因子为1或-1经过++或- -变成0的，说明新增结点在parent矮的一侧使得parent的左右子树一样高，不会影响parent的父亲结点，就不用往上更新平衡因子。在这里插入图片描述
  • 如果平衡因子的绝对值等于2，已经不满足AVL树，说明当前就需要旋转在这里插入图片描述

框架代码：

boolInsert(const pair<K, V>& kv){// 1、搜索树的规则插入// 2、看是否违反平衡规则，如果违反就需要处理：旋转//判断为空树if(_root ==nullptr){
            _root =newNode(kv);
            _root->_bf =0;returntrue;}//同步kvl操作
        Node* parent =nullptr;
        Node* cur = _root;while(cur){//判断key的插入位置if(cur->_kv.first < kv.first){
                parent = cur;
                cur = cur->_right;}elseif(cur->_kv.first > kv.first){
                parent = cur;
                cur = cur->_left;}else{returnfalse;}}//找到位置后插入节点
        cur =newNode(kv);if(parent->_kv.first < kv.first){
            parent->_right = cur;}else{
            parent->_left = cur;}

        cur->_parent = parent;//插入之后需要向上更新平衡因子while(parent)// 最远要更新根{if(cur == parent->_right){
                parent->_bf++;}else{
                parent->_bf--;}//更新了之后，需要判断是否继续更新，还是需要旋转// 原来是1 or -1  变成 0  插入节点填上矮的那边if(parent->_bf ==0){// 高度不变，更新结束break;}elseif(parent->_bf ==1|| parent->_bf ==-1)// 原来是0  变成 1 或 -1  插入节点导致一边变高了{// 子树的高度变了，继续更新祖先
                cur = cur->_parent;//向上更新
                parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2)// 原来是-1 or 1  变成 2 或 -2  插入节点导致本来高一边又变高了{// 子树不平衡，旋转if(parent->_bf ==2&& cur->_bf ==1)// 左单旋{RotateL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==-1)// 右单旋{RotateR(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1)// 左右双旋{RotateLR(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1)// 右左双旋{RotateRL(parent);}break;}else{// 插入之前AVL就存在不平衡子树assert(false);}}returntrue;}

💎四、AVL树旋转（重点）

1.1左单旋（新插入的节点在右子树的右侧）

步骤：让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0。

在这里插入图片描述

代码部分：

voidRotateL(Node* parent){
        Node* subR = parent->_right;
        Node* subRL = subR->_left;// 1.先让把subR的左边（可能为空也可能不为空）作为parent的右边
        parent->_right = subRL;// 2.如果subRL不为空，就让subRL的父指针指向parentif(subRL)
            subRL->_parent = parent;// 3.先记录parent的父节点的位置，然后把parent作为subR的左边 
        Node* ppNode = parent->_parent;
        subR->_left = parent;// 4.parent的父指针指向subR
        parent->_parent = subR;// 5.如果ppNode为空==>说明subR现在是根节点，就让subR的父指针指向nullptr//不是根节点就把subR的父指针指向parent的父节点，parent的父节点（左或右）指向subRif(parent == _root){// 更新根节点
            _root = subR;
            _root->_parent =nullptr;}else{// 判断parent是ppNode的左还是右if(parent == ppNode->_left){
                ppNode->_left = subR;}else{
                ppNode->_right = subR;}

            subR->_parent = ppNode;}// 6.把parent和subR的平衡因子更新为0
        subR->_bf = parent->_bf =0;}

1.2右单旋（新节点插入到较高左子树的左侧）

步骤： 让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0

在这里插入图片描述

代码部分：

voidRotateR(Node* parent){//让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
    Node* subL = parent->_left;
    Node* subLR = subL->_right;// 1.先让把subL的右边（可能为空也可能不为空）作为parent的左边
    parent->_left = subLR;// 2.如果subLR存在，就让subLR的父指针指向parentif(subLR)
        subLR->_parent = parent;// 3.先记录parent的父节点的位置，然后把parent作为subL的右边
    Node* ppNode = parent->_parent;
    subL->_right = parent;// 4.parent的父指针指向subL
    parent->_parent = subL;// 5.如果parent为根节点，则让subL成为新的根节点if(parent == _root){// 更新根节点
        _root = subL;
        _root->_parent =nullptr;}//如果不是根节点，则改变subL与其祖父节点的指向关系else{// 判断parent是ppNode的左还是右if(ppNode->_left == parent){
            ppNode->_left = subL;}else{
            ppNode->_right = subL;}
        subL->_parent = ppNode;}// 6.把parent和subL的平衡因子更新为0
    subL->_bf = parent->_bf =0;}

两种单旋的情况：

​ 左单旋，prev平衡因子为2,subR平衡因子为1，需要左单旋

在这里插入图片描述

右单旋，prev平衡因子为-2,subL平衡因子为-1，需要右单旋

在这里插入图片描述

总结：当父节点的平衡因子的绝对值超过1，其左/右边节点的平衡因子为1且和父节点平衡因子的正负相同时，需要向另外一个方向进行单旋

//插入函数的旋转部分elseif(parent->_bf ==2|| parent->_bf ==-2){if(parent->_bf ==2&& cur->_bf ==1){RotateL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==-1){RotateR(parent);}else{//左右双旋，右左双旋}break;}

1.3右左双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

步骤：先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子

如果subRL的平衡因子为0，就将它们依次改为0，0, 0；本身就是新增节点
如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；

在这里插入图片描述
如果subRL的平衡因子为-1，就将它们依次改为0，0, 1

在这里插入图片描述

// 右左旋转==>parent->_bf==2&&cur->_bf==-1voidRotateRL(Node* parent){
    Node* subR = parent->_right;
    Node* subRL = subR->_left;// 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树,调节旋转完后的平衡因子int bf = subRL->_bf;//先右单旋将折线结构转换为直线结构RotateR(parent->_right);//然后再左单旋RotateL(parent);// 从左到右 parent subRL subRif(bf ==0)// subRL的左子树  bf: 0 0 0{
        subRL->_bf =0;
        parent->_bf =0;
        subR->_bf =0;}elseif(bf ==1)// subRL的右子树 bf: -1 0 0{
        subRL->_bf =0;
        parent->_bf =-1;
        subR->_bf =0;}elseif(bf ==-1)// subRL的左子树  bf: 0 0 1{
        subRL->_bf =0;
        parent->_bf =0;
        subR->_bf =1;}else{// subLR->_bf旋转前就有问题assert(false);}}

1.4左右双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）

步骤：先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子

如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；

在这里插入图片描述
如果subLR的平衡因子为-1，就将它们依次改为0，0, 1

在这里插入图片描述

// 左右旋转==>parent->_bf==-2&&cur->_bf==1voidRotateLR(Node* parent){ 
    Node* subL = parent->_left;
    Node* subLR = subL->_right;int bf = subLR->_bf;// 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树,调节旋转完后的平衡因子//先左单旋将折线结构转换为直线结构RotateL(parent->_left);//然后再右单旋RotateR(parent);// 从左到右 parent subRL subRif(bf ==0)// subRL的左子树  bf: 0 0 0{
        parent->_bf =0;
        subL->_bf =0;
        subLR->_bf =0;}elseif(bf ==1)// subLR的右子树 bf: -1 0 0{
        parent->_bf =0;
        subL->_bf =-1;
        subLR->_bf =0;}elseif(bf ==-1)// subLR的左子树  bf: 0 0 1{
        parent->_bf =1;
        subL->_bf =0;
        subLR->_bf =0;}else{// subLR->_bf旋转前就有问题assert(false);}}

💎五、AVL树验证

AVL树有两点需要验证，通过高度判断，子树两边高度是否平衡，根据二叉搜索树的特性，判断平衡因子是否符合

//计算高度int_Height(Node* root){if(root ==nullptr)return0;int lh =_Height(root->_left);int rh =_Height(root->_right);//如果左子树高于右子树，就返回左子树+1（根）return lh > rh ? lh +1: rh +1;}//判断是否为平衡二叉树bool_IsBalanceTree(Node* root){// 空树也是AVL树if(nullptr== root)returntrue;// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则违反规则，则一定不是AVL树if(abs(diff)>=2){
        cout << root->_kv.first <<"节点平衡因子异常"<< endl;returnfalse;}if(diff != root->_bf){
        cout << root->_kv.first <<"节点平衡因子不符合实际"<< endl;returnfalse;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

实例演示：

voidTestAVLTree2(){const size_t N =1024*1024;
    vector<int> v;
    v.reserve(N);srand(time(0));//使用随机数for(size_t i =0; i < N;++i){
        v.push_back(rand());//v.push_back(i);}

    AVLTree<int,int> t;for(auto e : v){
        t.Insert(make_pair(e, e));}

    cout <<"是否平衡?"<< t.IsBalanceTree()<< endl;
    cout <<"高度:"<< t.Height()<< endl;}

💎六、AVL树删除(了解)

思路：

1.按照二叉搜索树的规则删除

2.更新平衡因子，并且进行旋转来调整（最坏情况下可能会一直调整到根节点）。

boolErase(const K& key){if(_root ==nullptr)returnfalse;// 有节点时插入
    Node* parent =nullptr;
    Node* cur = _root;while(cur){// 小于往左走if(key < cur->_kv.first){
            parent = cur;
            cur = cur->_left;}// 大于往右走elseif(key > cur->_kv.first){
            parent = cur;
            cur = cur->_right;}else{// 找到了// 1.左边为空，把parent指向cur的右// 2.右边为空，把parent指向cur的左// 3.左右都不为空，用右子树的最左边的节点（最小节点）的值替换要删除的节点，然后转换为用1的情况删除该节点if(cur->_left ==nullptr){if(cur == _root){
                    _root = cur->_right;delete cur;break;}else{if(parent->_left == cur){
                        parent->_left = cur->_right;
                        parent->_bf++;}else{
                        parent->_right = cur->_right;
                        parent->_bf--;}}if(parent->_bf !=-1&& parent->_bf !=1)AfterEraseUpdateBf(parent);delete cur;}elseif(cur->_right ==nullptr){if(cur == _root){
                    _root = cur->_left;delete cur;break;}else{if(parent->_left == cur){
                        parent->_left = cur->_left;
                        parent->_bf++;}else{
                        parent->_right = cur->_left;
                        parent->_bf--;}}if(parent->_bf !=-1&& parent->_bf !=1)AfterEraseUpdateBf(parent);delete cur;}else{
                Node* rightMinParent = cur;
                Node* rightMin = cur->_right;// 先去右子树while(rightMin->_left){
                    rightMinParent = rightMin;
                    rightMin = rightMin->_left;// 一种往左走}

                cur->_kv = rightMin->_kv;// 替代删除// 删除minNode  第一种情况：左节点为空if(rightMinParent->_left == rightMin){
                    rightMinParent->_left = rightMin->_right;
                    rightMinParent->_bf++;}else{
                    rightMinParent->_right = rightMin->_right;
                    rightMinParent->_bf--;}if(rightMinParent->_bf !=-1&& rightMinParent->_bf !=1)AfterEraseUpdateBf(rightMinParent);delete rightMin;}returntrue;}}returnfalse;}voidAfterEraseUpdateBf(Node* parent){if(parent ==nullptr)return;
    
    Node* cur = parent;goto first;while(parent){// 更新parent的平衡因子// cur在parent的左，parent->_bf++// cur在parent的右，parent->_bf--if(cur == parent->_left)
            parent->_bf++;else
            parent->_bf--;// bf 可能为 -2、-1、0、1、2// 如果平衡因子为0，说明更新之前，parent的bf为-1或1，现在删掉了左节点或右节点，整体高度变了，对上层有影响// 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在删掉了一个左节点或有节点，整体高度不变，对上层无影响// 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就另一边// 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整
    first:if(parent->_bf ==0){// 对上层有影响，迭代更新// 如果parent是根节点就结束if(parent->_parent ==nullptr)break;
            cur = parent;
            parent = parent->_parent;}elseif(parent->_bf ==-1|| parent->_bf ==1){// 对上层无影响，退出break;}else{// 平衡树出现了问题，需要调整// 1.右边高，左旋转调整if(parent->_bf ==2){// 如果是一条直线==>左旋转即可// 如果是一条折线==>右左旋转if(parent->_right->_bf ==1){RotateL(parent);
                    cur = parent->_parent;
                    parent = cur->_parent;continue;}elseif(parent->_right->_bf ==-1)// 调整后 p sL s  如果sL是1或-1可以退出 {
                    Node* s = parent->_right;
                    Node* sL = s->_left;RotateRL(parent);// 不平衡向上调整  注意：bug1（以为调整完就是1或-1了，其实这里不是，画图思考一下）//if (sL->_bf != 1 && sL->_bf != -1){
                        cur = sL;
                        parent = cur->_parent;continue;}}elseif(parent->_right->_bf ==0)// 旋转后平衡因子要修改，画图感受 parent: 1 parent->_parent:- 1{RotateL(parent);
                    parent->_bf =1;
                    parent->_parent->_bf =-1;}}// 2.左边高，右旋转调整elseif(parent->_bf ==-2){// 如果是一条直线==>右旋转即可// 如果是一条折线==>左右旋转if(parent->_left->_bf ==-1){RotateR(parent);
                    cur = parent->_parent;// bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图
                    parent = cur->_parent;continue;//parent不是-1或1就继续}elseif(parent->_left->_bf ==1)// 调整后 s sR p  如果sL是1或-1可以退出{
                    Node* s = parent->_left;
                    Node* sR = s->_right;RotateLR(parent);// 不平衡向上调整 为0时如果parent为根//if (sR->_bf != 1 && sR->_bf != -1){
                        cur = sR;
                        parent = cur->_parent;continue;}}elseif(parent->_left->_bf ==0)// 平衡因子要修改，画图感受 parent->_parent: 1 parent: -1 {RotateR(parent);
                    parent->_parent->_bf =1;
                    parent->_bf =-1;}}// 调整后是平衡树，bf为1或-1，不需要调整了break;}}}

💎七、AVL树查找

和KVL树一样

//因为kvl树我们需要修改value，所以返回节点的指针
Node*_FindR(Node* root,const K& key){if(root ==nullptr)returnnullptr;if(root->_kv.first < key){return_FindR(root->_right, key);}elseif(root->_kv.first > key){return_FindR(root->_left, key);}else{return root;//返回节点的指针}}

💎八、AVL树性能

  1. AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度logN
  2. 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置
标签： c++ 算法 开发语言
本文转载自: https://blog.csdn.net/YQ20210216/article/details/127107306
版权归原作者 企鹅不叫 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【初阶与进阶C++详解】第十六篇：AVL树-平衡搜索二叉树（定义+插入+旋转+验证）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

【Python】【持续项目】Python-安全项目搜集

泷羽sec学习day5-安全见闻6

随身 WiFi 通过 USB 连接路由器共享网络 扩展网络覆盖范围

如何将 Kubernetes 中的两个 Nginx Ingress 合并成一个：操作步骤与注意事项

单元测试使用JUnit 5

【大数据学习 | HBASE高级】hive操作hbase

MySQL Workbench 8.0 CE 中文汉化教程

文章导航