[부록]실습7주차_AVL삽입_[문제2]_2차시도

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

#내가 놓친 부분 :

• 요소1 : Rebalance 처리 문제_ LL 회전 | RR 회전 | LR 회전 | RL 회전 조건문 처리할때, 

1_ 전부 if로 다 따로 적기 (전에는 LL LR | RL RR 분류 뒤 => 자식의 노드 BF로 Case분류 2번함)

2_ else 처리 해야함

• 요소2 : InsertAVL()처리 문제 :

1_ 빈자리 도달 or 중복된 data가 이미 있을 시 => return 처리 

2_ 1_을 처리후, rebalance로 함수 스택 반환되면서 root노드로 도달할때까지 rebalance 검사하기

• 재귀함수 / 비재귀함수 차이 : 재귀함수로 구현했을 때는 조건문 if랑 else if에 민감할 필요가 있다.

- 순회할 때, else (X)

- InsertAVL / Search 메소드 할 떄, else (O)

• 요소3 : Heigjt 함수의 삼항 연산자 처리

return 1+ ( (L > R) ? L : R )

• 요소4 : 전위 순회 출력 메소드 :

노드 데이터 출력 띄어쓰기 " %d" (X) , "%d " (O) 

 

# 전체 코드 :

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
typedef struct _AVLBTree {
 
    int data;
    struct _AVLBTree* Left;
    struct _AVLBTree* Right;
 
}BNode;
 
BNode* CreateNode(int data) 
{
    BNode* newNode = (BNode*)malloc(sizeof(BNode));
    newNode->data = data;
    newNode->Left = NULL;
    newNode->Right = NULL;
 
    return newNode;
}
 
//회전 메소드
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);
}
 
//해당 노드에 대한 높이 구하는 메소드
int GetHeight(BNode* p)
{
    int height = 0;
    if (p == NULL)return height;
 
    int L = GetHeight(p->Left);
    int R = GetHeight(p->Right);
 
    return (L > R) ? L + 1 : R + 1;
}
 
//해당 노드에 대한 Bh를 구하는 메소드
int GetBH(BNode* p)
{
    if (p == NULL) return 0;
 
    return GetHeight(p->Left) - GetHeight(p->Right);
}
 
//중요 1_Rebalance 처리문제
// => 결론 LL|RR|LR|RL 모두 따로 if 적기
// => else 처리로 모두 해야함
void Rebalance(BNode** p, int data)
{
    int BH = GetBH(*p);
    //LL
    if (BH > 1 && GetBH((*p)->Left) > 0) {
        *p = LL(*p);
    }
    //LR
    else if (BH > 1 && GetBH((*p)->Left) < 0) {
        *p = LR(*p);
    }
    //RR
    else if (BH < -1 && GetBH((*p)->Right) < 0) {
        *p = RR(*p);
    }
    //RL
    else if (BH < -1 && GetBH((*p)->Right)>0) {
        *p = RL(*p);
    }
 
}
 
BNode* search(BNode* root, int key) {
    if (root == NULL || root->data == key)
        return root;
 
    if (key < root->data)
        return search(root->Left, key);
    else if (key > root->data)
        return search(root->Right, key);
}
 
 
//삽입 메소드
void InsertAVL(BNode** p, int data) {
 
    //중요 2
    if ((*p) == NULL) {
        (*p) = CreateNode(data);
        //중요 2_1_ 여기 return 처리 해야함
        return;
    }
 
 
    if ((*p)->data > data) {
        InsertAVL(&((*p)->Left), data);
    }
    else if ((*p)->data < data) {
        InsertAVL(&((*p)->Right), data);
    }
    else {
        printf("중복\n");
        return;
    }
 
    //중요 2_2 삽입 후, 균형을 맞춘 후 결과를 반환해야 함
    Rebalance(p ,data);
 
}
 
void preOrder(BNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->Left);
        preOrder(root->Right);
    }
}
 
// 메인 함수
int main() {
    BNode* root = NULL;
    char command;
    int key;
 
    while (1) {
        scanf(" %c", &command);
 
        if (command == 'i') {
            // 삽입
            scanf("%d", &key);
            InsertAVL(&root, key);  // 이중 포인터 사용
        }
        else if (command == 's') {
            // 탐색
            scanf("%d", &key);
            BNode* result = search(root, key);
            if (result != NULL) {
                printf("%d\n", result->data);
            }
            else {
                printf("X\n");
            }
        }
        else if (command == 'p') {
            // 전위 순회 출력
            preOrder(root);
            printf("\n");
        }
        else if (command == 'q') {
            // 종료
            break;
        }
    }
 
    return 0;
}