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