AVL树（c++版）
前言
前面我们介绍了平衡二叉搜素树，但是在某些极端的情况下会退化为单分支树，大大提高了搜索插入等操作的时间复杂度，那么有没有一种树形的数据结构可以保证树形尽可能的接近平衡，这就是我们今天要介绍的AVL树，它可以保证是一颗⾃平衡⼆叉查找树。它是⼀颗空树，或者它的左右⼦树都是AV树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡
AVL的历史和发展我们就不再展开，感兴趣的朋友可以自行查询相关资料
前面我们介绍了AVL树通过控制高度去控制平衡 ，我们由此引入一个平衡因子的概念，它是该节点右树高度减去左树高度的值，它可以监测该节点是否满足AVL树的规则。由AVL树的规则可知，该值的取值为 -1，0，1 。注意，AVL树的实现可以不引入平衡因子的概念，这里可以按需操作，我们这里按引入实现
AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在logN ，那么增删查改的效率也可
以控制在logN
AVL树的结构
我们先来认识一下每个节点的结构
节点结构
template<class K, class V> //声明为模板类，kV结构，为了复用代码
class treeNode
{
typedef treeNode<K, V> Node; //对节点进行重命名，方便后续的使用
template<class K, class V>
friend class AVLTree;//这里先将AVL树声明为友元类，方便AVL树对节点属性和方法的操作和调用
public:
//两个构造函数
treeNode(const pair<K, V>& kv)
:_kv(kv)
{}
treeNode()
{}
private:
Node* _left = nullptr; //指向左子节点
Node* _right = nullptr; //指向右子节点
Node* _parent = nullptr; //指向父节点
pair<K, V> _kv; //节点存储的数据
int _bf = 0; //引入平衡因子的概念，监测树是否平衡
};树节点
template<class K, class V>
class AVLTree //声明为模板类，方便后续代码的复用
{
typedef treeNode<K, V> Node; //对节点进行重命名方便后续使用
public:
private:
Node* root = nullptr; //树节点主要存贮根节点的信息即可
};AVL树方法
此时我们已经将AVL树的结构搭建完成，现在我们只需要向这颗AVL树补充方法即可
插入
插入逻辑基本盘
首先我们需要实现一个AVL树的插入功能。无论如何，AVL树也是二叉搜素树，所以还是要遵从二叉搜素树的插入规则，我们先通过比较节点和待插入元素的大小找到合适的位置，进行插入。不过AVL树相比于普通的平衡二叉树多一个步骤，那就是跟新平衡因子，然后通过旋转调整树结构至符合要求。
新增的节点只会改变祖先的平衡因子，可能是全部，也可能是部分。此时就需要向根不断更新，直到该某节点更新前后的平衡因子不变才结束更新。如果遇到平衡因子不符合要求的节点需要旋转使得该节点的子树降低高度，旋转完之后一般也不需要继续向上更新，因为此时树的高度加一减一不变
更新的原则
平衡因子是右树高度-左树高度，只有⼦树⾼度变化才会影响当前结点平衡因⼦，插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦--，parent所在⼦树的⾼度是否变化决定了是否会继续往上更新。这里patent指的是新增节点挂载的父节点
更新停止的条件
更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前
parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会
影响parent的⽗亲结点的平衡因⼦，更新结束
更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上更新
更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说
明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼
了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把
parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不
需要继续往上更新，插⼊结束。这里旋转的逻辑又分为好多种（左单旋，右单旋，右左双旋，左右双旋），我们可以现将插入的骨架搭好，在逐一分析旋转的情况
bool insert(const pair<K, V>& kv) //返回值为bool，我们待定不允许相同值插入，标识是否插入成功。//参数是待插入的元素
{
if (root == nullptr) //空树直接插入，修改根节点
{
root = (Node*)new Node(kv);
return true;
}
Node* cut = root;
Node* rem = nullptr;
while (cut != nullptr)//找到合适的插入位置，rem会标识合适插入位置的父节点
{
if (cut->_kv.first > kv.first) //小值往左走
{
rem = cut;
cut = cut->_left;
}
else if (cut->_kv.first < kv.first) //大值往右走
{
rem = cut;
cut = cut->_right;
}
else //有相同元素插入失败
{
return false;
}
}
//将值插入
cut = (Node*)new Node(kv);
if (rem->_kv.first > cut->_kv.first)
{
rem->_left = cut;
rem->_bf--;
}
else
{
rem->_right = cut;
rem->_bf++;
}
//这里会不断向根节点检查更新平衡因子旋转以保持平衡
cut->_parent = rem;
while (rem != nullptr)
{
// 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0
if (rem->_bf == 0)
return true;
//更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1
else if (rem->_bf == -1 || rem->_bf == 1)
{
cut = rem;
rem = rem->_parent;
if (rem == nullptr)
return true;
if (rem->_left == cut)
rem->_bf--;
else
rem->_bf++;
}
// 更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2
else if (rem->_bf == 2 || rem->_bf == -2)
{
if (rem->_bf == -2 && cut->_bf == -1)//右单旋
rotateR(rem);
else if (rem->_bf == 2 && cut->_bf == 1)//左单旋
rotateL(rem);
else if (rem->_bf == -2 && cut->_bf == 1)//左右双旋
rotateLR(rem);
else if (rem->_bf == 2 && cut->_bf == -1)//右左双旋
rotateRL(rem);
else
assert(false);
break;
}
//出现不存在的情况，直接报错
else
{
assert(false);
}
}
return true;
}旋转
实现我们先来明确旋转的原则
保持搜索树的规则
让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋
右单旋
这里红色表示的是该节点的平衡因子。那三颗子树是抽象的表示，不标识平衡因子
这三颗抽象子树的高度都必须为H，否则不满足AVL树的规则或者更新旋转会对应到其他情况
此时我们在H1新增节点就对应右单旋
此时我们就需要旋转，旋转完成之后应该长这样
然后我们需要更新数据
下面我们就来简单的实现一下
这里传入的参数就是要旋转子树的根节点
void rotateR(Node*& par)
{
Node* chi = par->_left;
Node* chiR = chi->_right;
par->_left = chiR;
if (chiR)
chiR->_parent = par;
chi->_right = par;
chi->_parent = par->_parent;
par->_parent = chi;
if (chi->_parent)
{
if (chi->_parent->_left == par)
chi->_parent->_left = chi;
else
chi->_parent->_right = chi;
}
if (root == par)
root = chi;
par->_bf = 0;
chi->_bf = 0;
}前后子树的高度都为H+1，不需要继续更新
左单旋
左单旋可以说就是右单旋的镜像
此时我们在H2新增节点就对应右单旋
旋转后应该为
实现
void rotateL(Node*& par)
{
Node* chi = par->_right;
Node* chiL = chi->_left;
par->_right = chiL;
if (chiL != nullptr)
chiL->_parent = par;
chi->_left = par;
chi->_parent = par->_parent;
par->_parent = chi;
if (chi->_parent)
{
if (chi->_parent->_left == par)
chi->_parent->_left = chi;
else
chi->_parent->_right = chi;
}
if (root == par)
root = chi;
par->_bf = 0;
chi->_bf = 0;
}右左双旋
有的时候我们使用单旋并不能很好的降低高度
例如这种情况
我们自H1新增节点
这时候我们想到的是右单旋，看下旋转后的结果
右边高变成了左边高，这时原先的逻辑已经解决不了这个问题了，可以理解为单旋是解决纯粹一边高的问题，此时需要右左双旋。此时我们需要将H1这颗子树展开
插入一个节点在H3
先对节点1进行右旋，变成完全一边高
再对根节点进行左单旋调整为平衡
注意这里根据H的不同，又可以分为三种情况
场景1：h>=1时，插入在H3： 节点1，节点2，原先根节点平衡因子分别为1,0,0
场景2：h>=1时，插入在H4：节点1，节点2，原先根节点平衡因子分别为0,0，-1
场景3：h==0时：节点1，节点2，原先根节点平衡因子分别为0,0,0
这三种情况下节点1，节点2，原先的根节点对应的平衡因子更新各不相同，需要具体情况具体分析。这里就不展开画了，给个结论
实现
void rotateRL(Node*& par)
{
Node* chi = par->_right;
Node* chiL = chi->_left;
int bf = chiL->_bf;
rotateR(par->_right);
rotateL(par);
if (bf == -1)
{
par->_bf = 0;
chi->_bf = 1;
chiL->_bf = 0;
}
else if (bf == 1)
{
chi->_bf = 0;
par->_bf = -1;
chiL->_bf = 0;
}
else if (bf == 0)
{
chi->_bf = 0;
par->_bf = 0;
chiL->_bf = 0;
}
else
{
assert(false);
}
}左右双旋
左右双旋完全就是右左双旋的镜像
插入一个节点在H3
先对节点1进行左旋，变成完全一边高
在对根节点进行右旋
注意这里根据H的不同，又可以分为三种情况
场景1：h>=1时，插入在H3： 节点1，节点2，原先根节点平衡因子分别为0,0,1
场景2：h>=1时，插入在H4：节点1，节点2，原先根节点平衡因子分别为-1,0,0
场景3：h==0时：节点1，节点2，原先根节点平衡因子分别为0,0,0
这三种情况下节点1，节点2，原先的根节点对应的平衡因子更新各不相同，需要具体情况具体分析。这里就不展开画了，给个结论
实现
void rotateLR(Node*& par)
{
Node* chi = par->_left;
Node* chiR = chi->_right;
int bf = chiR->_bf;
rotateL(par->_left);
rotateR(par);
if (bf == -1)
{
par->_bf = 1;
chi->_bf = 0;
chiR->_bf = 0;
}
else if (bf == 1)
{
chi->_bf = -1;
par->_bf = 0;
chiR->_bf = 0;
}
else if (bf == 0)
{
chi->_bf = 0;
par->_bf = 0;
chiR->_bf = 0;
}
else
{
assert(false);
}
}查找
查找只需要根据平衡搜素树的规则进行查找即可
V Find(K& key)
{
Node* cut = this->root;
while (cut!=nullptr)
{
if (key > cut->_kv.first)
{
cut = cut->_right;
}
else if (key < cut->_kv.first)
{
cut = cut->_left;
}
else
{
return cut->_kv.second;
}
}
return V();
}平衡检测
我们可以实现一个平衡检测的代码
本质上就是递归检查节点的左右子树高度差是否满足要求
bool checkAVL()//公开的接口
{
return _checkAVL(this->root);
}
int _getHeight(Node* root)//得到子树的高度
{
if (root == nullptr)
{
return 0;
}
int left = _getHeight(root->_left);
int right = _getHeight(root->_right);
return 1 + (left > right ? left : right);
}
bool _checkAVL(Node* root)//检测的子函数
{
if (root == nullptr)
return true;
int left = _getHeight(root->_left);
int right = _getHeight(root->_right);
int diff = right - left;
if (abs(diff) >= 2)
return false;
if (diff != root->_bf)
return false;
return _checkAVL(root->_left) && _checkAVL(root->_right);
}节点个数
递归累加即可
int Size()
{
return _size(this->root);
}
int _size(Node* root)
{
if (root == nullptr)
return 0;
return 1 + _size(root->_left) + _size(root->_right);
}
中序遍历
遍历的逻辑和平衡搜索二叉树一致，递归遍历即可。我们这里实现一个中序是可以得到有序的序列
void inoder()
{
_inoder(root);
}
void _inoder(Node* root)
{
if (root == nullptr)
return;
_inoder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_inoder(root->_right);
return;
}删除
删除我们就不介绍了。逻辑上就是替换删除再更新。找到需要删除元素的位置，再寻找该元素构成子树的最左节点或者左右节点，替换。我们以最左节点举例，替换之后，删除最左节点。然后和插入类似向根结点不断更新平衡因子和旋转，直至整棵树平衡。当然了，这里更新的逻辑可能和插入不同，但旋转的代码时可以复用的，这里就不再展开了
结语
以上便是今天的全部内容。如果有帮助到你，请给我一个免费的赞。
因为这对我很重要。
编程世界的小比特，希望与大家一起无限进步。
感谢阅读！