前言
本篇博客讲解c++中数据结构AVL树，看这篇博客之前请先去看：C++ | 二叉搜索树-CSDN博客
? 个人主页：普通young man-CSDN博客
⏩ 文章专栏：C++_普通young man的博客-CSDN博客
⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com
若有问题 评论区见?
?欢迎大家点赞?收藏⭐文章
————————————————
目录
AVL树的概念
AVL树的实现
AVL树的结构
AVL树的插入
平衡因子的更新原则
更新停止条件
插入结点及更新平衡因子的代码实现
代码结构
代码步骤
旋转
旋转的原则
旋转类型
AVL树的查找
AVL树的平衡检测
总结
AVL树的概念
| 概念 | 描述 |
|---|---|
| 定义 | AVL树是最先发明的自平衡二叉查找树，是一棵空树或满足特定条件的二叉搜索树。 |
| 平衡条件 | 左右子树均为AVL树，且左右子树高度差的绝对值不超过1。 |
| 命名来源 | 以发明者G. M. Adelson-Velsky 和 E. M. Landis 的名字命名，他们是前苏联的科学家。 |
| 发表时间 | 1962年论文《An algorithm for the organization of information》。 |
| 平衡因子 | 结点的一个属性，等于其右子树的高度减去左子树的高度，通常为 -1、0 或 1。 |
| 平衡因子作用 | 用于方便观察和控制树的平衡性，如同风向标一样指示结点的平衡状态。 |
| 高度平衡原因 | 虽然理论上高度差为0是最理想的平衡状态，但在某些节点数的情况下（如2个或4个节点），无法达到高度差为0。 |
| 效率 | 由于高度受限，AVL树的操作（增删查改）效率可以保持在对数级别，优于普通的二叉搜索树。 |
AVL树的实现
AVL树的结构
//定义节点结构template<class k,class v>struct AVLTreeNode{//pair组合k，v数据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){}};//树类template<class K, class V>class AVLTree{ typedef AVLTreeNode<K, V> Node;public: //...private: Node* _root = nullptr;};
AVL树的插入
按照二叉搜索树的规则插入：
如果插入的值小于当前节点的值，则递归地向左子树进行插入；如果插入的值大于当前节点的值，则递归地向右子树进行插入；如果插入的值等于当前节点的值（通常不允许重复值），则不进行插入。更新高度和平衡因子：
在完成插入操作之后，从插入节点开始向上回溯到根节点，更新每个祖先节点的高度和平衡因子。高度是节点的最大子树高度加一。平衡因子是左子树高度减去右子树高度。检测并修正不平衡：
如果在回溯过程中发现任何一个节点的平衡因子的绝对值大于1（即不平衡），则需要对该节点所在的子树进行旋转来恢复平衡。旋转包括单旋转（LL或RR）和双旋转（LR或RL）。旋转类型
左旋(L)：当父节点的平衡因子为正数（表示左子树较高），并且当前节点的平衡因子也为正数时，表示当前节点的左子树较高，需要进行左旋来平衡树。
示例表格
| 父节点(parent)平衡因子 | 当前节点(cur)平衡因子 | 旋转类型 |
|---|---|---|
| 2 | 1 | 左旋(L) |
| 2 | -1 | 先右后左双旋(RL) |
| -2 | -1 | 右旋(R) |
| -2 | 1 | 先左后右双旋(LR) |
平衡因子的更新原则
计算公式： 平衡因子 = 右子树高度 - 左子树高度更新时机： 只有当子树的高度发生变化时，才会更新当前节点的平衡因子。插入节点的影响： 如果新节点插入到父节点的右子树中，父节点的平衡因子 +1。如果新节点插入到父节点的左子树中，父节点的平衡因子 -1。更新停止条件
平衡因子变为0： 当父节点的平衡因子由非0变为0时（例如从-1变为0或从1变为0），这意味着之前父节点的一侧较高，而新插入的节点恰好在较低的一侧，因此插入后整个子树的高度未变，不影响其父节点的平衡因子，此时可以停止更新。 平衡因子变为±1： 当父节点的平衡因子由0变为±1时（例如从0变为1或从0变为-1），这意味着新插入的节点使两侧的高度不再相等，但由于高度仅增加了1，因此仍符合AVL树的平衡要求，但需要继续向上更新，直到找到需要旋转的节点或满足其他停止条件。 平衡因子变为±2： 当父节点的平衡因子由±1变为±2时（例如从1变为2或从-1变为-2），这表示新插入的节点使较高一侧的高度进一步增加，破坏了平衡。此时需要进行旋转操作来重新平衡该子树，并降低子树的整体高度。旋转完成后，由于子树高度已恢复至插入前的状态，因此不需要继续向上更新，插入操作结束。| 插入前平衡因子 | 插入后平衡因子 | 插入位置 | 更新原则 | 停止条件 |
|---|---|---|---|---|
| 0 | ±1 | 右子树 | +1 | 继续更新 |
| 0 | ±1 | 左子树 | -1 | 继续更新 |
| ±1 | 0 | 左子树 | -1 | 停止更新 |
| ±1 | 0 | 右子树 | +1 | 停止更新 |
| ±1 | ±2 | 右子树 | +1 | 进行旋转 |
| ±1 | ±2 | 左子树 | -1 | 进行旋转 |
| 0 | 0 | 任意位置 | 无变化 | 停止更新 |
插入13这个节点，平衡因子向上更新，更新到10这个节点的时候我们发现10平衡因子变成了2，代表了它的右子树高于左子树，这边需要做一个双旋
没更新到底部，这个树只需要更新平衡因子，不需要做旋转处理，因为平衡，从这里就可以看出树的平衡是看平衡因子
更新到最底部：算最坏的情况
插入结点及更新平衡因子的代码实现
bool insert(const pair<k, v>& kv) { // 如果树为空，则创建根节点 if (_root == nullptr) { _root = new Node(kv); return true; } // 定义父节点和当前节点指针 Node* parent = nullptr; Node* cur = _root; // 寻找插入位置 while (cur != nullptr) { if (cur->_kv.first > kv.first) { parent = cur; // 当前节点大于新节点，向下移动到左子树 cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; // 当前节点小于新节点，向下移动到右子树 cur = cur->_right; } else { // 如果键已经存在，则返回false return false; } } // 创建新的节点并插入 cur = new Node(kv); // 将新节点连接到父节点上 if (parent->_kv.first > kv.first) { parent->_left = cur; // 新节点成为父节点的左子节点 } else if (parent->_kv.first < kv.first) { parent->_right = cur; // 新节点成为父节点的右子节点 } // 设置新节点的父节点指针 cur->_parent = parent; // 更新平衡因子并检查是否需要旋转来维持平衡 while (parent != nullptr) { // 根据插入方向调整平衡因子 if (parent->_left == cur) { parent->_bf--; // 左子树高度增加 } else { parent->_bf++; // 右子树高度增加 } // 检查平衡状态 if (parent->_bf == 0) { // 平衡 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 轻微不平衡 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 严重不平衡，需要进行旋转 if (parent->_bf == 2 && cur->_bf == 1) { Rotati_l(parent); // 左旋 } else if (parent->_bf == -2 && cur->_bf == -1) { Rotati_r(parent); // 右旋 } else if (parent->_bf == -2 && cur->_bf == 1) { Rotati_LR(parent); // 先左后右双旋 } else if (parent->_bf == 2 && cur->_bf == -1) { Rotati_RL(parent); // 先右后左双旋 } else { assert(false); // 不应该达到此情况 } break; } else { assert(false); // 不应该达到此情况，因为平衡因子应介于-2到2之间 } } return true;}代码解析：
代码结构
这段代码是一个用于向 AVL 树中插入一个键值对 (pair<k, v>) 的函数 insert。AVL 树是一种自平衡的二叉查找树，其特点是任意节点的左右子树的高度差不超过 1。
代码步骤
检查根节点：
if (_root == nullptr) { _root = new Node(kv); return true;}_root 是否为空，如果为空，则直接创建一个新的节点作为根节点，并返回 true 表示插入成功。 寻找插入位置：
Node* parent = nullptr;Node* cur = _root;while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { return false; }}parent 和 cur 分别指向当前节点的父节点和当前节点。通过循环遍历树，找到合适的位置插入新节点。如果当前节点的键大于要插入的键，则向左子树移动；如果当前节点的键小于要插入的键，则向右子树移动。如果找到了键相同的节点，则返回 false 表示插入失败（AVL 树不允许键重复）。 插入新节点：
cur = new Node(kv);if (parent->_kv.first > kv.first) { parent->_left = cur;} else if (parent->_kv.first < kv.first) { parent->_right = cur;}cur->_parent = parent;cur 并将键值对 kv 存入其中。根据父节点与新节点的关系，将新节点作为父节点的左子节点或右子节点。设置新节点的父节点指针。 更新平衡因子并进行必要的旋转
while (parent) { if (parent->_left == cur) { parent->_bf--; } else { parent->_bf++; } if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 旋转操作 break; } else { assert(false); }}
从新插入的节点开始向上遍历，更新每个节点的平衡因子。
检查每个节点的平衡因子： 如果平衡因子为 0，说明树已经恢复平衡，跳出循环。如果平衡因子为 ±1，表示轻微不平衡，继续向上遍历。如果平衡因子为 ±2，表示严重不平衡，需要进行旋转操作来重新平衡树。如果平衡因子不在上述范围内，则表示出现了不应该发生的情况。旋转操作：
根据具体情况选择适当的旋转操作：单左旋、单右旋或者双旋（先左后右或先右后左）。旋转
这里可能会比较抽象，因为在我以前博客中二叉树并没有这样的操作，大家可以配合画图来进行阅读，这样会比较好理解。
旋转的原则
保持搜索树的规则：旋转后的树必须仍然是有效的二叉搜索树，即对于任意节点 NN，所有左子树中的节点的键值都小于 NN 的键值，所有右子树中的节点的键值都大于 NN 的键值。
让旋转的树从不平衡变为平衡，并且尽可能降低旋转树的高度：通过旋转操作，使树恢复到平衡状态，并尽量减少树的高度，从而提高树的操作效率。
旋转类型
AVL树中常见的旋转类型有四种：
1. 左单旋（Left Rotation）
适用场景：当新增节点导致节点 AA 的右子树 BB 的高度比左子树高 2 个单位时，并且 BB 的左子树高度小于等于其右子树高度。效果：将 BB 旋转到 AA 的位置，AA 成为 BB 的左子树。判断：如果失衡节点是2，代表该节点的左树低，右树高做左单旋
我们再看一个图：
这边插入parent->subR->right，15的平衡因子变成1,10的平衡因子变成了2，证明右树高于左树，需要左单旋。这里有一个规律：subR->left 给了parent->right,然后subR->left变成了parent.
特殊情况：
parent不是root，那就是说parent还有一个父亲，这里需要判断处理。
实现代码：
// 左旋函数定义void Rotate_l(Node* parent) { Node* subR = parent->_right; // 获取父节点的右子节点 Node* subRL = subR->_left; // 获取右子节点的左子节点 // 旋转过程开始 parent->_right = subRL; // 将父节点的右子节点设置为右子节点的左子节点 if (subRL) { // 检查新的右子节点是否为空，避免野指针 subRL->_parent = parent; // 设置新右子节点的父节点为当前父节点 } // 存储父节点的父节点，方便后续链接 Node* parentParent = parent->_parent; subR->_left = parent; // 将右子节点的左子节点设置为当前父节点 parent->_parent = subR; // 设置当前父节点的父节点为右子节点 // 判断是否是根节点还是局部旋转，以便正确地链接上下节点 if (parentParent == nullptr) { // 如果当前节点是根节点 _root = subR; // 新的根节点是右子节点 subR->_parent = nullptr; // 根节点的父节点应该为 null } else { // 如果不是根节点，则根据其位置进行相应的调整 if (parent == parentParent->_left) { // 当前节点是其父节点的左子节点 parentParent->_left = subR; // 将父节点的左子节点设置为右子节点 } else { // 当前节点是其父节点的右子节点 parentParent->_right = subR; // 将父节点的右子节点设置为右子节点 } subR->_parent = parentParent; // 右子节点的父节点设置为其原来的父节点 } // 更新旋转后节点的平衡因子 parent->_bf = subR->_bf = 0; // 假设每次旋转之后，这两个节点的平衡因子都变为0}2. 右单旋（Right Rotation）
适用场景：当新增节点导致节点 AA 的左子树 BB 的高度比右子树高 2 个单位时，并且 BB 的右子树高度小于等于其左子树高度。效果：将 BB 旋转到 AA 的位置，AA 成为 BB 的右子树。
还是一样，上面这个图是给你展示是如何旋转的，下面我来介绍旋转的过程
这边插入parent->subL->left，5的平衡因子变成-1,10的平衡因子变成了-2，证明左树高于右树，需要右单旋。这里有一个规律：subL->right给了parent->left,然后subL->left变成了parent.
特殊情况：
parent不是root，那就是说parent还有一个父亲，这里需要判断处理。
这三种何况都是一个概括，图三也计算了有多少种组合。
代码实现：
// 右旋函数定义void Rotate_r(Node* parent) { // 注意：这里的参数名已从 Rotate_r 改为 Rotate_r 并且 Node* 类型前没有 const，因为我们会修改这些节点 Node* subL = parent->_left; // 获取父节点的左子节点 Node* sublr = subL->_right; // 获取左子节点的右子节点 // 旋转过程开始 parent->_left = sublr; // 将父节点的左子节点设置为左子节点的右子节点 if (sublr) { // 检查新的左子节点是否为空，避免野指针 sublr->_parent = parent; // 设置新左子节点的父节点为当前父节点 } // 存储父节点的父节点，方便后续链接 Node* Pparent = parent->_parent; subL->_right = parent; // 将左子节点的右子节点设置为当前父节点 parent->_parent = subL; // 设置当前父节点的父节点为左子节点 // 判断是否是根节点还是局部旋转，以便正确地链接上下节点 if (parent == _root) { // 如果当前节点是根节点 _root = subL; // 新的根节点是左子节点 subL->_parent = nullptr; // 根节点的父节点应该为 null } else { // 如果不是根节点，则根据其位置进行相应的调整 if (Pparent->_left == parent) { // 当前节点是其父节点的左子节点 Pparent->_left = subL; // 将父节点的左子节点设置为左子节点 } else if (Pparent->_right == parent) { // 当前节点是其父节点的右子节点 Pparent->_right = subL; // 将父节点的右子节点设置为左子节点 } subL->_parent = Pparent; // 左子节点的父节点设置为其原来的父节点 } // 更新旋转后节点的平衡因子 subL->_bf = parent->_bf = 0; // 假设每次旋转之后，这两个节点的平衡因子都变为0}3. 左右双旋（Left-Right Double Rotation）
适用场景：当新增节点导致节点 AA 的右子树 BB 的高度比左子树高 2 个单位时，并且 BB 的左子树高度大于其右子树高度。过程：首先对 BB 进行左旋，然后对 AA 进行右旋。效果：先通过左旋使 BB 的左子树成为新的右子树，再通过右旋使新的右子树成为 AA 的新位置。
这两个图插入之后都变的不平衡，第一个图，对他进行了一个右旋，会发现他只是对称了一下，出现这个问题的原因是插入位置的不同，左旋和右旋都是插入在最大，最小的位置。而这里插入的是小中最大的位置。如何判断是这个位置：平衡因子
大家可以边看代码边画图自己分析一下就懂了
// 左右旋转调整（LR旋转）函数// 参数parent是需要进行旋转操作的节点的父节点void Rotate_LR(Node* parent) { // 获取parent的左子节点 Node* subl = parent->_left; // 获取subl的右子节点，这将是旋转的核心节点 Node* sublr = subl->_right; // 存储sublr的平衡因子 int bf = sublr->_bf; // 首先执行左旋操作来调整subl节点 Rotate_L(parent->_left); // 然后执行右旋操作来调整parent节点 Rotate_R(parent); // 根据sublr的平衡因子更新相关节点的平衡因子 if (bf == 0) { // 如果sublr的平衡因子为0，则所有相关节点的平衡因子都设为0 subl->_bf = 0; sublr->_bf = 0; parent->_bf = 0; } else if (bf == 1) { // 如果sublr的平衡因子为1，则设置parent的平衡因子为0，subl的为-1，sublr的为0 parent->_bf = 0; subl->_bf = -1; sublr->_bf = 0; } else if (bf == -1) { // 如果sublr的平衡因子为-1，则设置subl的平衡因子为0，sublr的为0，parent的为1 subl->_bf = 0; sublr->_bf = 0; parent->_bf = 1; } else { // 如果平衡因子不是以上三种情况中的任何一种，则断言失败 assert(false); }}4. 右左双旋（Right-Left Double Rotation）
适用场景：当新增节点导致节点 AA 的左子树 BB 的高度比右子树高 2 个单位时，并且 BB 的右子树高度大于其左子树高度。过程：首先对 BB 进行右旋，然后对 AA 进行左旋。效果：先通过右旋使 BB 的右子树成为新的左子树，再通过左旋使新的左子树成为 AA 的新位置。
这个和左右旋是一个相反的概念，就不做讲解
//右左旋void Rotati_RL(Node* parent) {Node* subr = parent->_right;Node* subrl = subr->_left;//存储subrl的平衡因子int bf = subrl->_bf;//旋转Rotati_r(parent->_right);Rotati_l(parent);//更新平衡因子if (bf == 0) {subr->_bf = 0;subrl->_bf = 0;parent->_bf = 0;}else if (bf == 1){parent->_bf = -1;subrl->_bf = 0;subr->_bf = 0;}else if (bf == -1){parent->_bf = 0;subrl->_bf = 0;subr->_bf = 1;}else{assert(false);}}AVL树的查找
这个二叉树的时候经常用：
Node* Find(const k& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}AVL树的平衡检测
我们是如何判断AVL树是否平衡？
我们可以通过检查左右子树高度差的的程序进行反向验证，同时检查⼀下结点的平衡因子更新是否出现了问题。
直接代码：
如果右递归不是很好的朋友，可以画递归展开图来帮助自己理解
//计算高度int _Height(Node* root) {if (root == nullptr)return 0;int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;}//判断是否是否平衡bool _IsBalanceTree(Node* root) {//空树也是AVL树if (root == nullptr) return true;//计算高度差int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);int diff =RightHeight - LeftHeight;//判断if (abs(diff) >= 2){cout << root->_kv.first << "⾼度差异常" << endl;assert(false);return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}总结
先附上我的git:
AVL树/AVL树 · 普通小青年/c++学习 - 码云 - 开源中国 (gitee.com)
AVL树通过维护每个节点的平衡因子来保持树的平衡状态。当插入，如果发现某节点的平衡因子不在{-1, 0, 1}范围内，则需要根据具体情况选择适当的旋转策略来进行调整，以恢复树的平衡性。
每个节点都有一个平衡因子（balance factor, BF），它定义为该节点的左子树高度减去右子树高度： BF=height(left subtree)−height(right subtree)BF=height(left subtree)−height(right subtree)
平衡因子的可能值为 -1、0 或 1。如果平衡因子的绝对值大于1，则表示树不平衡，需要进行旋转调整。
