C언어로 이진 탐색 트리 구현하기

✅ 개요

노드 삽입

1. 루트에 주목한다. 여기서 주목하는 노드를 node라고 하자.
2. 삽입하는 key과 주목 노드 node의 키를 비교한다.
   • key = node인 경우 : 삽입을 실패하고 종료한다.
   • key < node인 경우 :
     • 왼쪽 자식 노드가 없으면, 그 자리에 노드를 삽입하고 종료한다.
     • 왼쪽 자식 노드가 있으면, 주목 노드를 왼쪽 자식 노드로 옮긴다.
   • key > node인 경우 :
     • 오른쪽 자식 노드가 없으면, 그 자리에 노드를 삽입하고 종료한다.
     • 오른쪽 자식 노드가 있으면, 주목 노드를 오른쪽 자식으로 옮긴다.
3. 2번 과정으로 돌아간다.

노드 삭제

1️⃣ 리프 노드를 삭제하는 경우

• 삭제할 노드가 부모 노드의 왼쪽 자식이라면, 부모의 왼쪽 포인터를 NULL로 한다.
• 삭제할 노드가 부모 노드의 오른쪽 자식이라면, 부모의 오른쪽 포인터를 NULL로 한다.

2️⃣ 자식 노드가 1개인 노드를 삭제하는 경우

• 삭제할 노드가 부모 노드의 왼쪽 자식이라면, 부모의 왼쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트한다.
• 삭제할 노드가 부모 노드의 오른쪽 자식이라면, 부모의 오른쪽 포인터가 삭제할 노드의 자식을 가리키도록 업데이트한다.

3️⃣ 자식 노드가 2개인 노드를 삭제하는 경우

1. 삭제할 노드의 왼쪽 서브트리에서 키값이 가장 큰 노드를 검색한다.
2. 검색한 노드를 삭제 위치로 옮긴다. 즉, 검색한 노드의 데이터를 삭제할 노드의 위치에 복사한다.
3. 옮긴 노드를 삭제한다. 이 때 자식 노드의 개수에 따라 다음을 수행한다.
   • 옮긴 노드에 자식이 없으면, 1️⃣에 따라 노드를 삭제한다.
   • 옮긴 노드에 자식이 1개만 있으면, 2️⃣에 따라 노드를 삭제한다.

---

💻 코드 구현

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

typedef struct _bstnode{
	int key;
	struct _bstnode *left;
	struct _bstnode *right;
} BSTNode;

void insertNode(BSTNode **node, int value);
BSTNode* removeNode(BSTNode *root, int value);
void inorderTraversal(BSTNode *node);
void removeAll(BSTNode **node);

int main() {
    BSTNode *root = NULL;

    insertNode(&root, 50);
    insertNode(&root, 30);
    insertNode(&root, 20);
    insertNode(&root, 40);
    insertNode(&root, 70);
    insertNode(&root, 60);
    insertNode(&root, 80);

    printf("Inorder Traversal Result : ");
    inorderTraversal(root);
    printf("\n");

    root = removeNode(root, 20);
    printf("After deleting 20: ");
    inorderTraversal(root);
    printf("\n");

    root = removeNode(root, 30);
    printf("After deleting 30: ");
    inorderTraversal(root);
    printf("\n");

    root = removeNode(root, 50);
    printf("After deleting 50: ");
    inorderTraversal(root);
    printf("\n");

    removeAll(&root);

    return 0;
}

void insertNode(BSTNode **node, int value) {
    if (*node == NULL) {
        *node = malloc(sizeof(BSTNode));
        if (*node != NULL) {
            (*node)->key = value;
            (*node)->left = NULL;
            (*node)->right = NULL;
        }
    } else {
        if (value < (*node)->key) insertNode(&((*node)->left), value);
        else if (value > (*node)->key) insertNode(&(*node)->right, value);
        else return;
    }
}

BSTNode* removeNode(BSTNode *root, int value) {
    if (root == NULL) return NULL;
    
    if (value < root->key) root->left = removeNode(root->left, value);
    else if (value > root->key) root->right = removeNode(root->right, value);
    else {
        // 1. 리프 노드를 제거하는 경우
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 2. 자식이 1개 있는 노드를 제거하는 경우
        else if (root->left != NULL && root->right == NULL) {
            BSTNode *tmp = root->left;
            free(root);
            return tmp;
        }
        else if (root->left == NULL && root->right != NULL) {
            BSTNode *tmp = root->right;
            free(root);
            return tmp;
        }
        // 3. 자식이 2개 있는 노드를 제거하는 경우
        else {
            BSTNode* predecessor = root->left;
            while (predecessor->right != NULL) predecessor = predecessor->right;
            root->key = predecessor->key;
            root->left = removeNode(root->left, predecessor->key);
        }
    }
    return root;
}

void inorderTraversal(BSTNode *node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->key);
        inorderTraversal(node->right);
    }
}

void removeAll(BSTNode **node) {
	if (*node != NULL) {
		removeAll(&((*node)->left));
		removeAll(&((*node)->right));
		free(*node);
		*node = NULL;
	}
}

코드 실행 결과