C++进阶：AVL树详解及模拟实现（图示讲解旋转过程）
之前在搜索二叉树最后早就埋下伏笔，来介绍AVL树和红黑树，今天就先来第一个吧
文章目录
- 1.AVL树介绍
- 1.1概念介绍
- 1.2核心性质
- 2.项目文件规划
- 3.整体框架（节点和Tree）
- 4.AVL树的新节点插入
- 4.1新节点插入当前节点的右子树的右子树——左旋转
- 左旋 (Left Rotation)
- 情况：
- 操作：
- 4.2新节点插入当前节点的左子树的左子树——右旋转
- 右旋 (Right Rotation)
- 情况：
- 操作：
- 4.3新节点插入当前节点的左子树的右子树——左右双旋
- 左右双旋（LR旋转）
- 4.4新节点插入当前节点的右子树的左子树——右左双旋
- 右左旋（RL旋转）
- 4.5组装完整版Insert（）
- 5.中序方便过会测试
- 6.编写函数看是否满足要求
- 6.1求高度
- 6.2 平衡否
- 7.测试
- 8.全部代码
- 8.1 AVLTree.h
- 8.2 test.cpp
1.AVL树介绍
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法，人为规定：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过
1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度
1.1概念介绍
- AVL树定义：
- 解释AVL树是一种自平衡的二叉搜索树，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。
- 强调AVL树中每个节点的平衡因子（Balance Factor），即左子树高度和右子树高度之差不超过1。
- 平衡因子：
- 解释平衡因子的概念，即一个节点的左子树高度减去右子树高度的值。
- 平衡因子为{-1, 0, 1}时，树是平衡的。
- 自平衡性质：
- 说明AVL树具有自平衡性质，即在插入或删除节点时，会通过旋转操作来保持树的平衡。
- 提及AVL树的平衡因子限制，确保树的高度保持在对数级别。
1.2核心性质
-
严格平衡：
- 强调AVL树的严格平衡性质，即每个节点的左右子树高度差不超过1。
- 严格平衡性质保证了AVL树的高度近似于对数级别，保证了高效的插入、删除和查找操作。
-
插入和删除操作：
- 介绍当插入或删除节点时，AVL树如何通过旋转操作来保持平衡。
- 解释插入和删除操作可能会导致树失去平衡，需要通过单旋转、双旋转等操作进行调整。
-
时间复杂度：
- 说明AVL树的插入、删除和查找操作的时间复杂度都是O(log n)，其中n为树中节点的数量。
- 强调AVL树在动态数据集合中的高效性，适用于需要频繁更新的场景。
2.项目文件规划
头文件AVLTree.h：进行模拟的编写
源文件test.cpp：进行测试，检查代码逻辑是否满足期望
3.整体框架（节点和Tree）
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;//父亲节点
int _bf; // balance factor 平衡因子
pair<K, V> _kv;//每个节点里存一个pair
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)//都直接在初始化列表里初始化了
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;//名字太长了，叫Node也更好理解
public:
private:
Node* _root = nullptr;//给上缺省值
};
4.AVL树的新节点插入
基本步骤：
- 查找插入位置： 首先，我们需要找到新节点应该插入的位置。从根节点开始，按照二叉搜索树的性质，逐级向左或向右比较键值，直到找到一个合适的位置。
- 插入新节点： 找到插入位置后，我们创建一个新的节点，并将其插入到树中。如果树为空，则新节点成为树的根节点。否则，将新节点插入到合适的位置，使得树仍然保持二叉搜索树的性质。
- 更新平衡因子： 在插入新节点后，需要沿着插入路径更新所有受影响节点的平衡因子。平衡因子是指节点的左右子树的高度差。如果插入导致某个节点的平衡因子超出范围（通常是 -1、0、1），则需要进行旋转操作来恢复平衡。
- 平衡调整： 如果插入操作破坏了 AVL 树的平衡性，我们需要进行一系列的旋转操作来重新平衡树。旋转操作包括单旋转和双旋转，具体的旋转方式取决于插入节点的位置以及平衡因子的情况。
- 旋转后继续向上： 插入节点后，可能需要对父节点、祖父节点等进行旋转操作，直到树恢复平衡为止。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果是空树
{
_root = new Node(kv);
return true;//插入成功
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//这里开始找位置
{
if (kv.first < cur->_kv.first)//小于往左走
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//不能有相等的
}
}
//开始把新节点链接上
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent != nullptr)//cur到跟节点停下
{
if (cur == parent->_left)//在左就--
{
parent->_bf--;
}
else//在右++
{
parent->_bf++;
}
//开始检查父亲节点的情况
if (parent->_bf == 0)
{
break;//直接停止
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;//向上走
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//破坏了规则了，开始旋转
}
else
{
// 会到这说明插入之前AVL树就有问题
assert(false);
}
}
}
更新平衡因子过程：
更新的原则如下：
- 如果新节点插入到父节点的左侧，则父节点的平衡因子减一。
- 如果新节点插入到父节点的右侧，则父节点的平衡因子加一。
更新后，需要检查父节点的平衡因子是否发生变化，如果发生变化，则继续向上检查祖先节点的平衡因子，直到根节点或者到达一个平衡因子为 ±1 的节点为止。根据更新后节点的平衡因子情况，可以采取以下处理措施：
- 如果节点的平衡因子为 0，表示节点所在子树的高度没有变化，不会影响祖先节点的平衡因子，更新结束。
- 如果节点的平衡因子为 ±1，表示节点所在子树的高度变化（本来是0，现在变成 ±1，子树高度变了），会影响祖先节点的平衡因子，需要继续向上更新祖先节点的平衡因子。
- 如果节点的平衡因子为 ±2，表示节点所在子树违反了平衡规则，需要进行平衡调整操作（如旋转），然后更新结束。
4.1新节点插入当前节点的右子树的右子树——左旋转
左旋 (Left Rotation)
左旋的情况是当一个节点的右子树过高，需要进行左旋来降低右子树的高度，同时保持树的平衡。
情况：
- 新节点插入到当前节点的右子树的右子树中，导致当前节点的平衡因子为 +2。
- 在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。
操作：
左旋是指将当前节点向左旋转，使得当前节点的右子树的左子树成为当前节点的右子树，同时将当前节点成为其右子树的左子树。
A B / \ / \ T1 B ==> A T3 / \ / \ T2 T3 T1 T2
void RotateL(Node* parent)
{
Node* subR = parent->_right;//要成为根的
Node* subRL = subR->_left;//要成为30的右子树
parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;
subR->_left = parent;
Node* pparent = parent->_parent;//存一下，新根才能链接
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)//parent在pp的左，那我新的跟subR也要左
{
ppnode->_left = subR;
}
else//同理
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
4.2新节点插入当前节点的左子树的左子树——右旋转
右旋 (Right Rotation)
右旋的情况是当一个节点的左子树过高，需要进行右旋来降低左子树的高度，同时保持树的平衡。
情况：
- 新节点插入到当前节点的左子树的左子树中，导致当前节点的平衡因子为 -2。
- 在双旋的过程中，当左子树的平衡因子为 -1，右子树的平衡因子为 +1。
操作：
右旋是指将当前节点向右旋转，使得当前节点的左子树的右子树成为当前节点的左子树，同时将当前节点成为其左子树的右子树。
A B / \ / \ B T3 ==> T1 A / \ / \ T1 T2 T2 T3
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = 0;
parent->_bf = 0;
}
4.3新节点插入当前节点的左子树的右子树——左右双旋
当新节点插入当前节点的左子树的右子树时，会触发左右双旋操作（LR旋转）。这种情况发生在当前节点的左子树的右子树上插入了新节点，导致当前节点的平衡因子不平衡（可能为+2或-2），且当前节点的左子树的右子树的平衡因子为正值（+1）。为了恢复 AVL 树的平衡性，需要先对当前节点的左子树进行一次左旋操作，然后再对当前节点进行一次右旋操作。
左右双旋（LR旋转）
具体步骤如下：
- 对当前节点的左子树进行一次左旋操作。
- 对当前节点进行一次右旋操作。
示例：
假设当前节点为 A，新节点插入在 A 的左子树的右子树的情况下，左右双旋操作如下：
A A C / \ / \ / \ B T4 左旋后 C T4 右旋后 B A / \ ---------> / \ ---------> / \ / \ T1 C B T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//存一下，后面要更新bf
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
4.4新节点插入当前节点的右子树的左子树——右左双旋
右左旋（RL旋转）
右左旋操作发生在节点的右子树过深，导致平衡因子为 -2 且其右子节点的平衡因子为 +1 的情况下。具体步骤如下：
- 对 A 的右子树进行一次左旋操作。
- 再对 A 进行一次右旋操作。
示例：
A A C / \ / \ / \ T1 B ==> T1 C ==> A B / \ / \ / \ / \ C T4 T2 B T1 T2 T3 T4 / \ / \ T2 T3 T3 T4
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
}
}
4.5组装完整版Insert（）
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果是空树
{
_root = new Node(kv);
return true;//插入成功
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//这里开始找位置
{
if (kv.first < cur->_kv.first)//小于往左走
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//不能有相等的
}
}
//开始把新节点链接上
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent != nullptr)//cur到跟节点停下
{
if (cur == parent->_left)//在左就--
{
parent->_bf--;
}
else//在右++
{
parent->_bf++;
}
//开始检查父亲节点的情况
if (parent->_bf == 0)
{
break;//直接停止
}
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)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else
{
RotateRL(parent);
}
break;//调整完后就平衡了，也不用向上，直接出去
}
else
{
// 会到这说明插入之前AVL树就有问题
assert(false);
}
}
}
5.中序方便过会测试
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << "[" << root->_bf << "]" << endl;
_InOrder(root->_right);
}
6.编写函数看是否满足要求
只要有一个节点的左子树与右子树的高度差距大于等于2，那么就不满足了
从这里也能看出要写一个求高度函数更方便
6.1求高度
int Height()
{
_Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int right = _Height(root->_right);
int left = _Height(root->_left);
return right > left ? right + 1 : left + 1;
}
这段代码实现了 AVL 树的高度计算和平衡性检查功能。
_Height函数:这个函数用于计算给定树的高度。递归地计算左右子树的高度，然后返回较大的子树高度加上 1。这个函数被用于计算整棵树的高度。
Height函数:这个函数是对外提供的接口，用于获取 AVL 树的高度。它调用
_Height函数并传入根节点，返回整棵 AVL 树的高度。
6.2 平衡否
bool IsBalance()
{
int height = 0;
return _IsBlance(_root, height);
}
bool _IsBlance(Node* root, int& h)
{
if (root == nullptr)
{
h = 0;
return true;
}
int leftHeight = 0, rightHeight = 0;
if (!_IsBlance(root->_left, leftHeight)
|| !_IsBlance(root->_right, rightHeight))
{
return false;
}
if (abs(rightHeight - leftHeight) >= 2)
{
cout << root->_kv.first << "不平衡" << endl;
return false;
}
h= leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
return true;
}
_IsBalance函数:这个函数用于检查 AVL 树的平衡性。它递归地检查树的每个节点，计算左右子树的高度并比较它们的差值，如果差值大于等于 2，则表示不平衡。此外，还检查每个节点的平衡因子是否正确，即右子树高度减去左子树高度等于节点的平衡因子。如果平衡因子异常，则表示树不平衡。
IsBalance函数:这个函数是对外提供的接口，用于检查整棵 AVL 树的平衡性。它调用
_IsBalance函数并传入根节点，返回整棵 AVL 树是否平衡的结果。这些函数的实现是 AVL 树的重要部分，用于确保 AVL 树保持平衡性和正确性。
7.测试
void TestAVLTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
cout << e << "->" << t.IsBalance() << endl;
}
t.InOrder();
cout << t.IsBalance() << endl;
}
8.全部代码
8.1 AVLTree.h
#pragma once
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;//父亲节点
int _bf; // balance factor 平衡因子
pair<K, V> _kv;//每个节点里存一个pair
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)//都直接在初始化列表里初始化了
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;//名字太长了，叫Node也更好理解
public:
void RotateL(Node* parent)
{
Node* subR = parent->_right;//要成为根的
Node* subRL = subR->_left;//要成为30的右子树
parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;//存一下，新根才能链接
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)//parent在pp的左，那我新的跟subR也要左
{
ppnode->_left = subR;
}
else//同理
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = 0;
parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//存一下，后面要更新bf
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
}
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果是空树
{
_root = new Node(kv);
return true;//插入成功
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//这里开始找位置
{
if (kv.first < cur->_kv.first)//小于往左走
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//不能有相等的
}
}
//开始把新节点链接上
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent != nullptr)//cur到跟节点停下
{
if (cur == parent->_left)//在左就--
{
parent->_bf--;
}
else//在右++
{
parent->_bf++;
}
//开始检查父亲节点的情况
if (parent->_bf == 0)
{
break;//直接停止
}
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)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else
{
RotateRL(parent);
}
break;//调整完后就平衡了，也不用向上，直接出去
}
else
{
// 会到这说明插入之前AVL树就有问题
assert(false);
}
}
}
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << "[" << root->_bf << "]" << endl;
_InOrder(root->_right);
}
int Height()
{
_Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int right = _Height(root->_right);
int left = _Height(root->_left);
return right > left ? right + 1 : left + 1;
}
bool IsBalance()
{
int height = 0;
return _IsBlance(_root, height);
}
bool _IsBlance(Node* root, int& h)
{
if (root == nullptr)
{
h = 0;
return true;
}
int leftHeight = 0, rightHeight = 0;
if (!_IsBlance(root->_left, leftHeight)
|| !_IsBlance(root->_right, rightHeight))
{
return false;
}
if (abs(rightHeight - leftHeight) >= 2)
{
cout << root->_kv.first << "不平衡" << endl;
return false;
}
h= leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
return true;
}
private:
Node* _root = nullptr;//给上缺省值
};
void TestAVLTree1()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
cout << e << "->" << t.IsBalance() << endl;
}
t.InOrder();
cout << t.IsBalance() << endl;
}
8.2 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
#include"AVLTree.h"
int main()
{
TestAVLTree1();
return 0;
}
今天就到这里啦！！下一次肯定是红黑树啦！！！
![weblogic [WeakPassword]](https://img-blog.csdnimg.cn/direct/9b1a614a556840429f89f834ffdab968.png)
