(14)[Chapter6]AVL 트리_삽입 메소드

Chapter6_4_AVL트리탐색(이론+코드).pdf

5.68MB

##중요한 핵심 부분:

• 삽입 메소드 구현 코드 분석 :
• main에서 AVL트리 조립하는 방법

##복습해야 될 부분 : AVL삽입메소드와 Rebalance메소드를 void반환형으로 스스로 다시 작성해보기

##전체 코드

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
typedef int element;
 
typedef struct _AVLBNode 
{
    struct _AVLBNode* left;
    struct _AVLBNode* right;
    element data;
}AVLBNode;
 
 
//1_탐색
AVLBNode* Search(AVLBNode* root, element data)
{
    if (root == NULL) 
    {
        printf("%d는 트리에 존재하지 않습니다.\n", data);
        return root;
    }
 
    if (root->data > data) 
    {
        return Search(root->left, data);
    }
    else if (root->data < data)
    {
        return Search(root->right, data);
    }
    else 
    {
        return root;
    }
}
 
//2_ 회전
 
//LL
AVLBNode* LL(AVLBNode* Parent) 
{
 
    AVLBNode* child = Parent->left;
 
    Parent->left = child->right;
 
    child->right = Parent;
 
    return child;
}
//RR
AVLBNode* RR(AVLBNode* Parent) 
{
    AVLBNode* child = Parent->right;
 
    Parent->right = child->left;
 
    child->left = Parent;
 
    return child;
}
 
//LR
AVLBNode* LR(AVLBNode* Parent) 
{
    AVLBNode* child = Parent->left;
 
    Parent->left = RR(child);
 
    return LL(Parent);
}
 
//RL
AVLBNode* RL(AVLBNode* Parent)
{
    AVLBNode* child = Parent->right;
 
    Parent->right = LL(child);
 
    return RR(Parent);
}
 
//3_ height, BF 계산 메소드
//height
int GetHeight(AVLBNode* p) 
{
    int height = 0;
 
    if (p == NULL) {
        return height;
    }
 
    int leftheight = GetHeight(p->left);
    int rightheight = GetHeight(p->right);
 
    height = (leftheight > rightheight) ? leftheight: rightheight;
 
    return height + 1;
 
}
 
//BF계산 메소드
int GetBF(AVLBNode* p) 
{
    return GetHeight(p->left) - GetHeight(p->right);
}
 
//4_ 한 노드에 대한 BF값 계산 + 불균형 조정 메소드
AVLBNode* Rebalance(AVLBNode** root) 
{
    int BF = GetBF(*root);
 
    if (BF > 1) 
    {
        if (GetBF((*root)->left) > 0)//LL
        {
            return LL(*root);
        }
        else 
        {
            return LR(*root);
        }
    }
    else if (BF < -1) 
    {
        if (GetBF((*root)->right) < 0)//RR
        {
            return RR(*root);
        }
        else
        {
            return RL(*root);
        }
    }
 
    //★균형이 맞는 곳은 그대로 반환하기
    return *root;
}
 
//5_ AVL트리 삽입 메소드
AVLBNode* InsertAVL(AVLBNode** root,element data)
{
    if (*root == NULL) 
    {
        *root = (AVLBNode*)malloc(sizeof(AVLBNode));
        (*root)->data = data;
        (*root)->left = NULL;
        (*root)->right = NULL;
        return *root;
    }
 
    if ((*root)->data > data) 
    {
        //return InsertAVL(&((*root)->left), data);
        (*root)->left = InsertAVL(&((*root)->left), data);
    }
    else if ((*root)->data < data)
    {
        //return InsertAVL(&((*root)->right), data);
        (*root)->right = InsertAVL(&((*root)->right), data);
    }
    else 
    {
        printf("%d는 이미 트리에 존재하는 값입니다.\n",data);
        return *root;
    }
 
    *root = Rebalance(root);
    return *root;
}
 
//6_ 출력 하기
void InOrder(AVLBNode* root) {
    //종료조건
    if (root == NULL) {
        return;
    }
    //L
    InOrder(root->left);
    //D
    printf(" %d", root->data);
    //R
    InOrder(root->right);
}
 
 
int main() 
{
    AVLBNode* AVL_root = NULL;
 
    // AVL 트리
    AVL_root = InsertAVL(&AVL_root, 50);
    InsertAVL(&AVL_root, 60);
    InsertAVL(&AVL_root, 70);
    InsertAVL(&AVL_root, 90);
    InsertAVL(&AVL_root, 80);
    InsertAVL(&AVL_root, 75);
    InsertAVL(&AVL_root, 73);
    InsertAVL(&AVL_root, 72);
 
    printf("AVL Tree InOrder:\n");
    InOrder(AVL_root);
    printf("\n");
 
 
    
    return 0;
}