[C언어]53일차-이진트리 노드삽입 삭제 (이것이 c 자료구조와 알고리즘이다)

[C언어]53일차-이진트리 노드삽입 삭제 (이것이 c 자료구조와 알고리즘이다)

 

노드 삽입 연산의 핵심은 새 노드가 삽입될 곳이 어디인지를 찾아 내는 일이다.

 

다시 말해, 새 노드가 삽입될 곳을 이진 탐색으로 찾아내야 한다.

 

이진 탐색으로 새 노드를 연결할 부모 노드를 찾아낸 후 그곳에 노드를 살포시 내려놓으면 된다.

 

숫자 14를 아래 이진 트리에 삽입해 보기

 

14는 23보다 작으므로 23의 왼쪽 트리에 위치해야 한다.

 

그리고 11보다 크므로 11의 오른쪽 하위 트리에 위치 해야 한다.

 

마침 11의 오른쪽 자식 트리가 없으니 여기에 새 노드 14를 연결하면 된다.

 

 

 

노드 삭제 연산

 

노드 삭제를 할때는 2가지 케이스가 있다.

 

[케이스 1]

 

이진 탐색 트리에서 임의의 노드를 삭제하려면 먼저 삭제할 노드를 찾아야 한다. (이진 트리 탐색 이용)

 

이진 탐색을 통해 노드가 어디에 있는지 알아낸 후에는 노드를 트리에서 떼어낸다.

 

이때 떼어내는 노드가 '잎 노드'라면 아무 걱정 없이 부모 노드에서 자식 노드의 포인터를 NULL로 봉합하고 삭제한 노드의 주소를 반환하면 작업이 깔끔하게 마무리 된다.

 

14노드를 제거 하는 예제

 

 

 

 

[케이스 2]

 

1.왼쪽과 오른쪽 중 어느 한쪽 자식 노드만 갖고 있는 경우.

2.양쪽 자식 노드를 모드 갖고 있는 경우

 

 

1번 경우는 삭제할 노드의 자식을 -> 삭제할 노드의 부모에 연결시키기만 하면 된다.

 

아래에 139를 삭제하는 과정을 보자.

 

 

 

 

 

 

 

2번 경우에서 11 노드가 제거된 빈자리를 어떻게 연결해야 이진 탐색 트리의 특성을 가장 효율적으로 유지할 수 있을까?

 

답은 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드를 삭제된 노드의 위치에 옮겨놓는것이다.

 

삭제된 11노드의 오른쪽 하위 트리에서 가장 작은 13 노드를 옮겨 11 노드가 있던 자리에 놓으면 된다.

 

 

 

'최솟값 노드'가 자식이 없는 경우라면 이렇게 노드를 빈자리에 옮겨 놓는 것만으로 작업이 완료된다.

 

 

하지만 자식이 있는 경우에 처리해야 할 일이 더 있다.

 

최소 값 노드는 자식이 있어도 왼쪽 자식은 없고, 오른쪽 자식만 있다.

 

그 이유는 왼쪽 자식이 있으면 자기보다 작은 값을 가진 노드가 하위 트리에 있다는 뜻이기 때문이다.

 

그래서 최솟값 노드의 오른쪽 자식을 최솟값 노드의 원래 부모에게 연결함으로써 삭제 작업이 모두 끝난다.

 

15노드를 16노드의 왼쪽 자식으로 만들면 된다.

 

 

 

 

구현 메서드

 

 

 

 

 

 

 

내가 구현한 코드

#include <string.h>
#include <stdlib.h>
#include <stdio.h>


typedef struct _Node{
    int data;
    struct _Node* leftNode;
    struct _Node* rightNode;
}Node;



Node* createNode(int newData);
Node* searchNode(Node* Current, int target);
Node* removeNode(Node* Tree, Node* Parent, int target);

void insertNode(Node* Tree, Node* child);

void preOrder(Node* Tree);
void inOrder(Node* Tree);
void postOrder(Node* Tree);


