完整教程：AVL树（平衡二叉搜索树）

AVL树的简介

二叉搜索树在二叉树的基础上增加了一个规则：任何一颗子树的根的左边所有节点的值都小于根，根右边的所有节点的值都大于根。这个规则使其查找的时间复杂度大大减小，但是仍然有一些漏洞：如果根节点的值是最大或者最小的，那么所有节点都会堆在一边，搜索的效率会从O(logN)增加到O(N)。

基于这一点，有大佬给出了一种平衡搜索树——AVL树。

控制平衡的方式

AVL树基于二叉搜索树增加了一条新的规则：每个根左右子树的高度差都小于等于1。这使得这棵树十分接近完全二叉树，搜索的效率大致接近O(logN)。

控制高度差的方法有很多，这里我们只说明一种方法：在树的每个节点中加入一个平衡因子（Balance Factor），它的值我们定义为右树的高度减去左树的高度。

template
struct avlTreeNode
{
pair _kv;
avlTreeNode* _left;
avlTreeNode* _right;
avlTreeNode* _parent;
int _bf;//balance factor
avlTreeNode(const pair& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_kv(kv)
{}
};

很明显我们这里使用了key-value的结构，存储key值和它的映射值。同时在节点中加入了一个指针_parent，使每个节点成为三叉链，能更简单快速的找到其父节点。

_bf的初始值给0，是因为新节点的左右子树一定都为空，所以右树高度减去左树高度一定为0。

AVL树的插入

基本规则

1. 按照二叉搜索树插入的规则先将新的值插入成为树的新叶子节点。
2. 更新平衡因子：每个节点只需要更新其祖先的平衡因子，根据平衡因子的定义，插入到左树则父节点的平衡因子减一，反之则加一。
3. 一直往上更新，有三种情况：①更新后某个祖先的平衡因子变为0，说明该棵子树的高度没变，不需要继续更新了。②更新后某个祖先的平衡因子变为-1或者1，说明子树高度变化，还需要继续更新。③更新后某个祖先的平衡因子变为-2或者2，说明该子树不平衡了，需要进行处理。

平衡因子变为2或者-2之后，我们就需要对这棵子树进行处理了，这种处理就是旋转，旋转有四种情况，分别是左单旋，右单旋，左右双旋和右左双旋。

单旋

判断是哪种单旋需要两个节点，一个是当前节点parent，和其的子节点subL或者subR。

右单旋

如图，在节点5的左子树上插入一个节点，subL的平衡因子会变为-1，而parent的平衡因子会变为-2，破坏了这棵树的平衡。这个时候就需要右单旋——把subL变成根节点，parent变成subL的左边，subL的右边给parent的左边。就完成了一个右单旋。

如图，右单旋完成后subL和parent的平衡因子都变成了0，所以对于单旋来说，进行完毕之后两个相关的节点subL和parent的平衡因子都会变成0。

单旋的过程看起来很简单，但是实际上在转换为代码时会有很多注意点。

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* pParent = parent->_parent;
//parent的左边变成sunL的右边
parent->_left = subL->_right;
//如果subL的右边不为空，就将其的父节点变为parent
if(subL->_right)
subL->_right->_parent = parent;
//subL的右边变成parent
subL->_right = parent;
//parent的父节点变为subL
parent->_parent = subL;
//subL的父节点变为parent原来的父节点
subL->_parent = pParent;
//如果parent不是根节点
if (pParent != nullptr)
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
//如果parent是根节点
else
_root = subL;
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}

我们上文提到的核心代码只有两句，其余都是各个节点的父子关系的链接，这里必须小心的控制好每一步，不然旋转就会失败。

左单旋

与右单旋几乎一摸一样，只是方向不同。给实现的代码。

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* pParent = parent->_parent;
parent->_right = subR->_left;
if (parent->_right)
parent->_right->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
parent->_parent = subR;
subR->_parent = pParent;
if (pParent != nullptr)
{
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
}
else
_root = subR;
subR->_bf = 0;
parent->_bf = 0;
}

双旋

如图当新的节点插入到subL的左边时，相当于高是一边高，我们可以通过一次右单旋将其调整为平衡的AVL树，但是还有另一种情况，就是新的节点插入到subL的右边，这时一次右单旋之后也不是平衡的。

如图subL的左子树高度为h，右子树高度为h+2，明显它不是平衡的。

这个时候就需要双旋了。

左右双旋

进行双旋是，就与上图的b子树中的节点有关系了，所以我们需要将b子树展开。

如图，新的节点插入在subLR的左边或者右边，影响的是之后parent节点和subL节点的平衡因子的更新，之后我们会介绍。

双旋其实就是进行两次单旋来得到子树的平衡。所谓的左右双旋就是先进行一次左单旋，再进行一次右单旋，最后更新一下平衡因子。

对应到上图：先对subL进行一次左单旋，使subLR变为左子树的根，之后对parent进行一次右单旋，使suBLR变为整棵树的根，最后就平衡了。

如图，这是上图新节点插入在subLR的左边的情况，对其进行两次单旋之后，会发现原来subLR的两个子树会分给subL的右边和parent的左边，这对其平衡因子的更新起到了至关作用。

下面直接给出结论：

• 在插入之后subLR的平衡因子如果变成-1，subL的平衡因子更新为0，parent的平衡因子更新为1。
• 在插入之后subLR的平衡因子如果变成1，subL的平衡因子更新为-1，parent的平衡因子更新为0。
• 在插入之后subLR的平衡因子如果变成0，subL的平衡因子更新为0，parent的平衡因子更新为0。

第三种情况比较特殊，如果subLR是新插入的节点，或者说a，b，c，3棵子树都为空，这几个节点的平衡因子就都更新为0。

下面是代码的实现。

void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
//
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else 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
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 == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
//parent->_bf = 1;
//subR->_bf = 0;
//subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
assert(false);
}