AVL树由二叉搜索树进化而来。在二叉搜索树中如果出现特殊情况：所有插入的数据均为有序，根据二叉搜索树的插入原理，其会退化为单枝斜向下的而二叉树，此时插入，查找，删除的效率也就退化成了O(n)，效率太低。为了解决痛点因此引入AVL树。
AVL树继承了二叉搜索树的大框架，在其上增加了规定：在插入新数据后保证任意树的子树高度不大于1。因此定义了一个整型作为平衡因子，当左子树高度加1，平衡因子减1。右子树高度加1，平衡因子加1。在插入中需要确保任意节点的平衡因子绝对值小于1。
当某个插入某个节点后树中的任意一个节点的平衡因子绝对值大于1，要进行调整，这种调整就称为旋转。
那么什么是旋转如何旋转？
旋转：
1、让这颗子树左右高度不超过1
2、旋转过程中继续保持他是搜索树
3、更新调整孩子节点的平衡因子
4、让这颗子树的高度跟插入前保持一致
为了更方便对树内节点进行旋转，AVL树在二叉搜索树之上还增加了parent节点：
template<class T>
struct AVLTree
{AVLTreeNode(const T& data = T()): left(nullptr), right(nullptr), pare(nullptr), k(data), bf(0){}AVLTreeNode<T>* left;AVLTreeNode<T>* right;AVLTreeNode<T>* pare;T k;int bf; //平衡因子
};二叉搜索树的插入：
bool Insert(const K& key)
{
Node* cur = _root;
Node* pare = nullptr;
while (cur)
{
if (key < cur->k)
{
pare = cur;
cur = cur->right;
}
else if (key > cur->k)
{
pare = cur;
cur = cur->left;
}
else if (key == cur->k) return false;
}
Node* newnode = Node(key);
if (key < pare->k)
{newnode = pare->right;
newnode->pare = pare;
pare->bf++;//更新平衡因子
}
else if (key > pare->k)
{newnode = pare->left;
newnode->pare = pare;
pare ->bf--;
}
//到此为止是二叉树的插入
}
// 接下来开始判定是否有平衡因子绝对值大于2，从当前插入的节点的父节点开始，依次向上遍历，一共有这几种情况：
while(pare) //遍历到根节点
{
if(pare->bf == 0)//此时插入节点的父节点平衡因子为0，代表插入前父节点的左子树高度比右子树大1，或者右子树高度比左子树大1，插入后填补了高度差，但对于整个树来说，其高度没有改变，因此可以断定整个树的高度没有改变，直接退出循环。
break;
else if(pare->bf == -1 || pare->bf == 1) //此时如果新插入节点的父节点的平衡因子不为0，那么就代表插入节点前父节点为0，其子树是平衡的，插入后树的高度发生了变化。由于高度的变化可能对上层的节点平衡因子产生影响，此时就要找到父节点的父节点去查看它的情况。
{ cur = pare; pare = pare->pare;}
else if(pare ->bf == -2 || pare->bf == 2)//此时违反了AVL树的规定，需要进行旋转,旋转后pare的平衡因子变为0，可以直接break，不需要再继续往上遍历。
// AVL树的旋转一共有四种情况：
//通过抽象图对四种情况进行解析，图中的h代表任意高度为h的树(h为任意不小于0的整数），由于AVL树的调整不关心树的形状，只关心树的高度，因此抽象成了一个矩形。
（1）左单旋：
当产生如图情况，20的右子树高度加一导致10的左右高度差绝对值为2，我们需要将20这个节点往上提，10这个节点网上压，导致10旋转到20的左边，称为左单旋。左单旋的具体实现是，将pare（pare是10）变为cur（cur是20）的左树，然后cur的原左树变为pare的右树，也符合二叉搜索树的性质。
void RotateL(Node * pare){
Node* cur = pare -> right;
Node* subR = cur ->right;
ppare = pare ->pare;
cur -> left = pare;
pare->right = subR;
pare -> pare = cur;
if(subR != nullptr)
subR ->pare = pare;
if(ppare == nullptr)//此时pare为根
{_root == cur;
_root ->pare = nullptr;
}
else //如果pare不为根，分情况讨论pare是ppare的左树还是右树
{
if(ppare ->key < cur)
ppare-> right = cur;
else
ppare ->left = cur;
}
//接下来更新平衡因子
pare ->bf = cur->bf =0;
}
（2）右单旋：
产生如图情况，20这个节点的右子树高度加一导致其平衡因子变为2，需要将20往下压，10向上提，20旋转到10的右边，称为右单旋。右单旋的具体实现是将pare（也就是20）变为cur的右树，cur的原右树变为pare的左树。
void RotateR(Node* pare){
Node* cur = pare ->left;
Node* subR = cur ->left;
Node* ppare = pare ->pare;
cur ->right = pare;
pare ->left = subR;
if(subR != nullptr)
subR ->pare = pare;
if(ppare == nullptr)
{
_root = cur;
cur ->pare = nullptr;
}
else
{
if(ppare ->k < cur->k)
ppare ->right = cur;
else
ppare ->left = cur;
}
cur->bf = pare->bf = 0;
}
（3)左右双旋
在这种情况下要进行两次旋转，先对10这个节点进行左单旋，再对30这个节点进行右单旋。并且20的平衡因子变为0，10的平衡因子变为0，30的平衡因子变为-1。
void RotateLR(Node* pare)
{
Node * cur = pare->left;
Node * subR = cur ->right;
RotateL(cur);
RotateR(pare);
if(subR->bf == -1) //两种情况，在subR(图中的20节点)的左或者右插入
{
cur->bf = subR->bf = 0;
pare->bf = 1;
}
else if(subR ->bf == 1)//插入在subR的右边
{
pare ->bf = subR ->bf = 0;
cur->bf = -1;
}
else if(subR ->bf == 0)//subR自己就是新增节点
{
pare ->bf = cur ->bf = subR->bf = 0;
}
}
(4)右左双旋
也就是上一种情况的反向情况，如图：
先对30进行右单旋，再对10进行左单旋即可。
void RotateLR(Node* pare)
{
Node * cur = pare->right;
Node * subR = cur ->left;
RotateR(cur);
RotateL(pare);
if(subR->bf == -1)
{
pare->bf = subR->bf = 0;
cur->bf = 1;
}
else if(subR ->bf == 1)
{
cur ->bf = subR ->bf = 0;
pare ->bf = -1;
}
else if(subR ->bf == 0)
{
pare ->bf = cur ->bf = subR->bf = 0;
}
}
插入代码如下：
bool Insert(const k& data){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->k < k){pare = cur;cur = cur->_right;}else if (cur->k > k){pare = cur;cur = cur->_left;}else{return false;}}cur = new Node(k);if (pare->k< kt){pare->right = cur;cur->pare = pare;}else{pare->left = cur;cur->pare = pare;}while (pare) {if (cur == pare->left){pare->bf--;}else{pare->bf++;}if (pare->bf == 0){break;}else if (pare->_bf == 1 || pare->bf == -1){cur = pare;pare = pare->pare;}else if (pare->bf == 2 || pare->bf == -2){if (pare->bf == 2 && cur->bf == 1){RotateL(pare);}else if (pare->bf == -2 && cur->bf == -1){RotateR(pare);}else if (pare->bf == -2 && cur->bf == 1){RotateLR(pare);}else if (pare->bf == 2 && cur->bf == -1){RotateRL(pare);}else{assert(false);}break;}else{assert(false);}}return true;}
![k8s节点负载使用情况分析命令kubectl describe node [node-name]](https://img-blog.csdnimg.cn/direct/29bf0da49bfd4015ab54bb07fa292350.png)
