AVL的产生
二叉搜索树在一定程度上可以提高搜索效率，但是当序列是有序时：如果所示
此时二叉搜索树退化成单链表，搜索效率退化为O（N)。为了解决这个问题科学家引入了AVL树，又称平衡搜索二叉树。
AVL树的概念
AVL简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值。它具有如下几个性质：
可以是空树。
假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝值不超过 1。
AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）。
现在尝试判断一下，下面那个树不是平衡二叉树
图一：
图二：
图三：
在平衡二叉树的基础上添加上二叉搜索树的性质就成为了AVL树，
即：左子树全部小于根，右子树全部大于根。
AVL树的节点定义
我们这里直接实现KV模型的AVL树。
AVL树与二叉搜索树与众不同之处就是多了旋转这一步骤，然而为了方便后序的旋转操作，将AVL树的结点定义为三叉链结构，（还存在平衡因子，后面解释作用与存在原因）
template<class k, class v>
struct AVLTreeNode
{
//三叉链
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
//平衡因子
int _bf;
pair<k, v> _kv;
AVLTreeNode(const pair<k, v>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
AVL树的插入
AVL树的插入也是最为麻烦的，就比如说一个AVL树在插入前符合要求，然而插入后破坏了平衡，但如果我们知道这时会破坏平衡还好，但是坏就坏在不知道，在插入前不知道是左子树深度高还是右子树深度高，这就是麻烦之处。
然而，前面已经提到了AVL树是一种特别的平衡二叉树，平衡二叉树里面就有个概念就是：平衡因子，解决了这一问题。
平衡因子
定义
某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1或小于-1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。
有了平衡因子这一说，那么在插入前我都知道是左子树深度高还是右子树深度高了，又因为AVL树又有二叉搜索树的性质，所以我在插入前就可以知道其要被插入的位置，所以说对于插入还是有了一点思路，知道了什么时候会失衡，失衡的大致情况是什么。
此时平衡就会被打破，那么如果想要调节，从而达到平衡，那么就要想办法使其左子树的深度减少，
对于此又会引入另一个新的概念：
最小失衡树
在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1或小于-1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。
AVL树种解决失衡问题通过旋转最小失衡树来使整棵树达到平衡，旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。
对于此类的调节方法共可以分为四种旋转情况
插入的四种旋转方式
单旋
右旋
当插入0后，就会破坏破坏
此时树的平衡性被破坏此时从插入节点往上查到最小失衡树为3，3这个节点不平衡原因是它的左树的高度太高，因此我们只需要对3这个节点进行右旋。
下面的操作用抽象图代替
大致操作为如下：
在一个AVL树种插入一个值在a子树，从而使得平衡被破坏，使得60变为最小失衡树的根节点，我们令60为parent（下面为了简便用P代替）60的左子树为subPL（下面为了简便代替为PL），PL的右子树为subPLR（PLR）。
然后进行如图的操作。
图中的操作共可以分为3步走：
将b变为60的左
60变为30的右
30为新的根
代码如下：
void RotateR(Node parent)
{
Node subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* parent_parent = parent->_parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent)
{
parent_parent->_left = subL;
}
else
{
parent_parent->_right = subL;
}
subL->_parent = parent_parent;
}
parent->_bf = subL->_bf = 0;
}
左旋
同样我们用抽象图代替，在c子树下插入，从而破坏平衡，令30为P，30的右为PR，PR的左子树为PRL，大致操作可以分为3步骤：
b变为30的右
30变为60的左
60为新根
代码如下：
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
if (subRL)
{
subRL->_parent = parent;
}
Node* parent_parent = parent->_parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent)
{
parent_parent->_left = subR;
}
else
{
parent_parent->_right = subR;
}
subR->_parent = parent_parent;
}
subR->_bf = parent->_bf = 0;
}
双旋
在单旋我们的插入都是在图一的a（进行右旋），或者在图二的c（进行左旋）进行插入后破坏平衡，然后进行单旋从而恢复平衡，他的插入可以说是直线的插入，因此经过一次旋转就可以使其达到平衡。但是如果是折线过来又改怎么旋转呢。这时候就要用双旋了。
就比如说在图一的b插入（进行左右双旋），在图二的b插入（进行右左双旋）。
右左双旋
右左双旋就是在如图的b上插入节点
但是这个插入又分为两种，是在b的左子树与b的右子树部分插入，也就是分为在b1上插入，或在b2上插入，但实际上写代码的时候是不需要这样考虑的，写代码的时候还是一种情况，这里分两种情况是为了方便讲解详细操作步骤，从而使得过程更为好理解。
双旋重要的是要回更新平衡因子，两次的旋转还是很好解决的，下面我们以情况一来假设模拟一下。在双旋中，我们只需要先对PR进行右单旋，后对P进行左单旋便可以。总的来说还是很简单。
对于平衡因子的调整，我们就需要分情况了，这时候分为三种情况
subRL自己就是新增
插入的节点在b1上
插入的节点在b2上
这三种情况来说还是很好解决的
对于第一种就不多说了只需要将P，PR，PRL的平衡因子全等于0即可。
我们把图给出，对于此时
PRL的平衡因子为0，
P的为0
PR为1
我们把图给出，对于此时
PRL的平衡因子为0，
P的为-1
PR为0
最后代码展示：
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//调整平衡因子
if (bf == 0)
{
// subRL自己就是新增
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
//在b上增加
parent->_bf = 0;
subRL -> _bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
subR->_bf = subRL->_bf = 0;
parent->_bf = -1;
}
else
{
assert(false);
}
}
左右双旋
同样左右双旋也是要分两种情况来定，最后调整平衡因子，这一部分代码，就留给你来写了，就不在一步一步来说明了
直接给出代码：
void RotateLR(Node parent)
{
Node subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
//调整平衡因子
if (bf == 0)
{
// subLR自己就是新增
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false);
}
}
还有图解：
先对30左旋，后对40右旋。
旋转方式的选择
四种的旋转方式说完了，那么我们就要写代码，判断什么时候要进行那种旋转了，总的来说还是靠平衡因子来选择的。
注意：
插入后的调整要寻找最小失衡树！！！，而不是说插入后的那一小部分树来进行调整。
bool Insert(const pair& 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->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
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)
{
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)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
// 1、旋转让这颗子树平衡了
// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，
// 所以对上一层没有影响，不用继续更新
break;
}
else
{
break;
}
}
return true;
}
AVL树的删除
AVL的删除是比插入多了平衡调整，比较麻烦，真正实现起来要200-300行的代码，总的来说是插入的代码量的二倍左右，我也不会，这就不多说什么了，但推荐一个文章，里面就有删除：
【数据结构】AVL树的删除（解析有点东西哦）_avl树删除节点-CSDN博客
其余函数
find与中序遍历打印
总的来说AVL树到此就结束了，剩下的就是find函数与中序遍历函数，这两个函数与二叉搜索树的实现完完全全相同
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
Node* findLastIndex(K key)
{
Node* pre = _root;//记录前一个节点
Node* cur = _root;
while (cur) {
pre = cur;
if (cur->_kv.first == key) {
break;
}
else if (cur->_kv.first > key) {
cur = cur->_left;
}
else {
cur = cur->_right;
}
}
return pre;
}
检测是否为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 _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
到这就完了，拜拜
