1 AVL树介绍
1.1 问题引入
之前我们学习了二叉搜索树，但是其中，我们发现了一些问题。 比如：搜索树是单支的，那就和链表差不多了。因为高度太高了，效率就降低成了o(n)。
所以要尽量控制平衡。
1.2 引入AVL树的概念
俩位俄罗斯的数学家在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1（需要对树中的节点进行调整），即可降低树的高度，从而减少平均搜索长度。
总结：
1）任何树及其子树都需要满足条件：左右子树的高度差(平衡因子 = 右子树高度- 左子树高度)的绝对值不超过1(-1,0,1)；
2）平衡因子只是一种控制方式，帮助我们更便捷的控制树。
一颗正确的平衡二叉树如下图所示：
比如下面的图中就不满足平衡二叉树的条件。
1.2.1 问题1
为什么是高度差不超过1，而不是高度差为0呢？高度差为0不是更加平衡吗？
解答：因为假设只有2个节点进行插入，或者4个节点进行插入，此时的高度差就不会保持0.所以最优高度差就为1。
2 AVL树模拟实现
2.1 平衡二叉树节点构造
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;
};2.2 平衡二叉树构造
2.2.1 Insert
与二叉搜索树不同的是，多了一个和parent的链接。此处的parent的链接是与影响因子的更新相关的(下面的点会体现)。
bool Insert(const pair<K, V> kv)
{
//如果为空，则首先进行插入
//如果不为空，则要检查该树中是否有该key，如果没有则进行插入,如果有则进行return false;
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//如果不为空，值大的往右走，小的往左走
Node* cur = _root;
Node* parent = nullptr;
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 (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//最坏的情况是检查到根,如果没有问题，那就没有问题了,即_root == parent;parent == nullptr;的情况
while (parent)
{
//更新规则
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//第一种情况,平衡更新
if (parent->_bf == 0)
{
break;//更新结束
}
//第二种情况，更新后高度变化，但是存在平衡更新和不平衡更新的情况
else if(parent->_bf == 1 || parent->_bf == -1)
{
//向上走
cur = cur->_parent;
parent = parent->_parent;//在循环使用最开始的更新规则
}
//第三种情况，更新后高度变化，但是不平衡更新的
else if (parent->_bf == 2 || parent->_bf == -2)
{
//需要旋转处理
//左单旋
if (parent->_bf == 2 && cur->_bf == 1)
{
RotalL(parent);
}
//右单旋
else if (parent->_bf == -2 && cur->_bf == -1 )
{
RotalR(parent);
}
//LR双旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotalLR(parent);
}
//RL双旋
else
{
RotalRL(parent);
}
break;
}
else
{
//如果出现平衡因子不在上面范围内的,比如3或者-3等，则说明AVL树插入前就有问题
assert(false);
}
}
return true;
}2.2.2 平衡因子的更新
平衡因子的形成过程：
1）按二叉搜索树规则进行插入，但是会增加一个_parent的链接。
2）更新平衡因子：
①AVL树不一定有平衡因子，但是平衡因子是我们进行观察这棵树是否是AVL树的关键；
②插入结点会影响哪些结点的平衡因子？ 新增节点的部分祖先；
③更新原则: c是p的左边，p->bf--; c是p的右边,p->bf++。
④是否要继续更新取决于p的高度是否变化，是否会影响爷爷节点。
1.更新后，p->_bf == 0,p所在的子树的高度不变，不会影响爷爷节点。
--》那说明更新前，p节点的平衡因子是-1或者1。之后，p节点矮的那一边插入了新的节点，是左右得到了平衡, p节点的高度没有变化，所以不会影响爷爷节点。
--》更新结束。
2.更新后，p->_bf==1或者-1,p所在的子树高度变了，所以会影响爷爷节点 。
--》那说明更新前,p节点的影响因子是0，p的有一边进行了插入,p节点左右变的不均衡，但是还是在不超过1的绝对值范围内，但是p 的高度变了，会影响爷爷节点。
--》此时需要向上更新。
此时如何向上更新？
此时_parent的作用就体现出来了。
更新的过程再根据之前的更新原则继续更新。
那此时是否还需要再向上更新呢？
不需要，因为现在的节点的平衡因子从原来的1变成了0，使其更加平衡了。
3.不平衡的情况
更新后,p->_bf==2/-2,说明p节点所在的子树违反了平衡规则，需要进行处理-->旋转。
总结：
需要二叉搜索树的规则进行插入+平衡因子更新。
2.2.3 旋转
现在需要处理的就是当前树不平衡时，如何将其变成平衡，此时就需要对当前树进行旋转，使之平衡。 进行旋转之后，parent的平衡因子变为0，此时就变得平衡，无需再向上更新。
所以此时我们可以进行一下总结(什么时候更新结束):
1.更新后，p->_bf == 0,p所在的子树的高度不变。
2.更新到root节点，parent==nullptr时。
3.旋转之后，parent所在子树高度回到了插入之前，不会对上层平衡因子产生影响。
旋转的目的：
①保持搜索规则 ；
②当前树从不平衡转为平衡 ；
③降低当前树的高度。
根据节点位置的不同，AVL树的旋转分为四种:
1） 左单旋
右子树的右分支导致的不平衡，所以也可以叫RR。
①抽象图中，b变成30的右边。
②30变成60的左边。
③60变成当前树的根。
代码实现：
void RotalL(Node* parent)
{
//定义阶段
Node* subR = parent->_right;
Node* subRL = subR->_left;
//更改阶段
parent->_right = subRL;
if (subRL)//子树可能是空
{
subRL->_parent = parent;
}
//先记录parent的父结点,因为parent可能是一个子树，也可能是一个根
Node* ppnode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
//如果是根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else//parent不是根，那么parent可能是父结点的左节点还是右结点
{
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
} 所以什么时候会进行左单旋？
如上图中所示: parent->bf == 2 && cur->bf == 1。
2）右单旋
由于左子树的左分支的增加导致的不平衡，也可以叫做LL。
void RotalR(Node* parent)
{
//1.定义节点
//2.更改阶段
//3.注意子树可能为空
//4.parent是否为根
//5.更新平衡因子
Node* subL = parent->_left;
Node* subLR = subL->_right;
//更改阶段
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}所以什么时候会进行右单旋？
如上图中所示: parent->bf == -2 && cur->bf == -1 。
3）左右旋
左子树的有分支导致的不平衡，也可以叫做LR。
之前我们学习了单旋中的左单旋和右单旋，这些方法可以解决一些问题，但是下面的情况则不能单纯使用左单旋和右单旋来解决。
下面我们将使用具象图来分析一下不同高度下所造成的不平衡的情况：
下面我们通过抽象图分析不平衡之后是如何进行旋转使树平衡的：
b新增的情况
2. c新增的情况
3. 容易忽略的情况
双旋会将平衡因子进行修改。
对于平衡因子的更新，关键点在于如何区分这三种情况:
而进行LR双旋的标志是parent->bf == -2 && cur->bf == 1。
插入值之后，SubLR分别是-1,1,0。
这个就是区分三种的情况的关键。
void RotalLR(Node* parent)
{
//首先记录之前的平衡因子
Node* subL = parent->_left;
Node* subLR = subL->_right;
//插入时平衡因子改变了,但是区别在于三种情况的subLR不同
//所以记录旋转之前的subLR
int bf = subLR->_bf;
//进行旋转
RotalL(parent->_left);//以30为旋转点进行旋转
RotalR(parent);//以90为旋转点进行旋转
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}4）右左旋
右子树的左分支导致的不平衡，也可以叫做RL。
①c插入，引发的旋转
②b插入引发的旋转：
③容易忽略的情况
与LR相同的是如何使树变得平衡也分为三种情况：
1.如果h > 0,c插入，c的高度会变为h,引发旋转；
2.如果h > 0,b插入,b的高度会变为h,引发旋转；
3.如果h == 0，60为新增，引发旋转。
void RotalRL(Node* parent)
{
//1.记录节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
//2.记录subRL的平衡因子，这就是三种情况的区别
int bf = subRL->_bf;
//3.先进行右旋转，再左旋转
RotalR(subR);
RotalL(parent);
//4.三种不同平衡因子，在旋转到最后结果后，所得到的节点平衡因子更新情况
if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}此时，插入的整个环节已经进行完成，那么我们就可以通过中序将其遍历，检查其是否是一个平衡二叉树。
void _Inorder()
{
Inorder(_root);
}
void Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
else
{
Inorder(root->_left);
cout << root->_kv.first << " ";
Inorder(root->_right);
}
}
但是，这样真的能够知道这个二叉树是一个平衡二叉树吗？
不能，所以我们要使用一段能判断二叉树平衡的代码。
首先，我们需要计算树的高度。
2.2.4 计算树的高度
//用来计算树的高度
int TreeHeight(Node* root)
{
if (root == nullptr)
{
return 0;
}
//计算左子树和右子树的高度
int LeftHeight = TreeHeight(root->_left);
int RightHeight = TreeHeight(root->_right);
//若当前节点的左子树高，则左子树+1(当前层)
return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
其次再判断该二叉树的子树是否保持平衡。
1）如果|右子树高度-左子树高度| >= 2，那说明该树是不平衡的。
2）如果右子树高度-左子树高度的平衡因子与之前计算的平衡因子不相等，则说明计算异常。
3）要求根节点的左子树和右子树都满足上面的要求。
int IsBalance(Node* root)
{
//如果该子树为空,那么也是一个平衡二叉树
if (root == nullptr)
{
return true;
}
int LeftHeight = TreeHeight(root->_left);
int RightHeight = TreeHeight(root->_right);
//1.如果|右子树高度-左子树高度| >= 2，那说明该树是不平衡的
if (abs(RightHeight-LeftHeight)>=2)
{
//哪一个子树节点不平衡
cout << root->_kv.first << "不平衡" << endl;
return false;
}
//2.如果右子树高度-左子树高度计算的平衡因子与之前计算的平衡因子不相等，则说明计算异常。
if (RightHeight-LeftHeight != root->_bf)
{
//哪一个子树节点的平衡因子不相等
cout << root->_kv.first <<"[" << root->_bf << "]" <<"出现异常" << endl;
return false;
}
return IsBalance(root->_left) && IsBalance(root->_right);
}
int _IsBalance()
{
return IsBalance(_root);
}
但是上面的代码在进行求高度上，重复性过高，所以我们可以进行后序来进行减少高度的重复计算：
int _IsBalance2()
{
int a = 0;
return IsBalance2(_root,a);
}
bool IsBalance2(Node* root, int& height)
{
if (root == nullptr)
{
height = 0;
return true;
}
//左右若有一个不平衡，则返回false,这里的函数会返回高度
int Leftheight = 0;
int Rightheight = 0;
if ( !IsBalance2(root->_left,Leftheight) || !IsBalance2(root->_right,Rightheight))
{
return false;
}
if (abs(Rightheight - Leftheight) >= 2)
{
//哪一个子树节点不平衡
cout << root->_kv.first << "不平衡" << endl;
return false;
}
//2.如果右子树高度-左子树高度计算的平衡因子与之前计算的平衡因子不相等，则说明计算异常。
if (Rightheight - Leftheight != root->_bf)
{
//哪一个子树节点的平衡因子不相等
cout << root->_kv.first << "[" << root->_bf << "]" << "出现异常" << endl;
return false;
}
//更新高度
height = Leftheight > Rightheight ? Leftheight + 1 : Rightheight + 1;
return true;
}
在AVL树学习部分，对于找bug是比较困难的，所以我们可以对其有一个初步的步骤去进行调试，找出问题所在：
1.先看是插入哪一个值所导致的问题；
2.打断点，画出插入该值前的图；
3.单步跟踪，对比图进行一一分析。