Node* searchParentNode(Node* Parent, Node* TargetNode);
Node* removeFromParentNode(Node* Parent, Node* TargetNode);
Node* removeHavingOneChildNode(Node* Parent, Node* TargetNode , Node* TargetNodeChild);
Node* removeHavingTwoChildNode(Node* Tree,Node* Parent, Node* TargetNode);

Node* findMinNode(Node* Parent);


//MARK: 이진탐색트리 노드 생성
Node* createNode(int newData){
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("메모리 할당에 실패했습니다.");
        return NULL;
    }
    newNode->data = newData;
    newNode->leftNode = NULL;
    newNode->rightNode = NULL;
    return newNode;
}

//MARK: 이진트리 탐색
Node* searchNode(Node* Current, int target){
    
    //중앙 요소를 찾아 좌우의 대소를 비교하여 탐색 범위를 정하고,
    //또 다시 중앙 요소를 찾아 좌우의 대소를 비교하는 과정
    if (Current == NULL) {
        printf("찾는 값이 없습니다.\n");
        return NULL;
    }
    
    if (Current->data == target) {
        printf("찾았습니다.\n");
        return Current;
    }
    
    //왼쪽 탐색
    if (Current->data > target) {
       
        return searchNode(Current->leftNode, target);
    
    //오른쪽 탐색
    }else if(Current->data < target){
        return searchNode(Current->rightNode, target);
    }

    return NULL;
}

//MARK: 삽입
void insertNode(Node* Tree, Node* Child){
    
    //새 노드가 삽입될 곳을 이진 탐색으로 찾아야 한다.
    
    //Tree의 값과 child의 값을 비교한다.
    
    //Child의 값이 Tree보다 작으면
    //Tree의 왼쪽 자식을 체크한다. NULL아니면
    //왼쪽 자식을 Tree에 할당해서 다시 비교한다.
    //NULL 이면 왼쪽 자식이 된다.
    
    
    //Child의 값이 Tree보다 크면
    //Tree의 오른쪽 자식이 NULL이 아니면 -
    //오른쪽 자식을 Tree에 할당해서 다시 비교한다.
    //NULL 이면 Tree의 오른쪽 자식이 된다.
    
    if (Tree == NULL) {
        return;
    }
    
    if (Tree->data > Child->data) {
        
        if (Tree->leftNode != NULL) {
            insertNode(Tree->leftNode, Child);
        }else{
            Tree->leftNode = Child;
            return;
        }
        
    } else {
        if (Tree->rightNode != NULL) {
            insertNode(Tree->rightNode, Child);
        }else{
            Tree->rightNode = Child;
            return;
        }
    }
    
}

//MARK: 전위순회
void preOrder(Node* Tree){
    if (Tree == NULL) {
        return;
    }
    //뿌리노드 출력
    printf("[%d] " , Tree->data);
    preOrder(Tree->leftNode);
    preOrder(Tree->rightNode);
}

//MARK: 중위순회
void inOrder(Node* Tree){
    if (Tree == NULL) {
        return;
    }
    
    inOrder(Tree->leftNode);
    printf("[%d] " , Tree->data); //뿌리노드 출력
    inOrder(Tree->rightNode);
}

//MARK: 후위순회
void postOrder(Node* Tree){
    if (Tree == NULL) {
        return;
    }
    postOrder(Tree->leftNode);
    postOrder(Tree->rightNode);
    printf("[%d] " , Tree->data); //뿌리노드 출력
}



//MARK: 부모노드 찾기
Node* searchParentNode(Node* Parent, Node* TargetNode){
    
    if (Parent == NULL) {
        return NULL;
    }
    
    //왼쪽 탐색
    if (Parent->data > TargetNode->data) {
        
        if (Parent->leftNode->data == TargetNode->data) {
            return Parent;
        }else{
            return searchParentNode(Parent->leftNode, TargetNode);
        }
        
    //오른쪽 탐색
    }else if(Parent->data < TargetNode->data){
    
        if (Parent->rightNode->data == TargetNode->data) {
            return Parent;
        }else{
            return searchParentNode(Parent->rightNode, TargetNode);
        }
    }
    
    return NULL;
}


