【C++】“旋转！跳跃！我闭着眼！”—— 从零开始构建AVL树

送给大家一句话：

一个人认清了他在这世界上要做的事情，并且在认真地做着这些事情，他就会获得一种内在的平静和充实。 – 周国平

️️️️️️️

从零开始构建AVL树

• ️1 什么是AVL树
• ️2 实现AVL树
• • ️ 2.1 框架构建
  • ️ 2.2 插入函数
  • ️ 2.3 AVL树的旋转（重点）
  • • ️右单旋：
    • ️左单旋：
    • ️左右双旋：
    • ️右左双旋：
    • ️完成插入操作
    • ️ 2.4 寻找函数
    • ️ 2.4 删除函数（了解）
    • ️3 AVL树的测试
    • ️3 AVL树的性能
    • Thanks♪(･ω･)ﾉ谢谢阅读！！！
    • 下一篇文章见！！！

      ️1 什么是AVL树

      前两篇文章：

      【C++】从零开始构建二叉搜索树

      【C++】初探 map 与 set

      我们学习了二叉搜索树：二叉搜索树虽可以缩短查找的效率，如果数据有序或接近有序二叉搜索树将退化为单支树，这样二叉搜索树效率退化为O(n)，不够高效！所以就有了改进版的二叉搜索树->AVL树（平衡二叉搜索树）

      在1962年，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

      map与set 的底层实现也是AVL树或红黑树！

      一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

      • 它的左右子树都是AVL树
      • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1 )

        如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度 O( l o g 2 n log_2 n log2​n)

        通过每次插入删除的调整保证二叉树始终保持一个近乎完美的完全二叉树，规避了极端情况下二叉搜索树退化为单枝树的情况

        接下来我们就来研究如何实现AVL树!!!

        ️2 实现AVL树

        ️ 2.1 框架构建

        首先AVL树是在二叉搜索树的基础上进行改进，AVL树节点中加入了：

        • 平衡因子_bf：左右子树的高度差 right子树高度 - left子树高度 ，即左子树插入节点时_bf--，右子树插入节点时_bf++!
        • 父指针_parent：指向父节点的指针，为了可以回溯更新父节点的平衡因子。

          templatestruct AVLtreeNode{typedef AVLtreeNode Node;//三叉树结构Node* _parent;Node* _left;Node* _right;//键值对pair _kv;//平衡因子int _bf;AVLtreeNode(pair kv):_parent(nullptr),_right(nullptr),_left(nullptr),_kv(kv)     ,_bf(0){}};

          注意构造函数的初始化列表，不要出现野指针！！！

          ️ 2.2 插入函数

          先不管平衡因子这个变量，AVL树的插入比二叉搜索树略微复杂一点，需要多处理一步父指针：

          bool Insert(pair kv){Node* node = new Node(kv);//如果为空直接赋值if (_root == nullptr){_root = node;return true;}//反之寻找插入位置（按照 key 比较大小）else{Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if(cur->_kv.first _right;}else{//二叉搜索树默认不重复数据return false;}}//按照大小插入节点if (kv.first > parent->_kv.first){parent->_right = node;}else{parent->_left = node;}//记得要处理父指针！！！node->_parent = parent;cur = node;//更新平衡因子//...}}

          结下来就是处理平衡因子：左子树插入节点时_bf--，右子树插入节点时_bf++

          这里思考一下，平衡因子的处理要到什么情况才停下来？？？

          当我们插入一个新节点时，有两种情况：

          1. 插入parent的左子树，parent的平衡因子减一！
          2. 插入parent的右子树，parent的平衡因子加一！

          父节点的平衡因子经过更新后可以得到三种情况：

          1. parent的平衡因子是 0 ：得到0 说明之前之前parent的左右两边不平衡，插入后平衡了，高度没有改变，不需要处理爷爷节点！！！
          2. parent的平衡因子是 ∓1 ：得到正负一说明之前parent的平衡因子是0，插入后以parent为根节点的子树的高度增加了！那么就要继续处理爷爷节点！
          3. parent的平衡因子是 ∓2 ：得到这种情况说明在本来就高的一边继续插入了一个新节点！以parent为根节点的子树已经不满足AVL树的结构，需要特殊处理！

          根据上述是分类我们可以写出处理平衡因子的的代码！

          首先可能要向上一直处理，所以干脆写一个while循环，在内部在进行分类：如果需要继续处理爷爷节点，就继续循环，不需要处理就跳出循环！

          //...//处理平衡因子//更新平衡因子while (parent != nullptr){if (cur == parent->_left){//左子树增加 父节点平衡因子--parent->_bf--;}else{//右子树增加 父节点平衡因子++parent->_bf++;}//为零直接退出if (parent->_bf == 0){break;}//为 1 或 -1 继续向上进行else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}//旋转来哩！！！else if (parent->_bf == 2 || parent->_bf == -2){//分类旋转//旋转之后二叉树平衡！break;}//特殊情况处理 因为未来不知道会出什么bug ,在这里截断一下else{cout Node* subL  = parent-_left;   //左子节点Node* subLR = subL-_right;  //左节点的右节点Node* ppNode = parent->_parent;//爷爷节点subL->_right = parent;parent->_parent = subL;parent->_left = subLR;if (subLR != nullptr)subLR->_parent = parent;//处理爷爷节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//保证爷爷节点的指向正确if (parent == ppNode->_left){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//处理平衡因子 因为已经平衡了 所以都为 0 parent->_bf = 0;subL->_bf = 0;}

          旋转完parent满足AVL树的性质！

          ️左单旋：

          左单旋与右单旋类似！！！

          1. 初始化情况：树的情况如图，parnet的平衡因子是1，subL的平衡因子是0 ！
          2. 当我们在subL的左子树插入一个节点，并使subL的平衡因子变为1 , parent的平衡因子变为2
          3. 此时需要对parnet进行左单旋:

          具体实现基本就是右单旋的框架，更改一下变量，不在单独写！

          ️左右双旋：

          我们来看一种情况：

          这种情况既不能通过右单旋解决，也不能通过左单旋解决！！！

          这时候就需要继续左右双旋：先进行一次做单旋，在进行一次右单旋。

          具体怎么操作，我们来看：

          1. 初始化情况：树的情况如图，parnet的平衡因子是-1，subL的平衡因子是0 ！
          2. 当我们在subL的右子树插入一个节点，并使subL的平衡因子变为1 , parent的平衡因子变为-2
          3. 此时需要先对subL进行一次左单旋，使其成为可以进行右单旋的状态，再对parent进行一次右单旋

          注意，根据图分析，插入的位置会影响subL和 parent的平衡因子，需要根据subLR分类讨论:

          1. 如果插入到subLR的右子树， 那么该右子树最终会变成parent的左子树，所以相当于parent的左子树插入节点，所以parent的平衡因子应为-1
          2. 如果插入到subLR的左子树， 那么该左子树最终会变成subL的左子树，所以相当于subL的右子树插入节点，所以parent的平衡因子应为1
          3. 如果subLR自己是新插入的节点，那么平衡因子都为0！

          //左右双旋void RotateLR(Node* parent){//先记录相关信息Node* subL = parent->_left;Node* subLR = subL->_right;//需要通过subLR来确定平衡因子int bf = subLR->_bf;//进行旋转//左单旋 subLRotateL(subL);//右单旋 parentRotateR(parent);//平衡因子需要调整！！！//在subLR的左子树插入 if (bf == -1){//右单旋 parent 会将subLR的右子树给parent的左边 ，parent左边比右边低parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}//在subLR的右子树插入 else if (bf == 1){parent->_bf = 0;//左单旋 subL 会将subLR的左子树给subL的右边 ，subL左边比右边高subL->_bf = -1;subLR->_bf = 0;}//如果subLR自身是插入的节点else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{//出错了assert(false);}}

          这样就好了

          ️右左双旋：

          来看图：

          具体实现与左右双旋类似，先进行一次右单旋，再进行一次左单旋!

          细节不在多说，根据图自行书写即可！

          ️完成插入操作

          我们完成了旋转，就可以补全插入操作的空缺,按情况分好类即可：

          //插入节点bool Insert(pair kv){Node* node = new Node(kv);//如果为空直接赋值if (_root == nullptr){_root = node;return true;}//反之寻找插入位置（按照 key 比较大小）else{Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){parent = cur;if (cur->_kv.first > kv.first){cur = cur->_left;}else if(cur->_kv.first _right;}else{//二叉搜索树默认不重复数据return false;}}//cur = node;if (kv.first > parent->_kv.first){parent->_right = node;}else{parent->_left = node;}node->_parent = parent;cur = node;//更新平衡因子while (parent != nullptr){if (cur == parent->_left){//左子树增加 父节点平衡因子--parent->_bf--;}else{//右子树增加 父节点平衡因子++parent->_bf++;}//为零直接退出if (parent->_bf == 0){break;}//为 1 或 -1 继续向上进行else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = cur->_parent;}//旋转来哩else if (parent->_bf == 2 || parent->_bf == -2){//分类旋转if (parent->_bf == -2 && cur->_bf == -1){//右单旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左单旋RotateL(parent);}//需要双旋的情况else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}//旋转之后二叉树平衡！break;}//特殊情况处理else{cout Node* cur = _root;while (cur != nullptr){if (key == cur-_kv.first){return true;}else if (key _left;}else{cur = cur->_right;}}return false;}

          ️ 2.4 删除函数（了解）

          删除节点的方法是在二叉搜索树的基础上加入了平衡因子与父节点指针，我们依旧可以按照被删除节点的状况来分类讨论：

          • 1️⃣要删除的结点无孩子结点
          • 2️⃣要删除的结点只有左孩子结点
          • 3️⃣要删除的结点只有右孩子结点
          • 4️⃣要删除的结点有左、右孩子结点

            ⚠️⚠️⚠️下面的过程很重要⚠️⚠️⚠️：

            1. 同样要先找到需要删除的节点
            2. 找到需要删除的节点，按照AB类进行区分，来进行虚拟删除（处理完平衡因子在完全删除）
               • A类（1️⃣2️⃣3️⃣）：直接删除就可以，parent 跳过 cur 指向cur的子树，一定保证指针的指向正确！
               • B类（4️⃣）：使用替换法，寻找右子树的最小值，交换键值对，然后对其进行删除
               • 虚拟删除：就是记录下需要删除节点的指针与其父节点指针。
               • 更新平衡因子，与插入有一些不同，删除的情况更加复杂，其对应的平衡因子关系会有 3 种
                 • ⚠️parent 修改后变为 0 ：说明高度变化了，需要继续向上进行修改
                 • ⚠️parent 修改后变为 ∓1 ：说明相比原来，高度并没有变化（由 0 删除一边而来），可以停止更新平衡因子
                 • ⚠️parent 修改后变为 ∓2 ： 说明两边此时高度差不满足AVL树，需要进行旋转！此时旋转又要分 6 种情况来讨论：2 * 3 = 6 需要旋转时父树有两个子树，都需要讨论 。子树节点平衡因子有 3 种 -1 1 0 。我们不需要思考这些情况是删除哪里的节点得到的，只需要对每种情况进行处理就可以！！！

            平衡因子情况	如何选择	为什么
            parent为 -2 parent->_left为 -1	此时进行右单旋	现在是左边高，因此需要向右旋转
            parent为 -2 parent->_left为 1	此时进行左右双旋	此时左边高，并且子树的平衡，所以只需要向右旋转
            parent为 -2 parent->_left为 0	此时进行右单旋	此时是删除了parent右边的节点，导致其不平衡（左高右低），所以向右旋转
            parent为 2 parent->_right为 1	此时进行左单旋	现在是右边高，因此需要向左旋转
            parent为 2 parent->_right为 -1	此时进行右左双旋	因为子树左边高，父树右边高，先对子树进行右旋使其偏差一致，可以进行左旋来修正
            parent为 2 parent->_right为 0	此时进行左单旋	此时右边高，并且子树的平衡，所以只需要向左旋转

            1. 真正删除节点!!!

            来看代码：

            //删除节点bool Erase(K key){Node* cur = _root;Node* parent = nullptr;//记录需要删除的节点Node* DelParentPos = nullptr;Node* DelPos = nullptr;//寻找替换值//寻找需要被删除的节点while (cur != nullptr){if (key > cur->_kv.first){parent = cur;cur = cur->_right;}else if (key _kv.first){parent = cur;cur = cur->_left;}else{//现在找到了需要被删除的节点// //删除需要涉及平衡因子的改变//父指针的修正// 根据需要删除节点的状态分出以下4种状态：//a.要删除的结点无孩子结点//b.要删除的结点只有左孩子结点//c.要删除的结点只有右孩子结点//d.要删除的结点有左、右孩子结点//平衡因子的修正比较复杂 所以不能直接删除的情况要进行虚拟删除if (cur->_left == nullptr || cur->_right == nullptr){if (cur->_left == nullptr){//如果删除的的是根节点，单独处理if (cur == _root){_root = cur->_right;if(cur->_right)cur->_right->_parent = nullptr;delete cur;}//只要有祖先节点就要进行平衡因子的处理！！！ 先虚拟删除else{DelParentPos = parent; //标记实际删除结点的父结点DelPos = cur; //标记实际删除的结点}}else{//如果删除的的是根节点，单独处理if (cur == _root){_root = cur->_left;cur->_left->_parent = nullptr;delete cur;}else{DelParentPos = parent; //标记实际删除结点的父结点DelPos = cur; //标记实际删除的结点}}break;}//d.要删除的结点有左、右孩子结点//替换法 + 虚拟删除else{Node* rightMin = nullptr;Node* rightMinParent = cur;//寻找右子树最小值rightMin = cur->_right;rightMinParent = cur;while (rightMin->_left != nullptr){rightMinParent = rightMin;rightMin = rightMin->_left;}//找到可以替换的节点//交换键值对swap(cur->_kv, rightMin->_kv);//把要删除的节点记录下来，模拟删除DelParentPos = rightMinParent;DelPos = rightMin;break;}}}//没有找到的情况if (DelParentPos == nullptr) return false;parent = DelParentPos;cur = DelPos;//然后更新平衡因子while (cur != _root){if (cur == parent->_left){parent->_bf++;}else{parent->_bf--;}//根据不同结果来处理// 为0说明该子树的高度改变 高度变低了 继续向上处理if (parent->_bf == 0){cur = parent;parent = cur->_parent;}//为正负 1 说明该子树的高度没有改变 else if (parent->_bf == 1 || parent->_bf == -1){break;}//出现 正负 2 说明需要进行旋转修正！else if (parent->_bf == 2 || parent->_bf == -2){//分类讨论if (parent->_left->_bf == -1 && parent->_bf == -2){//注意要及时更新parent根节点，不然无法顺利向上推进//cur 节点经过旋转 指向依然正确，是parnet的子树Node* tmp = parent->_left;RotateR(parent);parent = tmp;}else if (parent->_left->_bf == 1 && parent->_bf == -2){Node* tmp = parent->_left->_right;RotateLR(parent);parent = tmp;}else if (parent->_left->_bf == 0 && parent->_bf == -2){Node* tmp = parent->_left;RotateR(parent);parent = tmp;parent->_bf = 1;parent->_right->_bf = -1;//此时 parent 的平衡因子为 1 说明该树删除后高度没有改变，所以不在需要向上更新break;}else if (parent->_right->_bf == -1 && parent->_bf == 2){Node* tmp = parent->_right->_left;RotateRL(parent);parent = tmp;}else if (parent->_right->_bf == 1 && parent->_bf == 2){Node* tmp = parent->_right;RotateL(parent);parent = tmp;}else if (parent->_right->_bf == 0 && parent->_bf == 2){Node* tmp = parent->_right;RotateL(parent);parent = tmp;parent->_bf = -1;parent->_left->_bf = 1;//此时 parent 的平衡因子为 -1 说明该树删除后高度没有改变，所以不在需要向上更新break;}//旋转的本质是将树的高度变低，所以parent树的高度一定会发生改变！//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子！cur = parent;parent = cur->_parent;}else{cout if (DelPos == DelParentPos-_left){DelParentPos->_left = DelPos->_right;if (DelPos->_right)DelPos->_right->_parent = DelParentPos;}if (DelPos == DelParentPos->_right){DelParentPos->_right = DelPos->_right;if (DelPos->_right)DelPos->_right->_parent = DelParentPos;}}else//右为空{if (DelPos == DelParentPos->_left){DelParentPos->_left = DelPos->_left;if (DelPos->_left)DelPos->_left->_parent = DelParentPos;}if (DelPos == DelParentPos->_right){DelParentPos->_right = DelPos->_left;if (DelPos->_left)DelPos->_left->_parent = DelParentPos;}}delete DelPos;//删除！！！return true;}

            这一部分值得细细琢磨！

            通过借鉴他人的 =代码，我调试了半天才完全排除错误…

            ️3 AVL树的测试

            我们写了这么多的代码，现在来测试一下，来看看是否满足AVL树！！！

            验证AVL树就要来检查每个节点的平衡因子是否满足条件！平衡因子的本质是左右子树的高度差，所以我们可以通过检查每颗子树的高度差来看看是否满足条件：

            检查过程需要遍历当前节点的左右子树来获得对应高度，所以我们需要再写一个求高度的函数，都是通过递归来实现，我这里使用的事前序，效率比后序稍差，但写起来简单。

            1. 判断一棵树是否平衡就要先判断当前节点是否满足AVL树的高度差，之后在判断左右子树是否满足
            2. 判断当前节点是否满足就要计算左右子树的高度差，就要遍历两个子树来获取。

            bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}bool _IsBalance(Node* root) {//按照高度进行检查if (root == nullptr) return true;if (abs(_Height(root->_left) - _Height(root->_right) ) >= 2) return false;return _IsBalance(root->_left) && _IsBalance(root->_right);}int _Height(Node* root){if (root == nullptr) return 0;return max(_Height(root->_left) + 1, _Height(root->_right) + 1);}

            现在：

            我们写个测试代码测试一下：

            void AVLTreeTest3(){const int N = 10000000;vector v;v.reserve(N);srand(time(0));for (size_t i = 0; i