(15)[Chapter6]AVL 트리_삭제 메소드(작성중)

##노트정리

##중요 핵심 개념 :
    AVL트리_Delete() 구현 논리 순서 :

1. 해당 노드에서 최솟값 노드 탐색 메소드
2. Delete()메소드 구현 논리순서 :

• 종료조건 : 빈노드 도달 || 처음부터 빈트리 => 종료
• 탐색 : 재귀
• 삭제대상 찾았을 때, Case 분류 (2가지 : 0,1차 || 2차) 

Case_1) 삭제대상 (0,1차) => *root를 temp에 보관, *root를 자손에 이동 , temp 메모리 해제

Case_2) ★삭제대상 (2차)

=> *root의 오른쪽노드부터 최솟값노드 탐색

=> 최솟값 노드를 temp에 보관(지정)

=> temp노드의 data를 *root노드에 data 업데이트

=> ★삭제대상의 오른쪽부터 temp->data의 노드를 Delete() 재귀

• 삭제대상 노드자리부터 쭈르르 위로 Rebalnce 재귀 작동 

## temp->data노드를 그냥 free가 아닌, 재귀를 하는 이유 :
temp->data 노드한테도 자손이 있을 수 있기 때문

##코드

// 트리에서 최소값을 찾는 함수
AVLBNode* GetMinValueNode(AVLBNode* node) {
    AVLBNode* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}
 
// 노드 삭제 메소드
void DeleteAVL(AVLBNode** root, int data) {
    if (*root == NULL) {
        return;
    }
 
    // 1. BST 삭제 방식으로 노드 삭제
    if (data < (*root)->data) {
        DeleteAVL(&((*root)->left), data);
    }
    else if (data > (*root)->data) {
        DeleteAVL(&((*root)->right), data);
    }
    else {
      //0,1차일 때,
        // 현재 노드가 삭제할 노드
        if ((*root)->left == NULL) {
            AVLBNode* temp = *root;
            *root = (*root)->right;
            free(temp);
        }
        else if ((*root)->right == NULL) {
            AVLBNode* temp = *root;
            *root = (*root)->left;
            free(temp);
        }
        else {//2차일 때,
      
            AVLBNode* temp = GetMinValueNode((*root)->right);
            (*root)->data = temp->data;
            DeleteAVL(&((*root)->right), temp->data);
        }
    }
 
    // 2. 균형 조정
    if (*root != NULL) {
        Rebalance(root);
    }
}

##AVL트리 삽입_삭제_전체코드 :

 

#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;
 
//탐색
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;
    }
}
 
//회전
AVLBNode* LL(AVLBNode* Parent)//LL
{
    AVLBNode* child = Parent->left;
 
    Parent->left = child->right;
 
    child->right = Parent;
 
    return child;
 
}
 
AVLBNode* RR(AVLBNode* Parent)//RR
{
    AVLBNode* child = Parent->right;
 
    Parent->right = child->left;
 
    child->left = Parent;
 
    return child;
}
 
AVLBNode* LR(AVLBNode* Parent)//LR
{
    AVLBNode* child = Parent->left;
    //RR
    Parent->left = RR(child);
    //LL
    return LL(Parent);
}
 
AVLBNode* RL(AVLBNode* Parent) //RL
{
    AVLBNode* child = Parent->right;
 
    //LL
    Parent->right = LL(child);
    //RR
    return RR(Parent);
}
 
//height
int GetHeight(AVLBNode* root)
{
    int height = 0;
 
    if (root == NULL) return height;
 
    int left_height = GetHeight(root->left);
    int right_height = GetHeight(root->right);
 
 
    height = ((left_height > right_height) ? left_height : right_height) + 1;
 
    return height;
}
 
//BF
int GetBF(AVLBNode* root)
{
    return GetHeight(root->left) - GetHeight(root->right);
}
 
//임의의 한 노드 균형 맞춰주는 메소드
void ReBalance(AVLBNode** root)
{
    int BF = GetBF(*root);
 
    if (BF > 1) 
    {
        //실수1_ 회전후, 반환 값이 없다.
        //실수2_ 회전 함수 매개변수 잘못 넣음
        if (GetBF((*root)->left)>0) 
        {
            (*root) = LL(*root);
        }
        else 
        {
            (*root) = LR(*root);
        }
    }
    else if (BF < -1) 
    {
        if (GetBF((*root)->right) < 0)
        {
            (*root) = RR(*root);
        }
        else
        {
            (*root) = RL(*root);
        }
    }
 
    return;
}
 
//AVL 삽입 메소드
void InsertAVL(AVLBNode** root, element data)
{
    if (*root == NULL) 
    {
        *root = (AVLBNode*)malloc(sizeof(AVLBNode));
        (*root)->data = data;
        (*root)->left = NULL;
        (*root)->right = NULL;
 
        return;
    }
 
    if ((*root)->data > data) 
    {
        InsertAVL(&((*root)->left), data);
    }
    else if ((*root)->data < data)
    {
        InsertAVL(&((*root)->right), data);
    }
    else 
    {
        printf("%d값은 트리에 이미 존재합니다.\n",data);
        return;
    }
    
    ReBalance(root);
 
}
 
//최솟값 노드 찾기
AVLBNode* MinNode(AVLBNode* p)
{
    //if (p == NULL) return p;
    
    AVLBNode* C = p;
 
    while (C->left != NULL) C = C->left;
 
    return C;
}
 
//AVL 삭제 메소드
void DeleteAVL(AVLBNode** root, element data)
{
    if (*root == NULL) 
    {
        printf("삭제할 %d값이 트리에 존재하지 않습니다.\n",data);
        return;
    }
 
    if ((*root)->data > data) 
    {
        DeleteAVL(&((*root)->left), data);
    }
    else if ((*root)->data < data)
    {
        DeleteAVL(&((*root)->right), data);
    }
    else {//실수3_삭제대상을 찾았을 때만, 삭제작업 시작
 
        //0차 1차일때, => 그냥 계승
        if ((*root)->left == NULL)
        {
            AVLBNode* tmp = *root;
            *root = (*root)->right;
            free(tmp);
        }
        else if ((*root)->right == NULL)
        {
            AVLBNode* tmp = *root;
            *root = (*root)->left;
            free(tmp);
        }
        else //2차일 때, =>삭제대상보다는 큰 노드 중 최솟값 노드와 data 교환 => 최솟값 노드를 삭제
        {
            AVLBNode* tmp = MinNode((*root)->right);
            (*root)->data = tmp->data;
            DeleteAVL(&((*root)->right), tmp->data);
 
        }
    }
    //★NULL이 아닌놈만 균형잡기
    if(*root!=NULL) ReBalance(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 트리
    InsertAVL(&AVL_root, 50);
    InsertAVL(&AVL_root, 60);
    InsertAVL(&AVL_root, 70);
    InsertAVL(&AVL_root, 90);
    InsertAVL(&AVL_root, 80);
    InsertAVL(&AVL_root, 77);
    InsertAVL(&AVL_root, 75);
    InsertAVL(&AVL_root, 73);
    InsertAVL(&AVL_root, 72);
 
    printf("AVL Tree InOrder:\n");
    InOrder(AVL_root);
    printf("\n");
 
    DeleteAVL(&AVL_root, 80);
 
    printf("AVL Tree InOrder:\n");
    InOrder(AVL_root);
    printf("\n");
 
    return 0;
}