//MARK: 부모노드 자식삭제
Node* removeFromParentNode(Node* Parent, Node* TargetNode){

    if (Parent == NULL) {
        return NULL;
    }
    //왼쪽 탐색
    if (Parent->data > TargetNode->data) {
        
        if (Parent->leftNode->data == TargetNode->data) {
            Parent->leftNode = NULL;
            printf("%d 삭제완료\n\n" , TargetNode->data);
            return Parent;
        }else{
            removeFromParentNode(Parent->leftNode, TargetNode);
        }
        
    //오른쪽 탐색
    }else if(Parent->data < TargetNode->data){
    
        if (Parent->rightNode->data == TargetNode->data) {
            Parent->rightNode = NULL;
            printf("%d 삭제완료\n\n" , TargetNode->data);
            return Parent;
        }else{
            removeFromParentNode(Parent->rightNode, TargetNode);
        }
    }
    
    return NULL;
}

//MARK: 부모노드 자식삭제 2
//삭제할 노드가 자식이 하나만 있는 경우
Node* removeHavingOneChildNode(Node* Parent, Node* TargetNode , Node* TargetNodeChild){
    
    if (Parent == NULL) {
        return NULL;
    }
    //왼쪽 탐색
    if (Parent->data > TargetNode->data) {
        
        if (Parent->leftNode->data == TargetNode->data) {
            Parent->leftNode = TargetNodeChild;
            printf("%d 삭제완료\n\n" , TargetNode->data);
            return Parent;
        }else{
            removeFromParentNode(Parent->leftNode, TargetNode);
        }
        
    //오른쪽 탐색
    }else if(Parent->data < TargetNode->data){
    
        if (Parent->rightNode->data == TargetNode->data) {
            Parent->rightNode = TargetNodeChild;
            printf("%d 삭제완료\n\n" , TargetNode->data);
            return Parent;
        }else{
            removeFromParentNode(Parent->rightNode, TargetNode);
        }
    }
    
    return NULL;
}


//MARK: 부모노드 자식삭제 3
//부모의 자식이 두개 있을 경우
Node* removeHavingTwoChildNode(Node* Tree , Node* Parent, Node* TargetNode){
    
    if (Parent == NULL) {
        return NULL;
    }
    //왼쪽 탐색
    if (Parent->data > TargetNode->data) {
        
        if (Parent->leftNode->data == TargetNode->data) {
            
            Node* minNode = findMinNode(TargetNode->rightNode);
            printf(">> min data : %d\n", minNode->data);

            if (minNode->rightNode != NULL) {
                
                Node* minNodeRightChild = minNode->rightNode;
                Node* minNodeParent = searchParentNode(Tree, minNode);
                minNodeParent->leftNode = minNodeRightChild;
                
                minNode->leftNode = Parent->leftNode->leftNode;
                minNode->rightNode = Parent->leftNode->rightNode;
                Parent->leftNode = minNode;
                
            }else{
                
                Node* minNodeParent = searchParentNode(Tree, minNode);
                minNodeParent->leftNode = NULL;
                
                minNode->leftNode = Parent->leftNode->leftNode;
                minNode->rightNode = Parent->leftNode->rightNode;
                Parent->leftNode = minNode;
            }
            
            printf("%d 삭제완료\n\n" , TargetNode->data);
            
            return Parent;
            
        }else{
            return removeHavingTwoChildNode( Tree , Parent->leftNode, TargetNode);
        }
        
    //오른쪽 탐색
    }else if(Parent->data < TargetNode->data){
    
        if (Parent->rightNode->data == TargetNode->data) {
           
            Node* minNode = findMinNode(TargetNode->rightNode);
            printf(">>> min data : %d\n", minNode->data);
            
            if (minNode->rightNode != NULL) {
                
                Node* minNodeRightChild = minNode->rightNode;

                Node* minNodeParent = searchParentNode(Tree, minNode);
                minNodeParent->leftNode = minNodeRightChild;
                
                minNode->leftNode = Parent->rightNode->leftNode;
                minNode->rightNode = Parent->rightNode->rightNode;
                Parent->rightNode = minNode;
                
            }else{

                Node* minNodeParent = searchParentNode(Tree, minNode);
                minNodeParent->leftNode = NULL;
                
                minNode->leftNode = Parent->rightNode->leftNode;
                minNode->rightNode = Parent->rightNode->rightNode;
                Parent->rightNode = minNode;
            }
        
            return Parent;
        }else{
            return removeHavingTwoChildNode(Tree , Parent->rightNode, TargetNode);
        }
    }
    
    return NULL;
}



