(12)실습7주차_AVL트리_FindMin(),DeleteAVL()_[문제3]

#문제 PDF파일은 아래에 링크 :

https://kojammin.tistory.com/107

(9)실습7주차_이진탐색트리_전위순회,삽입,삭제_이론+코드[문제1]

 

#문제 풀기전 알아야 할 개념 :

• DeleteAVL() 논리 순서 :

1. 종료조건 : 빈자리 도달했을 시 => 삭제할 data가 트리에 존재X => 이떄는 종료하는 게 맞다(InsertAVL과 차이)
2. 탐색 : 재귀
3. 삭제할 대상노드를 찾았을 시 => 세가지 Case : 삭제 대상 | 0차 | 1차 | 2차

• Case 1 ) 삭제 대상 0차 => free(포인터) => 포인터 노드 = NULL 대입
• Case 2 ) ▲삭제 대상 1차 :

=> 1_ 삭제 대상 포인터를 임시 tmp 포인터에 보관

=> 2_ (★) 삭제대상 포인터(*p) 에 유효 자손((*p)->Left || (*p)->Right 둘중 하나)를 땡긴다.

=> 3_ 임시 tmp 포인터 free()

• Case 3 ) ★삭제 대상 2차 

=> 1_FindMin()메소드로 삭제대상의 후속 노드 찾기

=> 2_ 후속노드 data를 삭제 대상 노드에 대입

=> 3_ 다시 포인터->Rgint 부터 DeleteAVL()재귀해서 최소노드를 삭제한다.

4. free()한 후, 루트 노드 거슬러 오라면서, 포인터 노드를 Rebalance() 해준다.

#Rebalance()메소드 이론 노트 :

 

#DeleteAVL() 노트 :

 

 

##[문제3] 최종 코드 :

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
int del_sign = -1;
 
typedef struct _AVLTree 
{
    int data;
    struct _AVLTree* Left;
    struct _AVLTree* Right;
 
}BNode;
 
//회전 메소드
BNode* LL(BNode* L1) 
{
    BNode* L2 = L1->Left;
    L1->Left = L2->Right;
    L2->Right = L1;
    return L2;
}
 
BNode* RR(BNode* R1) 
{
    BNode* R2 = R1->Right;
    R1->Right = R2->Left;
    R2->Left = R1;
    return R2;
}
 
BNode* LR(BNode* L1) 
{
    BNode* L2 = L1->Left;
    L1->Left = RR(L2);
    return LL(L1);
}
 
BNode* RL(BNode* R1) 
{
    BNode* R2 = R1->Right;
    R1->Right = LL(R2);
    return RR(R1);
}
 
//GetHeight메소드
int GetHeight (BNode* p)
{
    if (p == NULL) 
    {
        return 0;
    }
 
    int L = GetHeight(p->Left);
    int R = GetHeight(p->Right);
 
    return (L > R) ? L + 1 : R + 1;
}
 
//GetBH메소드
int GetBH(BNode* p) 
{
    if (p == NULL) {
        return 0;
    }
 
    return GetHeight(p->Left) - GetHeight(p->Right);
 
}
 
//Rebalance메소드
BNode* Rebalance(BNode** p) 
{
    int BH = GetBH(*p);
 
    if (BH > 1) {
        int L2_BH = GetBH((*p)->Left);
 
        if (L2_BH > 0) 
        {
            *p = LL(*p);
        }
        else if (L2_BH<0)
        {
            *p = LR(*p);
        }
 
    }
    else if (BH < -1) 
    {
        int R2_BH = GetBH((*p)->Right);
 
        if (R2_BH < 0) 
        {
            *p = RR(*p);
        }
        else if (R2_BH>0) 
        {
            *p = RL(*p);
        }
    }
 
    return *p;
 
}
 
