初音ミクの消失

AVL树总结

字数统计: 565阅读时长: 2 min
2018/12/06 Share

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);
<span class="hljs-keyword">return</span> SingleRotateWithLeft(x);

}

“右左”同理。

插入操作:先正常插入指定结点,再判断原树是否平衡,不平衡要根据具体情况旋转使原树平衡

int insert(int k,int rt){
    if(rt==0)
        rt=newNode(k);
    else if( k< no[rt].key ){
        no[rt].left=insert(k,no[rt].left);
        if( h(no[rt].left)-h(no[rt].right) )==2 )
            if(kelse rt= DoubleRotateWithLeft(rt)
    }else if( k > no[rt].key){
        no[rt].right=insert(k,no[rt].right);
        if( h(no[rt].right)-h(no[rt].left) )==2 )
            if(k > no[ no[rt].right ] .key ) rt=SingleRotateWithRight(rt);
            else rt= DoubleRotateWithRight(rt)
    }
    no[rt].height = max ( h( no[rt].left ), h( no[rt].right ) ) +1;
    return rt;
}
int newNode(int k){
    no[cnt].height=no[cnt].left=no[cnt].right=0;
    no[cnt].key=k;
    return cnt++;
}
AVL树过于复杂,但却是其他二叉搜索树变形特别是旋转的基础,删除操作实在过于复杂,本人无法理解。。。建议大家使用懒惰标记吧,不在真正意义上删除结点。

说这么多 大家还是转战SBT吧QAQ

原文作者:mrh929

原文链接:https://mrh1s.top/posts/17525de2/

发表日期:December 6th 2018, 11:46:59 pm

更新日期:May 5th 2019, 1:06:27 pm

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. AVL树总结