AVL树主要代码清单

/*返回树的高度*/
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树的概念以及代码实现

添加新评论

评论列表