AVL树
1.介绍
AVL树是对搜索二叉树的改进，通过特定的方法使得每个节点的左右子树高度差绝对值不超过1，使得避免出现歪脖子的情况，最核心的实现在于插入值部分是如何去实现平衡调整的，由于前面详细实现和解析过搜索二叉树，因此本篇文章着重整理AVL树核心的部分，插入的实现，以及旋转是如何操作的
2.基本框架
先搭建一个搜索二叉树的基本框架
节点定义部分
平衡因子的概念：
一个节点的平衡因子指的是左右子树的高度差，根据自己定义，可以是左边高度减右边高度，或者是右边高度减左边高度，在AVL树中，调节平衡因子是实现平衡的关键
ps：本篇对平衡因子_bf的定义都是右边减左边
AVL树的框架
3.核心部分
基本框架
插入部分重点还是在于平衡因子的调整部分，前面就不详细分析了
平衡因子的调整
每次插入要保持每个节点的平衡因子绝对值都小于1，则说明整棵树是符合AVL树的规则的，即每个节点的左右子树高度差的绝对值不超过1。
因此，再每次插入一个新的节点时，要考虑每个节点之间平衡因子的变化，通过画图观察发现，当一个新节点插入后，有可能受影响的是其部分或者全部祖先
通过画图观察总结出更新的规律，新增节点后，当新增节点在其父母节点的左边则对父母节点的bf进行--，在右边则进行++（这是因为我们定义bf采用右边减左边），当父母节点bf改变后，如果绝对值为1，那么需要继续向上调整，调整的规则也是，看该节点在其父母节点的左边还是右边，左边则--，右边则++，直到遇到每次调整parent时，parent的bf变为0，则说明不需要调整了，并且插入成功，又或者调整parent时，其bf绝对值等于2，则说明需要对该部分子树进行旋转调整了（降高度）
旋转调整
旋转又分成四种方式，分别是左单旋、右单旋、左右双旋、右左双旋
1.单旋
左单旋，当遇到这种最右边高左边低的时候，采用左单旋，将60位置的左子树给30位置，再由60去取代30原先的位置，形象点看就是，好像吧一个旋钮往左旋转了一样
右单旋，同理就是与左单旋的情况相反，最左边高，右边低，将30的b给60,30取代60的位置
代码实现
从画图上来看，这就是左单旋和右单旋，看似简单，但在转化成代码的时候，要注意几个问题：
1.要注意每个节点的parent指针需要被维护
2.一开始我们就对需要用到的位置，用指针去一 一对应的话，要注意中间的那个b是有可能为空的
3.最上面的位置不一定就是根节点，因此在更换掉最上面位置节点的时候，要考虑对其上面是否还有节点进行判断，如果还有节点，则进行进一步链接，为根节点则需要将其parent置空
右单旋同理，需要注意的细节和左旋是一样的，这里给出左单旋和右单旋的代码参考
左单旋代码参考：
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
if (pparent)
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
else
{
_root = subR;
_root->_parent = nullptr;
}
parent->_bf = subR->_bf = 0;
}右单旋代码参考：
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
if (pparent)
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
else
{
_root = subL;
_root->_parent = nullptr;
}
parent->_bf = subL->_bf = 0;
}2.双旋
双旋是为了解决子树往中间偏的问题，当子树往中间偏高时，可以先将其往一边掰直，转换成上面两种情况之一，然后再调整，因为需要两次单旋操作，所以叫双旋
左右双旋，对30位置进行左旋，然后再对90位置进行右旋，从结果来看就是，将60最终放到最上面，60的左子树给左边的30,60的右子树给了右边90
右左双旋同理
双旋的代码实现：
双旋的难点不是在于实现双旋操作本身，因为只需要复用左单旋和右单旋就可以了，真正的难点在于对平衡因子的更新，与单旋不同，双旋对平衡因子的更新并不是直接将调整位置的值都变成0，而是需要根据实际情况去分类讨论的
拿左右双旋举例
左右双旋代码分析
代码参考：
左右双旋：
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int subLR_bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (subLR_bf == -1)//在b下新增节点
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (subLR_bf == 1)//在c下新增节点
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (subLR_bf == 0)//subRL就是新增节点
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}右左双旋：
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}3.根据不同情况选择不同旋转方式
以上，就是AVL树的核心实现，最重要的就是控制平衡，通过旋转调整平衡的方式，保证了每个节点的左右子树绝对值不超过1，实现平衡，大大加快了搜索二叉树的效率，搜索效率能够达到
O(logN）
4.测试接口
中序遍历
中序遍历有序只能保证树是二叉搜索树，但不能保证平衡
void _InOrder()
{
InOrder(_root);
cout << endl;
}
void InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
InOrder(root->_left);
cout << root->_value.first << " ";
InOrder(root->_right);
}验证平衡因子是否绝对值不超过1
这里提供一个IsBalanceTree接口验证是否平衡因子绝对值不超过1
int _Height()
{
return Height(_root);
}
int Height(const Node* root)
{
if (root == nullptr)
return 0;
int left = Height(root->_left) + 1;
int right = Height(root->_right) + 1;
return left > right ? left:right;
}
bool _IsBalanceTree()
{
return IsBalanceTree(_root);
}
bool IsBalanceTree(Node* root)
{
// 空树也是AVL树
if (nullptr == root)
return true;
// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
// pRoot平衡因子的绝对值超过1，则一定不是AVL树
if (diff != root->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return IsBalanceTree(root->_left) && IsBalanceTree(root -> _right);
}随机值插入验证测试
bool test()
{
//16, 3, 7, 11, 9, 26, 18, 14, 15
//4, 2, 6, 1, 3, 5, 15, 7, 16, 14
srand(time(0));
const size_t N = 1000;
AVLTree<int, int> n;
for (int i = 0; i < N; i++)
{
size_t x = rand()%100;
n.Insert(make_pair(x, x));
}
n._InOrder();
return n._IsBalanceTree();
}总结
本篇内容整理总结了AVL树的核心实现，分析了其中的内部原理，对原理以及实现都画图进行了分析，提供了源码参考