//MARK: 최소값 찾기
Node* findMinNode(Node* Parent){
    
    if (Parent == NULL) {
        return NULL;
    }
    Node* Current = Parent;
    while (Current->leftNode != NULL) {
        Current = Current->leftNode;
    }
    return Current;
}

//MARK: 삭제
Node* removeNode(Node* Tree, Node* Parent, int target){
    
    Node* removeNode = NULL;
    
    //먼저 임의의 노드에서 삭제할 노드를 찾아야 한다.
    removeNode = searchNode(Tree, target);
    
    //이진 탐색을 통해 노드가 어디에 있는지 알아낸 후 노드를 트리에서 떼어 낸다.
    //떼어낸 노드가 잎 노드라면 부모 노드에서 자식 노드의 포인터를 NULL 할당해준다.
    if (removeNode->leftNode == NULL && removeNode->rightNode == NULL) {
        return removeFromParentNode(Tree, removeNode);
    }
    //삭제할 노드가 한쪽 자식을 가지고 있을 경우
    //삭제할 노드의 부모에 삭제할 노드의 자식을 연결 시킨다.
    else if(removeNode->leftNode != NULL && removeNode->rightNode == NULL){
        
        return removeHavingOneChildNode(Tree, removeNode, removeNode->leftNode);
    }
    else if(removeNode->leftNode == NULL && removeNode->rightNode != NULL){
        
        return removeHavingOneChildNode(Tree, removeNode, removeNode->rightNode);
    
    //삭제할 노드가 자식 두개를 모두 가지고 있는경우
    //삭제된 노드의 오른쪽 트리에서 가장 작은 값을 가지고 있는 노드를 찾아서
    //삭제된 위치에 옮겨둔다.
    //옮겨질 최솟값 노드의 자식이 있다면 그 자식은 최솟값 노드의 부모와 연결 시킨다.
    }else if (removeNode->leftNode != NULL && removeNode->rightNode != NULL){
        
        printf("삭제할 노드가 자식 두개를 모두 가지고 있는경우\n");
        return removeHavingTwoChildNode(Tree, Parent, removeNode);
        

    }
    return NULL;
}


//MARK: main
int main(int argc, const char * argv[]) {
    
    Node* root = createNode(23);
    
    Node* eleven = createNode(11);
    Node* oneThreeNine = createNode(139);
    
    Node* one = createNode(1);
    Node* sixteen = createNode(16);
    
    Node* sixteenSeven = createNode(67);

    Node* thirTeen = createNode(13);
    Node* twelVe = createNode(20);
    Node* fiTeen = createNode(15);
    
    
    insertNode(root, eleven);
    insertNode(root, oneThreeNine);
    
    insertNode(root, one);
    insertNode(root, sixteen);
    
    insertNode(root, sixteenSeven);

    insertNode(root, thirTeen);
    insertNode(root, twelVe);
    insertNode(root, fiTeen);
    
    
    
//    Node* findNode = searchNode(root, 34);
//    if (findNode == NULL) {
//        printf("값을 못찾았습니다..\n");
//    }else{
//        printf("찾은값 : %d \n" , findNode->data);
//    }
    

    printf("\n");
    printf("\n");
    preOrder(root);
    printf("\n");
    
    
//    insertNode(root,  createNode(34));
//    preOrder(root);
//    printf("\n");
//    
//    insertNode(root,  createNode(68));
//    preOrder(root);
//    printf("\n");
//    
//
    removeNode(root, root, 11);
    preOrder(root);
    printf("\n");
    printf("\n");
    
    
    removeNode(root, root, 13);
    preOrder(root);
    printf("\n");
    printf("\n");
//
//    removeNode(root, root, 14);
//    preOrder(root);
//    printf("\n");
//    
//
    
//    Node* ParentNode = searchParentNode(root, eleven);
//    printf("부모노드 : %d\n" , ParentNode->data);
//    
//    
//    removeNode(root, root, 139);
//    preOrder(root);
//    printf("\n");
//
//    Node* minNode = findMinNode(root);
//    printf("%d\n" , minNode->data);
    
    return 0;
}

 

 

 

