[부록]실습7주차_AVL삭제[문제3]_2차시도

@이것도 100점 안뜨길래 다시 작성, 다시 공부 :

 

#내가 놓친 부분 :

• LL회전 | RR회전 구현부_순서 : L1 | R1 의 Right, Left 부터 업데이트 하자

 

• Rebalance의 LL회전 RR회전 조건절 :

○ LL회전 조건절 : BF > 1 && GetBF((*p)->Left) >= 0

○ RR회전 조건절 : BF < -1 && GetBF((*p)->Right) <= 0

• AVL 삭제 메소드 구현 논리 순서

1_ 종료 조건 : 노드가 빈자리면, return

2_ 탐색 : 재귀

3_ 삭제대상 노드를 찾았다면,

• 삭제대상 노드가 0차 => free((*삭제대상)) =>" *삭제대상" 에 NULL 대입
• 삭제대상 노드가 1차 => 임시 노드 포인터 tmp에 NULL이 아닌 자식 보관   => free((*삭제대상)) =>" *삭제대상" 에 tmp 저장
• 삭제 대상 노드가 2차 => 임시 노드 포인터 tmp 에 FindMin노드 보관 => (*삭제대상)의 Data를 tmp->data 대입, =>DeleteNode((*t삭제대상)->RIght, tmp->data) 재귀 호출
• Rebalance() 하면서, root노드 까지 거슬러 올라가 균형 맞추기

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
//AVL 트리 구조체
typedef struct AVLBNode {
 
    int data;
    struct AVLBNode* Left;
    struct AVLBNode* Right;
 
}Node;
 
//search메소드
Node* Search(Node* p, int data) 
{
    if (p == NULL || p->data == data) return p;
 
    if (p->data > data) return Search(p->Left, data);
    else if (p->data < data) return Search(p->Right, data);
 
}
 
//CreateNode메소드
Node* CreateNode(int data) 
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->Left = NULL;
    newNode->Right = NULL;
}
 
//회전
// 
 
//LL
Node* LL(Node* L1) {
    Node* L2 = L1->Left;
    L1->Left = L2->Right;
    L2->Right = L1;
    return L2;
}
//RR
Node* RR(Node* R1) 
{
    Node* R2 = R1->Right;
    R1->Right = R2->Left;
    R2->Left = R1;
    return R2;
}
//LR
Node* LR(Node* L1) 
{
    Node* L2 = L1->Left;
    L1->Left = RR(L2);
    return LL(L1);
}
//RL
Node* RL(Node* R1) 
{
    Node* R2 = R1->Right;
    R1->Right = LL(R2);
    return RR(R1);
}
 
//노드에 대한 Height 구하는 메소드
//단말 노드 높이 : 1
//빈자리 노드 높이 : 0
int GetHeight(Node* p) 
{
    if (p == NULL) return 0;
 
    int L = GetHeight(p->Left);
    int R = GetHeight(p->Right);
 
    return  1 + ((L > R) ? L : R);
}
 
//GetBF메소드
int GetBF(Node* p) 
{
    if (p == NULL) return 0;
 
    return GetHeight(p->Left) - GetHeight(p->Right);
}
//Rebalance
void Rebalance(Node** p) 
{
    int BF = GetBF((*p));
 
    if (BF > 1 && GetBF((*p)->Left) >= 0) 
    {
        *p = LL(*p);
    }
    else if (BF > 1 && GetBF((*p)->Left) < 0)
    {
        *p = LR(*p);
    }
    else if (BF < -1 && GetBF((*p)->Right) <= 0)
    {
        *p = RR(*p);
    }
    else if (BF < -1 && GetBF((*p)->Right) > 0)
    {
        *p = RL(*p);
    }
}
 
void InsertAVL(Node** p,int data) 
{
    if ((*p) == NULL) 
    {
        (*p) = CreateNode(data);
        return;
    }
 
    if ((*p)->data > data) InsertAVL(&((*p)->Left), data);
    else if ((*p)->data < data) InsertAVL(&((*p)->Right), data);
    else return;
 
    Rebalance(p);
 
}
 
Node* findMin(Node* p) 
{
    Node* tmp = p;
    while (tmp->Left != NULL) {
        tmp = tmp->Left;
    }
 
    return tmp;
}
 
// AVL 트리에서 노드를 삭제하는 함수
void deleteNode(Node** root, int key) {
    if (*root == NULL)
        return *root;
 
    // 키가 현재 노드보다 작은 경우 왼쪽 서브트리에서 삭제
    if (key < (*root)->data)
        deleteNode(&(*root)->Left, key);
 
    // 키가 현재 노드보다 큰 경우 오른쪽 서브트리에서 삭제
    else if (key > (*root)->data)
        deleteNode(&(*root)->Right, key);
 
    // 키가 현재 노드와 같은 경우 (삭제할 노드를 찾은 경우)
    else {
        //삭제대상 노드가 0차인 경우
        if ((*root)->Left == NULL && (*root)->Right == NULL) 
        {
            free(*root);
            (*root) = NULL;
        }
        //삭제대상 노드가 1차인 경우
        else if ((*root)->Left == NULL) 
        {
            Node* tmp = (*root)->Right;
            free(*root);
            *root = tmp;
        }
        else if ((*root)->Right == NULL) 
        {
            Node* tmp = (*root)->Left;
            free(*root);
            *root = tmp;
        }
        else 
        {
            Node* tmp = findMin((*root)->Right);
            (*root)->data = tmp->data;
            deleteNode(&((*root)->Right), tmp->data);
        }
    }
 
    if ((*root) != NULL) Rebalance(root);
 
}
 
void PrintPreOrder(Node* p) 
{
    if (p == NULL) return;
 
    printf(" %d", p->data);
 
    if (p->Left != NULL) PrintPreOrder(p->Left);
    if (p->Right != NULL) PrintPreOrder(p->Right);
 
}
 
int main()
{
    Node* root = NULL;
    int data;
    char command;
 
    while (1)
    {
        scanf("%c", &command);
 
        if (command == 'i')
        {
            scanf("%d", &data);
            InsertAVL(&root, data);
 
        }
        else if (command == 's')
        {
            scanf("%d", &data);
            Node* search = Search(root, data);
            if (search == NULL) {
                printf("X\n");
            }
            else {
                printf("%d\n", search->data);
            }
 
        }
        else if (command == 'd') 
        {
            scanf("%d", &data);
            Node* search = Search(root, data);
 
            if (search == NULL) {
                printf("X\n");
            }
            else 
            {
                deleteNode(&root, data);
                printf("%d\n", data);
            }
        }
        else if (command == 'p')
        {
            PrintPreOrder(root);
            printf("\n");
        }
        else if (command == 'q')
        {
            break;
        }
 
 
    }
 
 
    return 0;
}