前言
AVL树，是一种“平衡”的二叉搜索树，关于搜索树的介绍和模拟，我已经在该篇文章（二叉搜索树的模拟实现-CSDN博客）介绍过，想复习或者了解二叉搜索树的读者可以去看看哦
♪(´▽｀)
什么叫平衡呢？
AVL树在二叉搜索树的基础上，进行了平衡调整，也就是每插入一个数，就会检查是否有两棵子树的高度差超过1，若超过，就将“旋转”调整至平衡，这是为了解决二叉树在数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下的问题
而AVL树的最重要的部分，也就是调整平衡啦❀ヾ(≧▽≦*)o，平衡因子是可以用来检测是否平衡的哦，我的模拟实现也是用这种方法哦~(￣▽￣)~***
平衡因子
平衡因子 = 右子树高度 - 左子树高度
当平衡因子的绝对值大于1时，就出现了“不平衡”现象，就要分情况来进行旋转调整啦~
知道了上面这些，相信你对AVL树有了基本了解啦，现在让我们开始吧( ‵▽′)ψ
代码实现
基础结构
AVL树与普通树的节点的不同
① 它的每个节点除了有左右孩子的指针，还有父母的指针
② 存的数据是键值对，也就是key-value结构，我在二叉搜索树的模拟实现-CSDN博客中介绍过
key结构： 通常用来用于： 查找某值是否存在 现实使用场景： 门禁系统 key、value结构 通常用于： 1、确定一个值是否存在 2、通过key查找value 现实使用场景： 字典
以下就是该部分的代码啦
代码语言：javascript复制template<typename K, typename V>// 类模板
struct AVLTreeNode// 类外也要使用，所以定义为struct
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;/**/
pair<K, V>_kv;/*键值对*/
int _bf;// 平衡因子（右子树高度 - 左子树高度）
// 构造函数
AVLTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};函数部分
构造部分
代码语言：javascript复制template<typename K, typename V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;// typedef后，方便使用
private:
Node* _root = nullptr;// 初始化
};Insert函数
代码语言：javascript复制 bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
// 查找合适的插入位置，与二叉搜索树相同
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 调整平衡因子
while (parent)
{
// 插入在右子树，平衡因子
if (cur == parent->_left)
{
parent->_bf--;
}
else// 插入在左子树，平衡因子--
{
parent->_bf ;
}
// 平衡因子 = 0，说明并未破坏平衡，不用再向上调整平衡因子
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{// 继续向上检查是否平衡
cur = parent;
parent = cur->_parent;
}
else
{
// 旋转
}
}
return true;
}旋转情况(敲重点！！！~(≧▽≦)/~)
1、右右情况 2、左左情况 3、左右情况 4、右左情况
1、右右情况 ——— 左单旋
右右情况
① 对于不平衡节点（该处是1）来说，插入元素在其右子树 ② 对于不平衡节点的右孩子（这里是2）来说，插入节点也在其右子树
这种情况我们需要左旋
左旋总步骤
拆解
① 将不平衡节点(root)的右孩子（subR）的左孩子(subRL) 给 不平衡节点 的右孩子
② 不平衡节点(root)做 subR的左孩子
最后各点的平衡因子如下
为什么叫左旋呢？
是不是很像向左旋转了一下呢 q(≧▽≦q)
代码
代码语言：javascript复制 // 左单旋
void RotateL(Node* root)
{
Node* subR = root->_right;
Node* subRL = subR->_left;/*可能为空*/
// 更新root的右孩子
root->_right = subRL;
// 更新父亲
// 注意subRL可能为空的情况
if (subRL)
{
subRL->_parent = root;
}
subR->_parent = root->_parent;
root->_parent = subR;
// 更新subR的左孩子
subR->_left = root;
// 注意root为整棵树的根时的情况
if (root == _root)
_root = subR;
// 将 原本指向root的父节点 改为 指向subR
if (subR->_parent)
{
if (root == subR->_parent->_left)
{
subR->_parent->_left = subR;
}
else
subR->_parent->_right = subR;
}
// 最后平衡因子都变为0
subR->_bf = root->_bf = 0;
}2、左左情况
和右右情况相反
1、插入元素在不平衡节点(root)的左子树（subL） 2、在不平衡节点(root)的左子树(subL)的左子树
右旋步骤
右旋
1、subL的右孩子subLR做root的左孩子
2、root做subL的右孩子
为什么叫右旋？
是不是向右旋转了呢(´▽`ʃ♡ƪ)
平衡因子变化：
root ： -2 -----> 0 subL：-1 ------> 0 subRL :不变
代码
代码语言：javascript复制 // 右单旋
// 与左单旋代码类似
void RotateR(Node* root)
{
Node* subL = root->_left;
Node* subLR = subL->_right;/*可能为空*/
root->_left = subLR;
if (subLR)
{
subLR->_parent = root;
}
subL->_right = root;
subL->_parent = root->_parent;
root->_parent = subL;
if (root == _root)
_root = subL;
if (subL->_parent)
{
if (root == subL->_parent->_left)
{
subL->_parent->_left = subL;
}
else
subL->_parent->_right = subL;
}
subL->_bf = root->_bf = 0;
}3、左右情况
情况1：subLR->_bf = 0
平衡因子变化：
root: -2 -> 0 subL: 1 -> 0 subLR: 0不变
情况2：subLR->_bf = 1
平衡因子变化：
root: -2 -> 0 subL: 1不变 subLR: 1 -> 0
情况3：subLR->_bf = -1
为什么叫左右双旋呢？
无论是上面三种哪种情况，都是先左单旋（subL），再右单旋(root)
代码
代码语言：javascript复制 // 左右双旋
void RotateLR(Node* root)
{
/*
其实就是将根节点的左子树左旋，根节点再右旋
*/
Node* subL = root->_left;
Node* subLR = subL->_right;
// 记录subLR的平衡因子，方便后续分情况来更改subLR,subL,root的平衡因子
int bf = subLR->_bf;
// 左子树先左旋，根再右旋
RotateL(root->_left);
RotateR(root);
if (bf == 0)
{
// subLR就是新增
root->_bf = subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
// 在subLR的右边新增
subL->_bf = -1;
root->_bf = subLR->_bf = 0;
}
else if (bf == -1)
{
// 在subRL的左边新增
root->_bf = 1;
subLR->_bf = subL->_bf = 0;
}
}4、右左情况
与左右情况极其类似
① 先对右子树右单旋 ② 再对根节点左单旋
大家可以自己画画图哦，看一下自己理解的怎么样哦(●ˇ∀ˇ●)
代码
代码语言：javascript复制// 右左双旋
void RotateRL(Node* root)
{
/*
其实就是将根节点的右子树右旋，根节点再左旋
*/
Node* subR = root->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
// 子树先右旋，根再左旋
RotateR(root->_right);
RotateL(root);
if (bf == 0)
{
// subRL就是新增
root->_bf = subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
// 在subRL的右边新增
root->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// 在subRL的左边新增
subR->_bf = 1;
subRL->_bf = root->_bf = 0;
}
}Inorder中序遍历
与二叉搜索树的地方一样哦
代码语言：javascript复制 void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}isBalance检查是否平衡
检查平衡要有三个要求：
代码语言：javascript复制1、根节点的平衡因子 = 右子树高度 - 左子树高度 2、两子树高度差的绝对值 < 2 3、所有子树都满足以上要求
bool isBalance()
{
/*
这种对外接口内部调用另一函数的原因，我在开头提到的那篇博客讲过
这样子写就可以不需要外部调用时还要知道AVL树的根了，直接调用就好
*/
// 检验该树是否平衡
return _isBalance(_root);
}
bool _isBalance(Node* root)
{
if (root == nullptr)
return true;
// 获取左右子树高度
int leftHeight = getHeight(root->_left);
int rightHeight = getHeight(root->_right);
// 看根节点的平衡因子是否合理
if (root->_bf != rightHeight - leftHeight)
{
cout << "_bf错误" << endl;
return false;
}
// 看高度差的绝对值是否小于2
return abs(rightHeight - leftHeight) < 2
// 继续检查子树是否合理
&& _isBalance(root->_left)
&& _isBalance(root->_right);
}
int getHeight(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = getHeight(root->_left);
int rightHeight = getHeight(root->_right);
// 根节点高度 = 左右子树较高者的高度 1
return max(leftHeight, rightHeight) 1;
}测试代码
以下测试代码可以帮你测试是否所有情况你的代码都能正确解决
代码语言：javascript复制void test1()
{
// 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[] = {10, 3, 7 };// 左右双旋
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert({e, e});
}
t.InOrder();
if (!t.isBalance())
cout << "该树不平衡" << endl;
}
void test2()
{
// 随机数据测试
const int N = 30;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i )
{
v.push_back(rand());
// cout << v.back() << endl;
}
AVLTree<int, int> t;
for (auto e : v)
{
if (e == 14604)
{
int x = 0;
}
t.Insert(make_pair(e, e));
if (!t.isBalance())
cout << "该树不平衡" << endl;
}
}结语
好啦，恭喜你今天又进步一点点哦~~如果支持博主的话，可以给博主点赞、收藏、关注(´▽`ʃ♡ƪ)哦，后续我将更新《红黑树》部分，待我学成归来(*≧︶≦))(￣▽￣* )ゞ
