树补白：自平衡
此文的思路为本文的写作提供了有用的参考。在此致谢 。 https://blog.csdn.net/qq_25806863/article/details/74755131
自平衡树
BST问题在于可能存在很深很深的层。因此导致数据遍历的性能问题。为此引入AVL树，整棵树的层级高度之差总是为1.
Adelson-Velskii-Landi树
AVL树和AV没有太大的关系。它是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
何时需要平衡：AVL树插入和删除判断
AVL树的和移除节点的逻辑和BST完全一致。不同的在于，需要计算节点的平衡因子。
现在回顾高度的概念：从结点x向下到某个叶结点最长简单路径中边的条数 。
- 需要计算两个值：左节点高度$Hl$ 和右侧节点高度 $Hr$ 。二者之差只能等于1或-1或0，也就是说： |$Hl$ - $Hr$ | ≤ 1，如果大于1，则必须平衡。
/**
* 计算一个节点的高度值
* 左子树或右子树中较长的一条+1
*/
heightNode(node){
if(node==null){
return -1;
}else{
return Math.max(this.heightNode(node.left),this.heightNode(node.right))+1;
}
}因此，向左侧子树插入新节点时，需要计算高度。如果高度1，就需要平衡左子树。
平衡子树：avl旋转
通过旋转可以降低高度。
树的旋转相当容易。实在搞不定初期可以唯象论。
所谓的左旋和右旋都是以子树为原点的：如X是Y的子树，那么旋转就围绕X来进行。如果X是Y的左子树，那么就围绕Y将X向右旋转，看着就像是Y直接掉下来了，掉成X的右子树。如果X是Y的右子树，那么就围绕Y将X向左旋转，看着就像是Y直接掉下来了，掉成了X的左子树。
插入节点时分四种情况，四种情况对应的旋转方法是不同的：
涉及四种旋转。
右右旋转：向左的单旋转
比如我要插入一个key为90的节点。触发了自平衡。
- 相关节点有X(70)、Y(50)和Z(80)。
- 把X(70)节点放在平衡因子为-2的位置上，取代原来的Y(50)
- X的右侧不变。
- 将X（50）的左侧侧节点置为Y
//rr旋转：向左单旋
rotationRR(node){
let tmp=node.right;
node.right=tmp.right;
tmp.left=node;
return tmp;
}参考流程图
左左旋转：向右的单旋转
假设向AVL树插入节点5，这会造成树失衡（节点50 Y高度为+2），需要恢复树的平衡。下
- 与平衡操作相关的节点有三个（X、Y、Z），将节点X置于节点Y（平衡因子为+2）所在
的位置；
- 节点X的左子树保持不变；
- 将节点Y的左子节点置为节点X的右子节点Z（行{2}）；
- 将节点X的右子节点置为节点Y（行{3}）。
// ll旋转 向右单旋
rotationLL(node){
let tmp=node.left;
node.left=tmp.right
tmp.right=node;
return tmp;
}再看一个例子
//rr旋转：向左单旋
rotationRR(node){
let tmp=node.right;
node.right=tmp.right;
tmp.left=node;
return tmp;
}左右旋转：先RR，再LL，（向右）的双旋转
// LR
rotationLR(node){
node.left=this.rotationRR(node.left);
return this.rotationLL(node);
}右左旋转：先LL，再RR，（向左）的双旋转、
// RL
rotationRL(node){
node.right=this.rotationLL(node.right);
return this.rotationRR(node);
}完成insertNode方法
向左侧子树添加节点，且左侧的值小其左节点，应进行LL旋转。否则进行LR旋转。
向右侧子树添加节点，且右侧的值小于右节点，应进行RR旋转，否则进行RR旋转。
// 添加节点
insertNode(node,element){
let index=this.heightNode(node.left)-this.heightNode(node.right)
if(node==null){
node=new Node(element);
}else if(element<node.key){
node.left=this.insertNode(node.left,element);
if(node.left!==null){
// 确认是否需要平衡
if(index>1){
// 左侧子树高度-右侧子树高度>1;需要平衡子树
node=this.rotationLL(node);
}else if(index<-1){
// 右侧子树高度-左侧子树高度>1;需要平衡子树
node=this.rotationLR(node);
}
}
}else if(element>node.key){
node.right=this.insertNode(node.right,element)
if(node.right!==null){
// 确认是否需要平衡
if(index>1){
// 左侧子树高度-右侧子树高度>1;需要平衡子树
node=this.rotationRR(node);
}else if(index<-1){
// 右侧子树高度-左侧子树高度>1;需要平衡子树
node=this.rotationRL(node);
}
}
}
return node;
}