一、什么是AVL树
1、AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间复杂度O(log_2 n)。
2. 平衡因子
平衡因子为结点左右子树的高度差，本文假设平衡因子（bf）=右子树高度-左子树高度
在AVL树中每个结点的平衡因子都是大于等于-1，小于等于1的
二、AVL树的实现
1.AVL树结点结构
template<class K, class V>
struct AVLTreeNode
{
struct AVLTreeNode* _left;
struct AVLTreeNode* _right;
struct AVLTreeNode* _parent; //_parent是为了后续旋转调整方便
pair<K, V> _kv;//结点数据
int _bf; //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0)
{}
};2.AVL树的插入
插入流程：
1. 先将结点按二叉搜索树的规则‘’插入AVL树
2. 更新插入结点祖先的平衡因子
a.如果插入到父亲结点的左边，平衡因子- -
b.如果插入到父亲结点的右边，平衡因子++
c.如果父亲的平衡因子==0，说明父亲结点原来的平衡因子一定为1或-1，插入后父亲结点达 到平衡，没有改变高度，插入成功，不需要向上改变祖先的平衡因子
d.如果父亲的平衡因子为1或-1，说明父亲结点原来的平衡因子一定为0，插入结点后改变了 树的高度，此时需要向上调整祖先结点的平衡因子
e.如果父亲的平衡因子为2或-2，说明此时不平衡了，需要旋转调整
三、AVL树的旋转
1. 新节点插入较高左子树的左侧---左左：右单旋
if (parent->_bf == -2 && cur->_bf == -1)
//纯粹的左边高
// *
// *
// *
让parent的左指向subLR，如果subLR不为空，更新subLR的父亲结点,让subL的右指向parent，并更新parent与subL的父亲结点，注意parrent结点可能是根节点也可能是一个子树结点，更新subL的父亲节点需要分类讨论。旋转完后，树达到平衡，将parent和subL的平衡因子置为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;
}
parent->_bf = SubL->_bf = 0;
}
2. 新节点插入较高右子树的右侧---右右：左单旋
if (parent->_bf == 2 && cur->_bf == 1)
//纯粹的右边高
// *
// *
// *
与右单旋相类似，让parent的右指向subRL，如果subRL不为空更新subRL的父亲节点，让subR的左指向parent，并更新parent和sunR的父亲节点
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
parent->_right = SubRL;
if (SubRL)
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)
{
ppNode->_left = SubR;
}
else
{
ppNode->_right = SubR;
}
SubR->_parent = ppNode;
}
parent->_bf = SubR->_bf = 0;
}3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
if (parent->_bf == -2 && cur->_bf == 1)
//parent结点的左树高，而cur结点的右树高
// *
// *
// *
先以subL为父亲结点进行左单旋，变为纯粹的左边高，再以parent为父亲结点进行右单旋调整，最后调整结点的平衡因子
平衡因子处理分析：
这种情况只有将结点插入到b树或c树后面才会进行左右旋，而左右旋只改变了parent、subL、subLR结点的左右子树，左旋是将b树给了subL结点，右旋是将c树给了parent结点，subLR作为处理树的根结点，故subLR的平衡因子最终为0，所以parent与subL结点平衡因子的关键就是插入结点插入到了b树下还是c树下
- 如果插入到b树下：subL结点左右子树高度相同，bf=0，parent结点的右子树比左子树高1，bf=1
- 如果插入到c树下：parent结点左右子树高度相同，bf=0，subL结点的左子树比右子树高1，bf=-1
void RotateLR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
int bf = SubLR->_bf;
RotateL(SubL);
RotateR(parent);
if (bf == -1)
{
SubL->_bf = 0;
SubLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
SubL->_bf = -1;
SubLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 0)
{
SubL->_bf = 0;
SubLR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
if (parent->_bf == 2 && cur->_bf == -1)
//parent结点的右树高，而cur结点的左树高
// *
// *
// *
先以subR为父亲结点进行右单旋，变为纯粹的右边高，再以parent为父亲结点进行左单旋调整，最后调整结点的平衡因子
- 如果插入到c树下：subR结点左右子树高度相同，bf=0，parent结点的左子树比右子树高1，bf=-1
- 如果插入到b树下：parent结点左右子树高度相同，bf=0，subR结点的右子树比左子树高1，bf=-1
void RotateRL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
int bf = SubRL->_bf;
RotateR(SubR);
RotateL(parent);
if (bf == -1)
{
SubR->_bf = 1;
SubRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
SubR->_bf = 0;
SubRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
SubR->_bf = 0;
SubRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}AVL树插入代码：
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 (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
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)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0) // 1 -1 -> 0
{
//更新结束
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 0 -> 1 -1
{
// 继续往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 1 -1 -> 2 -2
{
// 当前子树出问题了，需要旋转平衡一下
if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
break;
}
else
{
// 理论而言不可能出现这个情况
assert(false);
}
}
return true;
}五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
- 每个节点子树高度差的绝对值不超过1
- 节点的平衡因子是否计算正确
bool _Is_Balance(Node* root)
{
if (root == nullptr)
{
return true;
}
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
if (abs(LeftHeight - RightHeight >1))
{
cout<<"1:" << root->_kv.first << endl;
return false;
}
if (RightHeight - LeftHeight != root->_bf)
{
cout <<"2:" << root->_kv.first << endl;
cout << root->_parent->_kv.first << endl;
cout << root->_bf << endl;
return false;
}
return _Is_Balance(root->_left) && _Is_Balance(root->_right);
}六、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
