PAT MOOC dataStructure 4-1

데이터 구조 연습 4-1 AVL 트리
1. 제목:
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N 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 ythe root of the resulting AVL tree in one line.
Sample Input 1:

5

88 70 61 96 120

Sample Output 1:
   70
 
2. 제목 분석:
매우 전형적인 AVL 밸런스 트리의 실현.
선생님이 제공한 코드 프레임워크 구조에 따라 프로그래밍을 진행하다.안에 귀속 알고리즘을 운용했다는 점은 내가 비교적 약한 부분이다.매번 귀속을 만날 때마다 머리가 커진다.돌아가는 나선형에 따라 머리가 점점 뚜렷해지지 않을 것이다.엉엉
문제의 요구는 순서대로 수결점을 삽입하고 왼쪽 작은 오른쪽의 규칙에 따라 수치를 삽입하는 것이다.
InsertNode 함수 반복을 사용하여 삽입합니다.값이 현재 결점 값보다 크면 오른쪽 하위 트리에 차례로 삽입됩니다.반대로도 마찬가지다.
또한 삽입이 끝날 때마다 반복적으로 트리 노드의 높이를 변경하여 상부의 노드가 좌우 두 개의 트리의 높이차를 비교하여 그 자체의 균형을 판별할 수 있도록 한다.
현재 노드의 불균형을 판단하면 순환적으로 실행되는 프로그램이기 때문에 그 하위 노드는 일정한 균형을 이룬다. 현재 노드는 첫 번째 불균형한 노드이고 이때 LL, LR, RR 또는 RL을 통해 현재 노드를 균형 조정한다.
조정 방법은 LL을 예로 들 수 있습니다.
현재 노드 A가 균형이 맞지 않고 삽입된 노드가 왼쪽 트리 B의 왼쪽 트리 C에 있습니다.
먼저 A->left(원래 B)를 B->right로 가리키며 교환을 완료합니다.그리고 B->right=A를 되돌려줍니다. 이때 B의 오른쪽 트리는 A이고 B의 원래 오른쪽 트리는 A의 왼쪽 트리가 됩니다.
그런 다음 B로 돌아가면 위쪽의 포인터가 B를 가리키고 B층 균형이 맞춰집니다.이 때 위층이 불균형한 것을 발견하면 루트로 돌아가 루트 노드를 업데이트할 때까지 계속 조정합니다.
LR은 A의 왼쪽 트리 B를 RR하고 A를 LL합니다.나무의 균형을 유지하다.
 
3. 소스 코드:
 

#include <stdio.h>

#include <stdlib.h>



typedef struct AVLnode{

    int height;

    struct AVLnode * left;

    struct AVLnode * right;

    int data;

}tAVLnode, *pAVL;



pAVL SingleLeftRotation(pAVL T);



pAVL DoubleLeftRightRotation(pAVL T);



pAVL SingleRightRotation(pAVL T);



pAVL DoubleRightLeftRotation(pAVL T);



pAVL InsertNode(int data, pAVL T);



int GetHeight(pAVL T);



pAVL InsertNode(int data, pAVL T)

{

    if(!T)

    {

        T = (pAVL)malloc(sizeof(tAVLnode));

        T->data = data;

        T->height = 0;

        T->left = NULL;

        T->right = NULL;

    }

    else if(data < T->data)

    {

        T->left = InsertNode(data,T->left);

        if(GetHeight(T->left)-GetHeight(T->right)== 2)

        {

            if(data < T->left->data)

            {

                T=SingleLeftRotation(T);

            }

            else

            {

                T=DoubleLeftRightRotation(T);

            }

        }

    }

    else if(data > T->data)

    {

        T->right = InsertNode(data,T->right);

        if(GetHeight(T->left)-GetHeight(T->right) == -2)

        {

            if(data > T->right->data)

            {

                T=SingleRightRotation(T);

            }

            else

            {

                T=DoubleRightLeftRotation(T);

            }

        }

    }

    T->height = (GetHeight(T->left)>=GetHeight(T->right))?GetHeight(T->left)+1:GetHeight(T->right)+1;

    

    return T;    

}



pAVL SingleLeftRotation(pAVL T)

{

    pAVL B = T->left;

    T->left = B->right;

    B->right = T;

    T->height = (GetHeight(T->left)>=GetHeight(T->right))?GetHeight(T->left)+1:GetHeight(T->right)+1;

    B->height = (GetHeight(B->left)>=GetHeight(B->right))?GetHeight(B->left)+1:GetHeight(B->right)+1;

    return B;

}



pAVL DoubleLeftRightRotation(pAVL T)

{

    T->left = SingleRightRotation(T->left);

    return SingleLeftRotation(T);

}



pAVL SingleRightRotation(pAVL T)

{

    pAVL B = T->right;

    T->right = B->left;

    B->left = T;

    T->height = (GetHeight(T->left)>=GetHeight(T->right))?GetHeight(T->left)+1:GetHeight(T->right)+1;

    B->height = (GetHeight(B->left)>=GetHeight(B->right))?GetHeight(B->left)+1:GetHeight(B->right)+1;

    return B;

}



pAVL DoubleRightLeftRotation(pAVL T)

{

    T->right = SingleLeftRotation(T->right);

    return SingleRightRotation(T);

}



int GetHeight(pAVL T)

{

    if(!T)

    {

        return -1;

    }

    else

    {

        return T->height;

    }

}



int main()

{

    int nodeSum;

    int data;

    int i;

    pAVL Root = NULL;

    

    scanf("%d", &nodeSum);

    

    for(i=0;i<nodeSum;i++)

    {

        scanf("%d",&data);

        Root = InsertNode(data,Root);

    }

    printf("%d",Root->data);

}