AVL树的插入函数
在二叉搜索树的插入函数基础上，AVL树的插入操作还需要对父节点的平衡因子进行调节，并在失衡的根节点处进行旋转调整。
AVL树插入流程：
- 如果是第一次插入节点，直接赋值给 _root 作为根节点，_size+1。
- 将插入值的key与当前节点值传入 _com函数 中对比，当函数返回true时向左子树走，返回false时向右子树走，如果走到空则跳出准备插入，如果相等则返回当前节点值。
- 根据节点值与插入值key在_com函数中的对比结果，决定插入到父节点的左子树还是右子树。
- 调整父节点的平衡因子，如果出现失衡（平衡因子绝对值为2）则进行旋转，并依次向上继续调整祖父节点，直到当前父节点平衡因子为0或节点为树的根节点为止。
- _size+1并返回插入结果。
关于AVL树的返回值：AVL树返回值为 pair<val_type,bool>，当插入成功在返回节点值的同时并返回true，当插入失败(遇到相等值节点时)返回false。
插入函数代码：
//插入函数
pair<val_type, bool> insert(const val_type& data)
{
//首次插入特殊处理
if (nullptr == _root)
{
Node* newnode = new Node(data);
_root = newnode;
++_size;
return { data,true };
}
//寻找合适的插入位置
Node* newnode = new Node(data);
Node* parent = _root;
Node* cur = _root;
while (cur)
{
if (_com(data.first, cur->_val.first)) // <
{
parent = cur;
cur = cur->_left;
}
else if (_com(cur->_val.first, data.first)) // >
{
parent = cur;
cur = cur->_right;
}
//找到相同值节点 返回false和节点值
else return { data,false}; // ==
}
//将新节点插入所寻找的父节点下
if (_com(data.first, parent->_val.first)) parent->_left = newnode;
else parent->_right = newnode;
newnode->_parent = parent;
cur = newnode;
while (parent)
{
//调整父节点平衡因子
if (parent->_left == cur) --(parent->_bf);
else if (parent->_right == cur) ++(parent->_bf);
//调整和旋转
if (parent->_bf == 1 || parent->_bf == -1)
{
parent = parent->_parent;
cur = cur->_parent;
}
else if (parent->_bf == 0) break;
else //开始调整和旋转
{
if (parent->_bf == -2 && cur->_bf == -1) RotateR(parent); //右单旋
else if (parent->_bf == 2 && cur->_bf == 1) RotateL(parent); //左单旋
else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent); //左右旋
else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); //右左旋
else { assert(false); }
}
}
++_size;
return { data,true };
}
关于节点调整流程：
关于旋转调整节点，我们接下来进行详细探究！
关于需要调整的情况，一共可以分为四大类：
是否旋转，取决于parent和cur节点的平衡因子：
parent(父节点)平衡因子 cur(子节点)平衡因子 操作 -2 -1 右单旋 2 1 左单旋 -2 1 左右双旋 2 -1 右左双旋
左单旋
当根节点的右子树平衡因子为1的情况下，仍然向右子树中插入比右子树节点值大的节点，此时就会导致根节点平衡因子为2，右子树平衡因子为1，此时就需要左单旋。
当我们向20节点的右子树中插入35时，35是该树中的最大节点，便会插入在最右节点，此时30节点的平衡因子变为1，25节点则变为2，需要对其进行左单旋。
左单旋的函数代码：
//左单旋
void RotateL(Node* parent)
{
//parent右子节点
Node* childR = parent->_right;
//parent右子节点的左子节点
Node* childRL = childR->_left;
//parent右子节点的右子节点
Node* childRR = childR->_right;
//parent节点的父节点
Node* pparent = parent->_parent;
//parent节点的右指向childR的左子树
parent->_right = childRL;
//如果childRL节点存在 则链接与parent节点的关系 否则parent->_right指向空
if (childRL) childRL->_parent = parent;
//将childR的左指向parent 构建链接关系
childR->_left = parent;
parent->_parent = childR;
//与pparent构建链接关系 如果pparent为_root根节点 则设置_root
if (pparent == nullptr)
{
_root = childR;
_root->_parent = nullptr;
}
else //否则查看原parent节点是pparent的左还是右子树 插入原parent位置
{
if (pparent->_left = parent) pparent->_left = childR;
else pparent->_right = childR;
childR->_parent = pparent;
}
//更新受影响节点的平衡因子
parent->_bf = childR->_bf = 0;
}
旋转过程简而言之就是更改节点的链接关系，使其深度降低！
对于上面图中的树，我们根据左单旋进行调整：
左单旋过程梳理：
- parent节点与childRL节点构建链接关系
- childR节点的左子树置为parent，并相互构建链接关系
- 判断pparent是否为空，不为空则将childR与pparent构建链接关系
- 将parent节点与childR节点的平衡因子置为0
注意：这里在构建链接关系时，一定要注意构建与父节点的关系，容易忘记；childRL节点可能为空，如果为空则不需要与其新父节点(parent)构建链接关系，需要if判断！
右单旋
当根节点的左子树平衡因子为-1的情况下，仍然向左子树中插入比左子树节点值小的节点，此时就会导致根节点平衡因子为-2，左子树平衡因子为-1，此时就需要右单旋。
右单旋与左单旋相似，只不过指针的调整方式不同。
当节点3插入后，节点10的平衡因子(左右子树高度差为2)为-2，此时插入的节点位于左子树的左侧，此时需要右旋转。
右单旋的函数代码：
//右单旋
void RotateR(Node* parent)
{
Node* childL = parent->_left;
Node* childLL = childL->_left;
Node* childLR = childL->_right;
Node* pparent = parent->_parent;
parent->_left = childLR;
if (childLR) childLR->_parent = parent;
childL->_right = parent;
parent->_parent = childL;
if (pparent == nullptr)
{
_root = childL;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent) pparent->_left = childL;
else pparent->_right = childL;
childL->_parent = pparent;
}
parent->_bf = childL->_bf = 0;
}
对于上面图中的树，我们根据右单旋进行调整：
右单旋过程梳理：
- parent节点与childLR节点构建链接关系
- childL节点的右子树置为parent，并相互构建链接关系
- 判断pparent是否为空，不为空则将childL与pparent构建链接关系
- 将parent节点与childL节点的平衡因子置为0
注意：这里在构建链接关系时，一定要注意构建与父节点的关系，容易忘记；childLR节点可能为空，如果为空则不需要与其新父节点(parent)构建链接关系，需要if判断！
右左双旋
当我们将值插入(高度差为1的树时)右子树右侧时会引发左单旋，当插入左子树左侧时会引发右单旋。
相反，如果将值插入右子树左侧或左子树右侧，则会引发双旋。
如果插入的是右子树左侧，此时parent平衡因子为，那么单旋就不能解决问题了，此时需要右左双旋，详细解释就是先 进行右单旋 再进行左单旋，这样才能降低高度。
关于以下情况，就是需要进行右左双旋：
右左双旋代码：
//右左双旋
void RotateRL(Node* parent)
{
Node* childR = parent->_right;
Node* childRL = childR->_left;
int bf = childRL->_bf;
RotateR(childR);
RotateL(parent);
/*
A
B C
D
E
*/
if (bf == -1)
{
parent->_bf = 0;
childR->_bf = 1;
childRL->_bf = 0;
}
/*
A
B C
D
E
*/
else if (bf == 1)
{
parent->_bf = -1;
childR->_bf = 0;
childRL->_bf = 0;
}
/*
A
B
C
*/
else if (bf == 0)
{
parent->_bf = 0;
childR->_bf = 0;
childRL->_bf = 0;
}
//如果出现其他情况，则表示代码有问题，需要检查
else assert(false);
}
关于右左双旋，可以结合下图理解(三列情况，对应三种不同的平衡因子调整)：
关于右左双旋的过程：
- 先确定parent和childR和childRL节点
- 对childR进行右单旋(将childRL变成childR的父节点)
- 对parent进行左单旋(再将childRL变成childR的父节点)
- 调整parent,childR和childRL节点的平衡因子(根据childRL节点平衡因子调整)
关于节点平衡因子的调整，从上图看出来，需要根据childRL节点来进行判断：
- 当childRL平衡因子为 0 ：
parent的平衡因子调整为0，childR的平衡因子调整为0，childRL平衡因子调整为0。- 当childRL平衡因子为 -1 ：
parent的平衡因子调整为0，childR的平衡因子调整为1，childRL平衡因子调整为0。- 当childRL平衡因子为 1 ：
parent的平衡因子调整为-1，childR的平衡因子调整为0，childRL平衡因子调整为0。
注意：右左双旋中，对childR进行右单旋转再对parent进行左单旋，这个顺序不能颠倒，且平衡因子的调整必须根据childRL平衡因子进行调整。
左右双旋
当节点插入到左子树的右侧时，此时parent平衡因子为-2且childR平衡因子为1，此时需要左右双旋，即需要 先进行左单旋，再进行右单旋 才能降低高度。
关于以下插入情况，此时的树需要进行左右双旋：
左右双旋代码：
//左右双旋
void RotateLR(Node* parent)
{
Node* childL = parent->_left;
Node* childLR = childL->_right;
int bf = childLR->_bf;
RotateL(childL);
RotateR(parent);
/*
A
B C
D E
F
*/
if (bf == -1)
{
childL->_bf = 0;
childLR->_bf = 0;
parent->_bf = 1;
}
/*
A
B C
D E
F
*/
else if (bf == 1)
{
childL->_bf = -1;
childLR->_bf = 0;
parent->_bf = 0;
}
/*
* A
* B
* C
*/
else if (bf == 0)
{
childL->_bf = 0;
childLR->_bf = 0;
parent->_bf = 0;
}
//如果出现其他情况，则表示代码有问题，需要检查
else assert(false);
}
关于右左双旋，可以结合下图理解(三列情况，对应三种不同的平衡因子调整)：
关于左右双旋的过程：
- 先确定parent和childL和childLR节点
- 对childL进行左单旋(将childLR变成childL的父节点)
- 对parent进行右单旋(再将childLR变成parent的父节点)
- 调整parent,childL和childLR节点的平衡因子(根据childLR节点平衡因子调整)
关于节点平衡因子的调整，从上图看出来，需要根据childRL节点来进行判断：
- 当childLR平衡因子为 0 ：
parent的平衡因子调整为0，childL的平衡因子调整为0，childLR平衡因子调整为0。- 当childLR平衡因子为 -1 ：
parent的平衡因子调整为1，childL的平衡因子调整为0，childLR平衡因子调整为0。- 当childLR平衡因子为 1 ：
parent的平衡因子调整为0，childL的平衡因子调整为-1，childLR平衡因子调整为0。
注意：左右双旋中，对childL进行右单旋转再对parent进行左单旋，这个顺序不能颠倒，且平衡因子的调整必须根据childLR平衡因子进行调整。