AVL树总结

发布于 2018-12-06  120 次阅读


 

AVL树总结

AVL树是二叉查找树的一种优化,能将链状的二叉查找树几乎平均地储存下来,从而减少搜索使用的时间。

 

AVL树是空树,或满足以下定义的树:

1、左右子树都是AVL树;(递归定义)

2、左右子树高度之差不超过1;

 

定义平衡因子:

左子树高度-右子树高度,当平衡因子大于等于2时,我们就称这棵树不平衡,需要通过旋转让它重新平衡。

 

获取节点高度:

       int h(int rt){

       if(rt==0) return -1;//这里return-1的原因后面阐释

       return no[rt].height;

}

 

单旋转

“左左”当根节点的左子树的左儿子与根节点的右儿子不平衡时

我们通过单旋转使平衡树符合该树的性质

int SingeRotateWithLeft(int x){
    int y;
    y=no[x].left;
    no[x].left=no[y].right;
    no[y].right=x;
    no[y].height=max(h(no[y].left),h(no[y].right))+1;
    no[x].height=max(h(no[x].left),h(no[x].right))+1;
    return y;
}

“右右”方法类似,与左左对称

 

双旋转

“左右”当根节点的左子树的右儿子与根节点的右儿子不平衡时

旋转两次即可使这棵树平衡

int doubleRotateWithLeft(int x){

    no[x].left=SingleRotateWithRight(no[x].left);
    return SingleRotateWithLeft(x);

}