前言

本篇博客讲解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树的结构

<code>//定义节点结构

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)：当父节点的平衡因子为正数（表示左子树较高），并且当前节点的平衡因子也为正数时，表示当前节点的左子树较高，需要进行左旋来平衡树。

右旋(R)：当父节点的平衡因子为负数（表示右子树较高），并且当前节点的平衡因子也为负数时，表示当前节点的右子树较高，需要进行右旋来平衡树。

先右后左双旋(RL)：当父节点的平衡因子为正数（左子树较高），但当前节点的平衡因子为负数（当前节点的右子树较高）时，首先需要对当前节点进行右旋，然后对其父节点进行左旋。

先左后右双旋(LR)：当父节点的平衡因子为负数（右子树较高），但当前节点的平衡因子为正数（当前节点的左子树较高）时，首先需要对当前节点进行左旋，然后对其父节点进行右旋。

示例表格

父节点(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，代表了它的右子树高于左子树，这边需要做一个双旋

没更新到底部，这个树只需要更新平衡因子，不需要做旋转处理，因为平衡，从这里就可以看出树的平衡是看平衡因子

更新到最底部：算最坏的情况

---

插入结点及更新平衡因子的代码实现

<code>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还有一个父亲，这里需要判断处理。

        实现代码：

<code>// 左旋函数定义

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还有一个父亲，这里需要判断处理。

这三种何况都是一个概括，图三也计算了有多少种组合。

代码实现：

<code>// 右旋函数定义

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 的新位置。

这两个图插入之后都变的不平衡，第一个图，对他进行了一个右旋，会发现他只是对称了一下，出现这个问题的原因是插入位置的不同，左旋和右旋都是插入在最大，最小的位置。而这里插入的是小中最大的位置。如何判断是这个位置：平衡因子

大家可以边看代码边画图自己分析一下就懂了

<code>// 左右旋转调整（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 的新位置。

这个和左右旋是一个相反的概念，就不做讲解

<code>//右左旋

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，则表示树不平衡，需要进行旋转调整。

---

​​​​​​​