??今天的这一篇博客，我要跟大家介绍一颗树——AVL树，它也是一颗二叉搜索树，它就是在二叉搜索树中加了一个平衡因子的概念在里面，下面我就来和大家聊一聊这棵树是个怎么样的树。
??博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code

目录

• 概念
• AVL树的实现
• • AVL树的节点定义
  • AVL树的插入
  • • 方法概述
    • 平衡因子的调节
    • • 正常情况
      • 旋转处理（出现了不平衡子树）
    • 插入代码实现
  • AVL树的查找
  • AVL树的删除
  • • 方法概述
    • 平衡因子的调节
    • • 正常情况
      • 需要旋转处理的几种情况
    • 删除代码如下
  • AVL树的测试代码
• 总结

概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

• 它的左右子树都是AVL树
• 左右子树高度之差的绝对值（也叫平衡因子）不超过1
• 我规定：平衡因子（balance factor）= 右子树高度 - 左子树高度（后面这样实现）

文章图片

AVL树的实现 AVL树的节点定义 这里节点是一个三叉链，里面存放了元素的数据和该节点此时的平衡因子。不管今后我们进行什么操作，都要维持这里的平衡因子的绝对值不超过1。

template struct AVLTreeNode { // 三叉链 AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; pair _kv; int _bf; // balance factor平衡因子 右子树高度-左子树高度 AVLTreeNode(const pair& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_bf(0) {} };

AVL树的插入 方法概述
第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点（这一步很简单，上一篇博客介绍过）
第二步： 更新平衡因子，更新平衡因子的过程是一个难点，下面我给大家分析一下整个过程
平衡因子的调节
正常情况 实际上，我们应该能够发现，插入一个节点后，它之后影响它祖先的平衡因子（可能是所有祖先，也可能是一部分祖先），下面就是一个分析过程：
第一步： 判断父亲节点是否存在，不存在直接结束，如果存在，且插入节点是它的左孩子，那么父亲节点的平衡因子就减1，如果是父亲的右，父亲的平衡因子就加1。然后对父亲节点的平衡因子进行检索。
第二步： 继续对父亲节点的平衡因子进行检索，平衡因子会有一下三种情况
第一种情况： 此时父亲的平衡因子为0，则说明插入前父亲的平衡因子为1或-1，缺少左节点或右节点插入后，插入的节点已经补齐了左节点或右节点，整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

文章图片

第二种情况 此时父亲节点的平衡因子为-1或1，则说明插入前父亲的平衡因子为0，插入后增加了一个左节点或右节点，整体高度增加1，对上层有影响，继续迭代更新祖先的平衡因子。下面是一个演示图：

文章图片

第三种情况： 此时父亲节点的平衡因子为-2或2，则说明插入前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，插入后增加了一个左节点或右节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

文章图片

旋转处理（出现了不平衡子树） 旋转有四种情况：

1. 左单旋（新插入的节点在右子树的右侧）
   具体步骤： 让subR的左孩子成为parent的右孩子，然后让parent成为subR的左孩子，最后把两个节点的平衡因子修改为0.
   先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）：
   
   文章图片
   
   再画一个抽像图来演示：
   
   文章图片
   
   代码实现如下：

// 左单旋 bf为2右边高，把上面的压下来放到左边 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; // 1.先让把subR的左边（可能为空也可能不为空）作为parent的右边 parent->_right = subRL; // 2.如果subRL不为空，就让subRL的父指针指向parent if (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的父节点（左或右）指向subR if (ppNode == nullptr) { // 更新根节点 _root = subR; subR->_parent = nullptr; } else { // 判断parent是ppNode的左还是右 if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; subR->_parent = ppNode; } // 6.把parent和subR的平衡因子更新为0 subR->_bf = parent->_bf = 0; }

2. 右单旋 （新节点插入到较高左子树的左侧）
   具体步骤： 让subL的右孩子成为parent的左孩子，然后让parent成为subL的右孩子，最后把两个节点的平衡因子修改为0.
   先画一个具像图给大家演示如何进行这个操作（下面是一部分失衡的子树）：
   
   文章图片
   
   在给大家演示一下抽象图：
   
   文章图片
   
   代码实现如下：

// 右单旋 bf为-2左边高，把上面的压下来放到右边 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; // 1.先让把subL的右边（可能为空也可能不为空）作为parent的左边 parent->_left = subLR; // 2.如果subLR不为空，就让subLR的父指针指向parent if (subLR) subLR->_parent = parent; // 3.先记录parent的父节点的位置，然后把parent作为subL的右边 Node* ppNode = parent->_parent; subL->_right = parent; // 4.parent的父指针指向subL parent->_parent = subL; // 5.如果ppNode为空==>说明subR现在是根节点，就让subL的父指针指向nullptr //不是根节点就把subL的父指针指向parent的父节点，parent的父节点（左或右）指向subL if (ppNode == nullptr) { // 更新根节点 _root = subL; subL->_parent = nullptr; } 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; }

3. 右左双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）
   具体步骤 先对subR进行一个右单旋，然后对parent进行左单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：parent、subRL和subR。
   如果subRL的平衡因子为0，就将它们依次改为0，0, 0；
   如果subRL的平衡因子为1，就将它们依次改为-1，0, 0；
   如果subRL的平衡因子为-1，就将它们依次改为0，0, 1。
   先看具像图：
   
   文章图片
   
   再看一个抽象图（两种情况）：
   subRL的bf为1
   
   文章图片
   
   subRL的bf为-1
   文章图片
   
   代码实现如下：

// 右左旋转==>parent->_bf==2&&cur->_bf==-1 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; // 保留subRL的平衡因子的值，方便知道新插入的节点是在subRL的左子树还是右子树 // 旋转 先对subR进行右旋转，再对parent进行左旋转 RotateR(subR); RotateL(parent); // 从左到右 parent subRL subR if (bf == -1)// subRL的左子树bf: 0 0 1 { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 1; } else if (bf == 1)// subRL的右子树 bf: -1 0 0 { parent->_bf = -1; subRL->_bf = 0; subR->_bf = 0; } else if (bf == 0) { parent->_bf = 0; subRL->_bf = 0; subR->_bf = 0; } }

4. 左右双旋（新节点插入在较高右子树左侧，这里和第一种情况的区别就是前者是直线，后者是折线）
   具体步骤先对subL进行一个左单旋，然后对parent进行右单旋，修改平衡因子，有三种改法。三个节点从左至右的三个节点一次是：subL、subLR和parent。（和上面的类似，这样有助于我们记住平衡因子的调整，同时我们也可以画简图理解记忆）
   如果subLR的平衡因子为0，就将它们依次改为0，0, 0；
   如果subLR的平衡因子为1，就将它们依次改为-1，0, 0；
   如果subLR的平衡因子为-1，就将它们依次改为0，0, 1。
   先看具像图：
   
   文章图片
   
   再看一个抽象图（也有两种情况）：
   subLR的bf为-1
   
   文章图片
   
   subLR的bf为1
   
   文章图片
   
   代码实现如下：

// 左右旋转==>parent->_bf==-2&&cur->_bf==1 void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; // 保留subLR的平衡因子的值，方便知道新插入的节点是在subLR的左子树还是右子树 // 旋转 先对subL进行左旋转，再对parent进行右旋转 RotateL(subL); RotateR(parent); // 从左到右 subL subLR parent if (bf == -1)// subLR的左子树bf: 0 0 1 { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1)// subLR的右子树 bf: -1 0 0 { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } }

插入代码实现
插入的步骤也就是如上面说的一样，下面的代码我们通过迭代实现。
代码实现如下：

bool Insert(const pair& kv) { // 先按照二叉搜索数一样插入元素 // 无节点是插入 if (_root == nullptr) { _root = new Node(kv); return true; } // 有节点时插入 Node* parent = nullptr; Node* cur = _root; while (cur) { parent = cur; // 小于往左走 if (kv.first < cur->_kv.first) { cur = cur->_left; } // 大于往右走 else if (kv.first > cur->_kv.first) { cur = cur->_right; } else { // 找到了，就返回false return false; } } cur = new Node(kv); // 判断cur应该插在parent的左还是右 // 小于在左，大于在右 if (cur->_kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } // 更新parent的平衡因子 // 节点的插入只会影响cur的祖先的平衡因子（不是所有的，是一部分，分情况） 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，现在补齐了左节点或右节点，bf==0，对上层无影响 // 如果平衡因子为-1或1，说明更新之前，parent的bf为0，现在增加了一个左节点或有节点，bf==-1 || bf==1,对上层有影响 // 如果平衡因子为-2或2，说明更新之前，parent的bf为-1或1，现在往左（右）节点补了左（右）节点，也就是一边 // 拉高了，树不平衡了，需要用左旋转或右旋转来进行调整 if (parent->_bf == 0) { // 对上层无影响，退出 break; } else if (parent->_bf == -1 || parent->_bf == 1) { // 对上层有影响，迭代更新 cur = parent; parent = parent->_parent; } else { // 平衡树出现了问题，需要调整 // 1.右边高，左旋转调整 if (parent->_bf == 2) { // 如果是一条直线==>左旋转即可 // 如果是一条折线==>右左旋转 if (cur->_bf == 1) RotateL(parent); else if (cur->_bf == -1) RotateRL(parent); } // 2.左边高，右旋转调整 else if (parent->_bf == -2) { // 如果是一条直线==>右旋转即可 // 如果是一条折线==>左右旋转 if (cur->_bf == -1) RotateR(parent); else if (cur->_bf == 1) RotateLR(parent); }// 调整后是平衡树，bf为0，不需要调整了 break; } } return bool; }

AVL树的查找 查找的代码和二叉搜索树是一样的，这里就不过多介绍。
代码实现如下：

bool Find(const K& key) { if (_root == nullptr) return false; Node* cur = _root; while (cur) { // 小于往左走 if (key < cur->_kv.first) { cur = cur->_left; } // 大于往右走 else if (key > cur->_kv.first) { cur = cur->_right; } else { // 找到了 return true; } } return false; }

AVL树的删除 方法概述
【C++篇|【C++进阶】第十八篇——AVL树（概念+平衡因子的调节+旋转+代码实现）】第一步： 我们先按照二叉搜索树树删除节点的方式，删除节点（这一步很简单，上一篇博客介绍过）
第二步： 然后根据对应删除情况更新平衡因子，这里更新平衡因子的方法与插入的更新方法是相反的，下面我给大家分析一下整个过程
平衡因子的调节
正常情况 删除节点后，如果删除的节点为根节点，就结束。否则根据删除节点为父节点的左右调整父节点的平衡因子。如果删除节点是父节点的左孩子，那么父亲节点的平衡因子加1，否则减1。然后对父亲节点进行检索。
有以下几种情况：
第一种情况： 此时父亲的平衡因子为0，则说明删除前父亲的平衡因子为1或-1，多出一个左节点或右节点，删除节点后，左右高度相等，整体高度减1，对上层有影响，需要继续调节。下面是一个演示图：（如果此时3为根节点，那么也可以结束）

文章图片

第二种情况： 此时父亲的平衡因子为-1或1，则说明删除前父亲的平衡因子为0，左右高度相等，删除节点后，少了一个左节点或右节点，但是整体高度不变，对上层无影响，不需要继续调节。下面是一个演示图：

文章图片

第三种情况： 此时父亲节点的平衡因子为-2或2，则说明删除前父亲的平衡因子为-1或1，多了一个左节点或一个右节点，删除了一个右节点或左节点，此时多了两个左节点和右节点，这棵子树一边已经被拉高了，此时这棵子树不平衡了，需要旋转处理。下面是一个演示图：

文章图片

需要旋转处理的几种情况 这里我只分析右边高的情况，左边高和它对称的，操作是相同的。
情况一：
操作方法： 对parent进行左旋转，因为subR的平衡因子为0，需要继续检索，然后继续迭代，把cur迭代sub的位置，parent到cur的父亲的位置
具像图：

文章图片

抽象图：

文章图片

情况二：
操作方法： 对parent进行左旋，然后修改平衡因子，把subR的平衡因子改为-1，parent的平衡因子改为1，因为subR的平衡因子为-1，所以无需迭代，直接结束
具像图：

文章图片

抽象图：

文章图片

情况三：
操作方法： 对subR进行右旋，然后对parent进行左旋，此时subR的平衡因子为0，需迭代
具像图：

文章图片

抽象图：

文章图片

删除代码如下
删除代码如下：

bool Erase(const K& key) { if (_root == nullptr) return false; // 有节点时插入 Node* parent = nullptr; Node* cur = _root; while (cur) { // 小于往左走 if (key < cur->_kv.first) { parent = cur; cur = cur->_left; } // 大于往右走 else if (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; } else if (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; } return true; } } return false; } void AfterEraseUpdateBf(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; } else if (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; } else if (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; } } else if (parent->_right->_bf == 0)// 旋转后平衡因子要修改，画图感受 parent: 1 parent->_parent:- 1 { RotateL(parent); parent->_bf = 1; parent->_parent->_bf = -1; }} // 2.左边高，右旋转调整 else if (parent->_bf == -2) { // 如果是一条直线==>右旋转即可 // 如果是一条折线==>左右旋转 if (parent->_left->_bf == -1) { RotateR(parent); cur = parent->_parent; // bug2 cur要变成这个位置是因为选择后父亲的位置变了，画图 parent = cur->_parent; continue; //parent不是-1或1就继续 } else if (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; } } else if (parent->_left->_bf == 0)// 平衡因子要修改，画图感受 parent->_parent: 1 parent: -1 { RotateR(parent); parent->_parent->_bf = 1; parent->_bf = -1; } }// 调整后是平衡树，bf为1或-1，不需要调整了 break; } } }

AVL树的测试代码 下面是验证是否为AVL树的代码：

int _Height(Node* root) { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return 1 + max(leftHeight, rightHeight); } bool _IsBalanceTree(Node* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return rightHeight - leftHeight == root->_bf && abs(rightHeight - leftHeight) < 2 && _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }

实例演示：

void TestAVLTree1() { AVLTree at; srand((size_t)time(nullptr)); // int a[] = { 4,3,5,3,1,2,7 }; // int a[] = { 1,2,3,4,5,6,7,8,9 }; // int a[] = { 2,4,6,3,5,1,9,10,8,7 }; // int a[] = { 4,2,3,5 }; // int a[] = { 16,3,7,11,9,26,18,14,15 }; // int a[] = { 4,2,6,1,3,5,15,7,16,14 }; // int* a = new int[10000]; /*int i = 1; for (auto& e : a) { e = i++; }*/ vector a; for (size_t i = 0; i < 13; ++i) { // a.push_back(rand()); a.push_back(13); } for (auto e : a) { int begin = clock(); pair*, bool> ret = at.Insert(make_pair(e, e)); int end = clock(); // cout << ret.first->_kv.second << endl; // cout << ret.first->_kv.second << ":" << ret.second << endl; cout << "插入 " << e << " 后变化 --> Height: " << at.Height() << " 是否为AVLTree：" << at.IsBalanceTree(); cout << " 用时: " << end - begin << "ms" << endl; } cout << "------------------------------------------------------" << endl; // at.InOrder(); for (auto e : a) { if (e == 11478) { int a = 0; } int begin = clock(); at.Erase(e); int end = clock(); cout << "删除 " << e << " 后变化 --> Height: " << at.Height() << " 是否为AVLTree：" << at.IsBalanceTree(); cout << " 用时: " << end - begin << "ms" << endl; } at.InOrder(); }

代码运行结果如下：

文章图片

总结 AVL树的全部内容就介绍到这，图画了一下午，创造不易，感谢支持，下一篇博客更新红黑树的相关内容，喜欢的话，欢迎点赞支持~

文章图片

推荐阅读

• 

  肤色暗黄怎么去角质
• 

  移动plus会员是什么意思 plus会员是什么意思
• 

  王者荣耀亚瑟最强出装是什么？只要攻击性型的不要防御的？
• 

  对纸飞机头哈气 纸飞机哈气什么意思
• 

  游戏大全小游戏益智，益智小游戏排名
• 

  jquery页面延时加载，jquery设置延时动画
• 

  南阳卧龙岗2021春节门票价格 南阳卧龙岗2023年春节游玩攻略
• 

  梦见准备买房子 梦见准备买房子是什么预兆呢
• 

  按日期分组查询oracle 按日期分组mysql
• 

  单反夜景怎么拍
• 

  猕猴桃寒性还是热性的，猕猴桃温性还是寒性还是平性
• 

  手机怎么自动刷新图片格式，手机网页怎么自动刷新
• 

  英文微信名男生简单气质 英文微信名男
• 

  有关保险诈骗罪的相关解释包括哪些规定
• 

  ios开发自用软件免费吗，苹果开发的软件不是说免费吗
• 

  党参和当归的区别介绍
• 

  1个穿云箭主播能挣多少 快手一个穿云箭多少钱
• 

  mysql中的约束有哪些 mysql如何用语句约束
• 

  排骨大酱汤的做法 排骨大酱煲怎么做
• 

  qq找回

• C++篇|【C++进阶】第十九篇——红黑树（概念+代码实现）
• C-C++易混知识点|C++容易忘记的知识点——map和set（六）
• 中间件安全|Struts2 远程代码执行漏洞复现（附Struts2漏洞检测工具）
• JavaWeb|线程安全详解
• OpenCV|opencv （三十七）图像形态学——腐蚀
• springboot|springboot整合Mybatis-Plus
• 陪伴程序员的一条龙、一骑士 36 岁了
• java|单点登录方案
• 计算机视觉|OpenCV的简单使用教程与基本函数（C++版本）