数据结构MOOC|平衡二叉树

迈不过友情╰ 2022-05-19 23:44 279阅读 0赞

ASL平均查找长度：

![70][]

平衡因子BF：BF(T)=hL-hR

平衡二叉树（AVL树）：空树或者任一节点左、右子树高度差的绝对值不超过1，即|BF(T)|<=1

![70 1][]

![70 2][]

RR旋转：

![70 3][]

LL旋转：

![70 4][]

LR旋转：

![70 5][]

RL旋转：

![70 6][]

typedef struct AVLNode *Position;
    typedef Position AVLTree; /* AVL树类型 */
    struct AVLNode{
        ElementType Data; /* 结点数据 */
        AVLTree Left;     /* 指向左子树 */
        AVLTree Right;    /* 指向右子树 */
        int Height;       /* 树高 */
    };
     
    int Max ( int a, int b )
    {
        return a > b ? a : b;
    }
     
    AVLTree SingleLeftRotation ( AVLTree A )
    { /* 注意：A必须有一个左子结点B */
      /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */     
     
        AVLTree B = A->Left;
        A->Left = B->Right;
        B->Right = A;
        A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
        B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
      
        return B;
    }
     
    AVLTree DoubleLeftRightRotation ( AVLTree A )
    { /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
      /* 将A、B与C做两次单旋，返回新的根结点C */
         
        /* 将B与C做右单旋，C被返回 */
        A->Left = SingleRightRotation(A->Left);
        /* 将A与C做左单旋，C被返回 */
        return SingleLeftRotation(A);
    }
     
    /*************************************/
    /* 对称的右单旋与右-左双旋请自己实现 */
    /*************************************/
     
    AVLTree Insert( AVLTree T, ElementType X )
    { /* 将X插入AVL树T中，并且返回调整后的AVL树 */
        if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
            T = (AVLTree)malloc(sizeof(struct AVLNode));
            T->Data = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        } /* if (插入空树) 结束 */
     
        else if ( X < T->Data ) {
            /* 插入T的左子树 */
            T->Left = Insert( T->Left, X);
            /* 如果需要左旋 */
            if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
                if ( X < T->Left->Data ) 
                   T = SingleLeftRotation(T);      /* 左单旋 */
                else 
                   T = DoubleLeftRightRotation(T); /* 左-右双旋 */
        } /* else if (插入左子树) 结束 */
         
        else if ( X > T->Data ) {
            /* 插入T的右子树 */
            T->Right = Insert( T->Right, X );
            /* 如果需要右旋 */
            if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
                if ( X > T->Right->Data ) 
                   T = SingleRightRotation(T);     /* 右单旋 */
                else 
                   T = DoubleRightLeftRotation(T); /* 右-左双旋 */
        } /* else if (插入右子树) 结束 */
     
        /* else X == T->Data，无须插入 */
     
        /* 别忘了更新树高 */
        T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
         
        return T;
    }

[70]: /images/20220520/880ab57b586a4506a8531398caf9bb3d.png
[70 1]: /images/20220520/165b03779ef243749993eb70f65d45ce.png
[70 2]: /images/20220520/d3fc0d47252f4ff7add7f29dc83b52ca.png
[70 3]: /images/20220520/d8e8e1e421724ff98bc2c7d6604c7064.png
[70 4]: /images/20220520/c703443c6e5f41baa88ee11e3d27520b.png
[70 5]: /images/20220520/6a2aa8f4a6f44704aecf3bbc0c31f74d.png
[70 6]: /images/20220520/7c09a31bb323467ea715f5441d040edb.png