//InsertAVL()메소드
void InsertAVL(BNode** p, int data) 
{
    //1_빈자리 도달 시, 할당 삽입 => 함수종료(x)
    if ((*p) == NULL) 
    {
        (*p) = (BNode*)malloc(sizeof(BNode));
        (*p)->data = data;
        (*p)->Left = NULL;
        (*p)->Right = NULL;
    }
    else 
    {
        //2_탐색 : 재귀
        if ((*p)->data > data) 
        {
            InsertAVL(&((*p)->Left), data);
 
        }
        else if ((*p)->data<data) 
        {
            InsertAVL(&((*p)->Right), data);
        }
        //이거 한번 실험 해보자(중복된 키가 있을 시 처리)
    }
    //3_ 거슬러 올라오면서, Rebalance로 균형조정
    if ((*p) != NULL) 
    {
        (*p) = Rebalance(p);
    }
 
    return;
}
 
//DeleteAVL()메소드
 
//1_FindMin()메소드
BNode* FindMin(BNode* p) 
{
    BNode* tmp = p->Right;
    while (tmp->Left!=NULL) {
        tmp = tmp->Left;
    }
    return tmp;
}
 
//2_ DeleteAVL()
void DeleteAVL(BNode** p , int data) 
{
    //1_종료조건
    if ((*p)==NULL) {
        del_sign = 1;
        return;
        //InsertAVL과 다르게 얘는 종료조건때는 재귀할 필요가 없어, return 때린다.
    }
    else 
    {
        //2_탐색 : 재귀
        if ((*p)->data > data)
        {
            DeleteAVL(&((*p)->Left), data);
 
        }
        else if ((*p)->data < data)
        {
            DeleteAVL(&((*p)->Right), data);
        }
        else//3_ 삭제할 대상을 찾았다면, 
        {
            //삭제 대상이 0차
            if ((*p)->Left == NULL && (*p)->Right==NULL) 
            {
                free((*p));
                (*p) = NULL;
 
            }//삭제 대상이 1차
            else if((*p)->Left == NULL)
            {
                BNode* tmp = *p;
                (*p) = (*p)->Right;
                free(tmp);
            }
            else if ((*p)->Right == NULL)
            {
                BNode* tmp = *p;
                (*p) = (*p)->Left;
                free(tmp);
            }
            else //삭제 대상이 2차
            {
                BNode* tmp = FindMin((*p));
                (*p)->data = tmp->data;
 
                DeleteAVL(&((*p)->Right), tmp->data);
 
            }
        }
 
    }
 
    if ((*p) != NULL) {
        (*p) = Rebalance(p);
    }
 
 
}
 
BNode* Search(BNode* root, int data) 
{
    if (root == NULL) 
    {
        return NULL;
    }
 
    if (root->data > data) 
    {
        return Search(root->Left, data);
    }
    else if (root->data < data) 
    {
        return Search(root->Right, data);
    }
    else return root;
 
}
 
void PrintTree(BNode* root) 
{
    if (root == NULL) return;
 
    printf(" %d", root->data);
 
    if (root->Left != NULL) PrintTree(root->Left);
 
    if (root->Right != NULL) PrintTree(root->Right);
}
 
//추가1_ 메모리 해제 메소드 (후위 순회)
void FreeTree(BNode* root) {
    if (root == NULL) return;
 
    FreeTree(root->Left);
    FreeTree(root->Right);
 
    free(root);
}
 
 
int main()
{
 
    BNode* AVLTree = NULL;
    int input;
    char sign;
 
    while (1)
    {
        scanf("%c", &sign);
        getchar();
 
        if (sign == 'i')
        {
            scanf("%d", &input);
 
            getchar();
 
            InsertAVL(&AVLTree, input);
 
        }
        else if (sign == 's')
        {
            BNode* result;
 
            scanf("%d", &input);
 
            getchar();
 
            result = Search(AVLTree, input);
 
            if (result == NULL) {
                printf("X\n");
            }
            else {
                printf("%d\n", result->data);
            }
        }
        else if (sign == 'd')
        {
            BNode* result = NULL;
 
            scanf("%d", &input);
 
            getchar();
 
            DeleteAVL(&AVLTree, input);
 
            if (del_sign == 1)
            {
                printf("X\n");
            }
            else if (del_sign == -1)
            {
                printf("%d\n", input);
            }
 
 
        }
        else if (sign == 'p')
        {
            PrintTree(AVLTree);
            printf("\n");
        }
        else if (sign == 'q')
        {
            break;
        }
 
    }
 
    free(AVLTree);
 
    return 0;
}