✅ 전체 삭제 로직 — 핵심 요약 (쉽게)

 

BST(Binary Search Tree) 노드 삭제는 3가지 상황이 있어:

 

---

 

① 삭제할 노드가 자식이 0개 (leaf 노드)

 

→ 그냥 부모의 왼쪽/오른쪽 포인터를 NULL로 하면 끝.

 

예:

   23
  /
 11   ← 삭제

 

---

 

② 삭제할 노드가 자식이 1개

 

→ 부모에게 “내 자식”을 대신 연결.

 

예:

 23
 /
11         ← 삭제
 \
 16   ← 이 노드를 부모와 연결

 

---

 

③ 삭제할 노드가 자식이 2개

 

→ 오른쪽 서브트리에서 가장 작은 노드(minNode) 를 찾아서

→ 삭제할 노드 자리로 옮긴다.

 

예:

    23
   /
  11     ← 삭제
   \
   16
    \
    20

16의 오른쪽에서 가장 작은 값 20이 11 자리로 올라간다.

 

---

 

❗ 너의 코드에서 핵심 문제들 (쉬운 설명)

 

 

🚨 1) Parent->leftNode->data == TargetNode->data

 구문이 위험함

 

왜냐하면:

• Parent->leftNode 가 NULL이면
• → Parent->leftNode->data 접근하면 세그폴트 발생.

 

항상 NULL 체크가 먼저 있어야 함!

 

 

🚨 2) removeHavingOneChildNode에서 실수 있음

 

코드:

removeFromParentNode(Parent->leftNode, TargetNode);

여기서 removeFromParentNode를 호출하는데,

실제로는 “1개 자식을 가진 노드” 방식으로 삭제해야 한다.

 

즉,child 1개 삭제 함수 안에서 leaf 삭제 함수를 호출하는 버그가 있음.

 

---

 

🚨 3) removeHavingTwoChildNode 로직이 너무 복잡하고 여러 문제 있음

문제점

• minNode의 부모가 항상 leftNode에 minNode가 있다고 가정
• 하지만 minNode가 오른쪽 자식일 수도 있음
• searchParentNode 로 parent를 찾는데 이것도 잘못 동작할 가능성 높음
• 자식 연결 로직이 중복되고 복잡함
• 실제 BST 삭제 표준 방식보다 훨씬 에러날 가능성이 높음

 

👍 쉬운 해결책: 표준 BST 삭제 알고리즘 써라

 

너무 복잡하게 parent를 찾고, child를 붙이고 할 필요 없어.

 

표준 BST 삭제는 단 30줄이야.

 

핵심 아이디어

• 현재 노드 포인터를 그대로 바꿔주면 Parent 필요 없음
• left/right 포인터만 재귀로 연결하면 깔끔하게 해결됨

 

 

🎯 너의 삭제 로직 중 “정상적으로 돌아가는 부분”

✔ delete case1 (leaf 삭제)

removeFromParentNode

기능 자체는 맞다.

BUT null 체크 없어 안전하지 않음.

 

 

✔ delete case2 (자식 1개)

removeHavingOneChildNode

아이디어는 맞는데

부모를 찾아서 바꿔주는 로직이 잘못 작성됨.

 

 

✔ delete case3 (자식 2개)

 

removeHavingTwoChildNode

아이디어는 맞지만

구현이 매우 불안정.

minNode 부모 찾기, 연결 과정 모두 예외 발생 가능.

 

🔧 결론: 코드가 “돌아갈 수는 있지만” 구조적으로 매우 위험

주요 위험 요인:

• NULL 체크 부족
• 부모 탐색과 포인터 갱신 로직이 너무 복잡
• minNode 제거 후 포인터 연결이 위험
• 코드 중복이 많아 유지보수 어려움