AVL树是啥
一提到AVL树，脑子里不是旋了，就是悬了。
AVL树之所以难，并不是因为结构难以理解，而是因为他的旋转。
AVL树定义
- 平衡因子：对于一颗二叉树，某节点的左右子树高度之差，就是该节点的平衡因子
- AVL树：对于一颗二叉树，任意节点的平衡因子
bf在范围[-1，1]之间（即左右子树高度差的绝对值<=1），则该树就是平衡二叉树
为何会有AVL树
AVL树是二叉搜索树的衍生，其名字来源是根据两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis，他们在1962年发明的一种用来解决二叉搜索树在极端情况下时间复杂度变为O(n)的情况。而其解决该情况的方法便是：通过旋转旋转来调整二叉搜索树的平衡
AVL树的节点
AVL树的节点实现方式有很多，这里采取下面的方法定义节点：
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data)
: _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_bf(0)
{}
AVLTreeNode<T>* _left; // 该节点的左孩子
AVLTreeNode<T>* _right; // 该节点的右孩子
AVLTreeNode<T>* _parent;// 该节点的父亲
T _data;//存储数据
int _bf;//平衡因子
};
这里AVL树节点的实现增加了_bf （平衡因子）成员变量，用来记录每个点的平衡因子。同时用了父节点的指针_parent ，目的是方便调整平衡因子。
AVL树的插入
这里AVL树的插入操作与二叉搜索树一样，唯一不同的是，在插入后要调整平衡因子
- 对于插入的节点，因为其是插入到叶节点位置，所以他的平衡因子为0
- 将节点插入后，树的高度可能会发生改变，此时则要调整他父亲，甚至还要调整父亲的父亲的平衡因子。主要分为以下几种情况
情况1：
如果在节点的右孩子插入，则该节点的
bf需要+1（节点70、50的bf连锁着发生了变化，后面有说明）
情况2：
如果在节点的左孩子插入，则该节点的
bf需要-1（节点70、50的bf连锁着发生了变化，后面有说明）但是没完！
如果节点的平衡因子因为插入而变成了
1或者-1，则说明子树的高度发生了变化，此时该节点的父节点的bf也应发生变化（如果父节点的bf更改之后影响了“爷爷节点”，则爷爷节点也要跟着跟着变化）。所以上图中的70和50两节点的bf也要发生变化。
但是还没完！
bf的值有可能会变为2、-2，则此时就需要进行旋转操作（旋转完成后，会手动调整bf，保证其符合要求）
代码：
//插入操作
...
//调整平衡因子
cur = newnode;
parent = newnode->_parent;
while (parent)
{
if (parent->_right == cur)
{
++parent->_bf;
}
else if (parent->_left == cur)
{
--parent->_bf;
}
if (parent->_bf == 0)//AVL树稳定了，break出去
break;
else if (parent->_bf == 1 || parent->_bf == -1)//无需旋转但是需要更改父亲的平衡因子
{
cur = parent;
parent = parent->_parent;
}
else if ()//需要旋转
{
}
}
AVL树的旋转
重中之重，也是难中之难
AVL树旋转的目的
AVL树是一个平衡二叉搜索树，因为某些插入操作导致它不再平衡（具体表现是平衡因子变为2或-2），则此时为了使之平衡，就需要进行旋转操作
AVL树旋转操作
AVL树的旋转主要分为4种情况：
- 左旋
- 右旋
- 左旋再右旋（双旋）
- 右旋再左旋（双旋）
情况1：左旋
对于插入后父亲的
bf=2，右孩子的bf=1的情况，采用左旋。且左旋后平衡因子都是0
情况2：右旋
对于插入后父亲的
bf=-2，左孩子的bf=-1的情况，采用右旋。且右旋后平衡因子都是0
双旋
这种情况的发生是因为发现对该节点无论左旋还是右旋，都无法使其平衡，原因是插入节点的位置比较特殊
情况3：左旋再右旋
对于插入（这里插入b还是c只会影响旋转完后的平衡因子）后父亲的
bf=-2，左孩子的bf=1的情况，采用左旋再右旋。这里的平衡因子更新规则与前不同，详见后文。
情况4：先右旋再左旋
对于插入（这里插入b还是c只会影响旋转完后的平衡因子）后父亲的
bf=2，右孩子的bf=-1的情况，采用右旋再左旋。这里的平衡因子更新规则与前不同，详见后文。
双旋的平衡因子更新规则
更新规则相比旋转规则就简单许多
分为以下3种情况（以上图为例）：
- 如果60的平衡因子（旋转前）是-1，则更新后的60的平衡因子变为0，左孩子变为0，右孩子变为1
- 如果60的平衡因子（旋转前）是1，则更新后60的平衡因子变为0，左孩子变为-1，右孩子变为0
- 如果60的平衡因子（旋转前）是0，则更新后60的平衡因子变为0，左孩子变为0，右孩子变为0
代码：
这里只给出一部分代码，剩下的可以自己尝试写出来，然后可以到仓库对照
bool insert(const pair<K,V>& kv)
{
//插入
Node* newnode = new Node(kv);
if (newnode == nullptr) return false;
if (_root == nullptr)
{
_root = newnode;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (kv.first > cur->_kv.first)
{
cur = cur->_right;
}
else cur = cur->_left;
}
//调整节点连接
if (kv.first > parent->_kv.first)
parent->_right = newnode;
else
parent->_left = newnode;
newnode->_parent = parent;
//调整平衡因子
cur = newnode;
parent = newnode->_parent;
while (parent)
{
if (parent->_right == cur)
{
++parent->_bf;
}
else if (parent->_left == cur)
{
--parent->_bf;
}
if (parent->_bf == 0)//AVL树稳定了，break出去
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);
}
else
{
assert(false);
}
}
}
return true;
}
//左旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
if (!pparent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
parent->_bf = 0;
subR->_bf = 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)
{
subLR->_bf = 0;
parent->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
subLR->_bf = 0;
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
subLR->_bf = 0;
parent->_bf = 1;
subL->_bf = 0;
}
else
{
assert(false);
}
}
