menu Error0 Blog
AVL树主要代码清单
53 浏览 | 2019-11-07 | 分类:数据结构 | 标签:
/*返回树的高度*/
int GetHeight(SubTree T)
{
    if (!T)
        return 0;
    else
        return T->height;
}

int Max(int a, int b)
{
    return (a > b) ? a : b;
}
/*左子树的左边就要 往右转*/
SubTree LLRotate(SubTree T)
{
    SubTree Tmp;
    Tmp = T;
    T = T->left;
    Tmp->left = T->right;
    T->right  = Tmp;
    /*维护高度*/
    Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1;
    T->height   = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
    return T;
}
/*右子树的右边就要 往转转*/
SubTree RRRotate(SubTree T)
{
    SubTree Tmp;
    Tmp = T;
    T = T->right;
    Tmp->right = T->left;
    T->left    = Tmp;
     /*维护高度*/
    Tmp->height = Max(GetHeight(Tmp->left), GetHeight(Tmp->right)) + 1;
    T->height   = Max(GetHeight(T->left), GetHeight(T->right)) + 1;
    return T;
}
/*先左 后右 */
SubTree LRRotate(SubTree T)
{
    T->left = RRRotate(T->left);
    T = LLRotate(T);
    return T;
}
/*先右 后左 */
SubTree RLRotate(SubTree T)
{
    T->right = LLRotate(T->right);
    T = RRRotate(T);
    return T;
}

自己总结:AVL树概念图
来自:AVL树的概念以及代码实现

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

Emoji

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 46

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 48

Warning: file_get_contents(/assets/json/owo.json): failed to open stream: No such file or directory in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 87

Warning: array_keys() expects parameter 1 to be array, null given in /www/wwwroot/build/usr/themes/Cuckoo/includes/owo.php on line 89