04-树5 Root of AVL Tree

我不是女神ヾ 2022-08-21 10:51 11阅读 0赞

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

![attachment_id_31][] ![attachment_id_32][]

![attachment_id_33][] ![attachment_id_34][]

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains a positive integer NNN (≤20\\le 20≤20) which is the total number of keys to be inserted. Then NNN distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

### Output Specification: ###

For each test case, print the root of the resulting AVL tree in one line.

### Sample Input 1: ###

5
    88 70 61 96 120

### Sample Output 1: ###

### Sample Input 2: ###

7
    88 70 61 96 120 90 65

### Sample Output 2: ###

主要是调整平衡二叉树，LL，RR，LR，RL.....

#include <stdio.h>
    #include <stdlib.h>
    #define ElementType int
    #define Max(a,b) ((a)>(b)?(a):(b))
    typedef struct AVLTreeNode{
        ElementType Data;
        struct AVLTreeNode *Left;
        struct AVLTreeNode *Right;
        int Height;
    } *AVLTree;
    
    
    int 
    GetHeight(AVLTree T)
    {
        if(!T) 
            return 0;
        else
            return T->Height;
    }
    
    AVLTree
    SingleLeftRotation(AVLTree A)
    {
        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
    SingleRightRotation(AVLTree A)
    {
        AVLTree B=A->Right;
        A->Right=B->Left;
        B->Left=A;
        A->Height=Max(GetHeight(A->Left),GetHeight(A->Right))+1;
        B->Height=Max(GetHeight(B->Right),A->Height)+1;
        
        return B;
    }
    
    AVLTree
    DoubleLeftRightRotation(AVLTree A)
    {
        A->Left=SingleRightRotation(A->Left);
        return SingleLeftRotation(A);
    }
    
    
    AVLTree
    DoubleRightLeftRotation(AVLTree A)
    {
        A->Right=SingleLeftRotation(A->Right);
        return SingleRightRotation(A);
    }
    
    AVLTree 
    AVL_Insertion(ElementType X, AVLTree T)
    {
        if(!T){
            T=(AVLTree)malloc(sizeof(struct AVLTreeNode));
            T->Data=X;
            T->Height=0;
            T->Left=T->Right=NULL;
        }else if(X<T->Data){
            T->Left=AVL_Insertion(X,T->Left);
            if(GetHeight(T->Left)-GetHeight(T->Right)==2)	//判断左右两边的树平衡不
                if(X<T->Left->Data)
                    T=SingleLeftRotation(T);	//LL旋转
                else
                    T=DoubleLeftRightRotation(T);	//LR旋转
        }else if(X>T->Data){
            T->Right=AVL_Insertion(X,T->Right);
            if(GetHeight(T->Left)-GetHeight(T->Right)==-2)
                if(X>T->Right->Data)
                    T=SingleRightRotation(T);	//RR旋转
                else
                    T=DoubleRightLeftRotation(T);	//RL旋转
        }
        
        T->Height=Max(GetHeight(T->Left),GetHeight(T->Right))+1;	//height为此子树的高度
        return T;
    }
    int main()
    {
        int i,NodeNum,tmpkey;
        AVLTree tree=NULL;
        scanf("%d",&NodeNum);
        for(i=0;i<NodeNum;i++){
            scanf("%d",&tmpkey);
            tree=AVL_Insertion(tmpkey,tree);
            
        }
        
        printf("%d",tree->Data);
        
        return 0;      
    }

[attachment_id_31]: https://pta.patest.cn/api/image/attachment?id=31
[attachment_id_32]: https://pta.patest.cn/api/image/attachment?id=32
[attachment_id_33]: https://pta.patest.cn/api/image/attachment?id=33
[attachment_id_34]: https://pta.patest.cn/api/image/attachment?id=34