[C언어] 이진 탐색 트리(Binary Search Tree) 구현 실습하기

이진 탐색 트리(Binary Search Tree) 구현 실습하기

이번 포스트에서는 이진 탐색 트리(Binary Search Tree, BST) 라는 자료구조를 직접 구현해보는 시간을 가져보려고 합니다. 이진 탐색 트리는 왼쪽 서브트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브트리의 모든 값이 부모 노드보다 큰 구조를 갖는 이진 트리인데요. 그렇다면 이러한 이진 탐색 트리에서는 노드들을 어떻게 생성하고, 어떻게 탐색하며, 또 어떻게 삭제할 수 있을까요?

사실 문제에서는 기본적으로 삽입 함수만 제공되지만, 저는 실습을 진행하기에 앞서 C언어로 이진 탐색 트리를 더 깊이 이해하기 위해 탐색(search)과 삭제(delete)같은 기본 연산 함수들도 직접 추가해보았습니다. 구조가 처음엔 막막하게 느껴질 수 있지만, 이번 실습을 통해 이진 탐색 트리의 동작 원리를 구현하며 개념을 자연스럽게 익혀보면 좋겠습니다.

필요한 구조체, 함수 정의하기

구조체

BSTNode: (struct) 이진 탐색 트리 노드 구조체
- item: (int field) 노드의 값
- *left: (pointer field) 왼쪽 자식 노드 주소
- *right: (pointer field) 오른쪽 자식 노드 주소

함수 (추천 구현 순서)

void insertBSTNode(BSTNode **node, int value): 이진 탐색 트리에 새로운 값을 삽입
BSTNode *searchBSTNode(BSTNode *node, int value): 이진 탐색 트리에서 주어진 값을 가진 노드를 탐색
void deleteBSTNode(BSTNode **node, int value): 이진 탐색 트리에서 주어진 값을 가진 노드를 삭제
void removeAll(BSTNode **node): 이진 탐색 트리 전체 노드를 삭제

전체 실습 코드

이진 탐색 트리 구현 실습용 뼈대 코드입니다. 각 함수에는 간단한 힌트가 주석으로 포함되어 있어, 스스로 고민하고 구현해볼 수 있게끔 되어 있습니다. 칠판이나 노트에 그림을 그려 보면서 기본 함수들을 하나씩 구현해 보세요.

//////////////////////////////////////////////////////////////////////////////////

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

///////////////////////////////////////////////////////////////////////////////////

typedef struct _bstnode{
	int item;
	struct _bstnode *left;
	struct _bstnode *right;
} BSTNode;   // You should not change the definition of BSTNode

///////////////////////////////////////////////////////////////////////////////////

// 삽입
void insertBSTNode(BSTNode **node, int value);
// 탐색
BSTNode* searchBSTNode(BSTNode *node, int value);
// 삭제
void deleteBSTNode(BSTNode **node, int value);
// 전체 트리 메모리 해제
void removeAll(BSTNode **node);

/////////////////// 이진 탐색 트리 테스트 프로그램 ///////////////////

int main()
{
	int c, i;
	c = 1;

	BSTNode *root = NULL;

	printf("1: Insert an integer into the binary search tree;\n");
	printf("2: Search for a value in the binary search tree;\n");
	printf("3: Delete a value from the binary search tree;\n");
	printf("4: Remove the entire binary search tree;\n");
	printf("0: Quit;\n");

	while (c != 0)
	{
		printf("\nPlease input your choice(0~4): ");
		scanf("%d", &c);

		switch (c)
        {
            case 1:
                printf("Input an integer to insert: ");
                scanf("%d", &i);
                insertBSTNode(&root, i);
                break;

            case 2:
                printf("Input an integer to search: ");
                scanf("%d", &i);
                BSTNode *found = searchBSTNode(root, i);
                if (found != NULL)
                    printf("Found node with value %d.\n", found->item);
                else
                    printf("Value not found.\n");
                break;

            case 3:
                printf("Input an integer to delete: ");
                scanf("%d", &i);
                deleteBSTNode(&root, i);
                break;

            case 4:
                removeAll(&root);
                printf("All nodes removed. Tree is now empty.\n");
                break;

            case 0:
                removeAll(&root);  // 종료 전에도 안전하게 메모리 해제
                break;

            default:
                printf("Unknown choice.\n");
                break;
        }

	}

	return 0;
}

///////////////////////////////////////////////////////////////////////////////

void insertBSTNode(BSTNode **node, int value){
    // TODO: 이진 탐색 트리 삽입 로직 구현
    // - 현재 노드가 NULL이면 새 노드를 생성해 연결
    // - 값이 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀 호출
    // - 중복된 값은 삽입하지 않음
}

BSTNode* searchBSTNode(BSTNode *node, int value) {
    // TODO: 재귀 또는 반복으로 value를 가진 노드를 찾아 반환
    // 찾으면 해당 노드 포인터 반환
    // 없으면 NULL 반환
}

void deleteBSTNode(BSTNode **node, int value) {
    // TODO: 이진 탐색 트리 삭제 로직 구현
    // 세 가지 경우를 고려
    // - 자식이 없는 노드
    // - 자식이 하나 있는 노드
    // - 자식이 두 개인 노드 (inorder successor 또는 predecessor 사용)
}

void removeAll(BSTNode **node) {
    // TODO: 트리 전체를 후위 순회(post-order traversal) 방식으로 해제
}

//////////////////////////////////////////////////////////////////////////////////

이진 탐색 트리 구현하기

함수마다 주어진 매개변수(parameter)를 바탕으로, 해당 함수가 어떤 기능을 수행해야 하는지 먼저 논리적으로 생각해보고, 그 후에 실제로 직접 구현해봅니다.

각 함수는 어떤 기본 동작 흐름을 따르는지, 어떤 포인터 변수를 새로 만들어야 할지, 그리고 예외 상황(스택이 비어있는 경우 등)에는 어떻게 대응해야 할지도 함께 고민해보면 더 좋습니다.

insertBSTNode 함수

이진 탐색 트리에 새로운 값을 삽입하는 함수

이진 탐색 트리의 각 자식은 또 다른 노드를 가리키는 포인터입니다. 따라서 자식 노드 자체를 수정하거나 새로 연결하기 위해서는 그 포인터를 직접 조작할 수 있어야 하며, 이를 위해 함수에 이중 포인터(double pointer)를 전달해야 합니다.

**node: (double pointer) 이진 트리 노드 주소의 주소
value: (int) 저장할 값

insertBSTNode 구현하기

// 이진 탐색 트리에 새로운 값을 삽입하는 함수
void insertBSTNode(BSTNode **node, int value){
    // 현재 위치가 NULL이면, 새 노드를 생성해 연결
    if (*node == NULL) {
        *node = malloc(sizeof(BSTNode));        // 메모리 동적 할당
        (*node)->item = value;                  // 값 저장
        (*node)->left = (*node)->right = NULL;  // 자식 포인터 NULL 초기화
        return;
    }

    // 중복된 값이 들어오면 삽입하지 않고 return
    if (value == (*node)->item) {
        printf("중복된 값은 삽입할 수 없습니다.\n");
        return;
    }

    // 삽입할 값이 현재 노드보다 작으면 왼쪽 서브트리로 이동
    if (value < (*node)->item) {
        insertBSTNode(&((*node)->left), value);
    } 
    // 삽입할 값이 현재 노드보다 크면 오른쪽 서브트리로 이동
    else {
        insertBSTNode(&((*node)->right), value); 
    }
}

searchBSTNode 함수

이진 탐색 트리에서 주어진 값을 가진 노드를 탐색하는 함수. 탐색은 트리 구조를 변경하지 않고 단순히 값을 찾기만 하면 되므로,
포인터 자체를 수정할 필요가 없기 때문에 함수에 일반 포인터를 전달합니다.

*node: (pointer) 이진 트리 노드 주소
value: (int) 탐색할 값

searchBSTNode 구현하기

// 이진 탐색 트리에서 주어진 값을 가진 노드를 탐색하는 함수
BSTNode* searchBSTNode(BSTNode *node, int value) {
	// 트리가 비어있거나 값이 없는 경우 NULL을 반환
    if (node == NULL) return NULL;
    
	// 값을 찾은 경우 현재 노드 반환
    if (value == node->item) return node;       

	// 탐색할 값이 현재 노드보다 작으면 왼쪽 서브트리로 이동
    if (value < node->item) {
        return searchBSTNode(node->left, value);
	// 탐색할 값이 현재 노드보다 크면 오른쪽 서브트리로 이동
    } else {
        return searchBSTNode(node->right, value);
    }
}

deleteBSTNode 함수

이진 탐색 트리에서 주어진 값을 가진 노드를 삭제하는 함수

이진 탐색 트리의 각 자식은 또 다른 노드를 가리키는 포인터입니다. 따라서 특정 노드를 삭제하기 위해서는 그 포인터를 직접 조작할 수 있어야 하며, 이를 위해 함수에 이중 포인터(double pointer)를 전달해야 합니다. 또 삭제의 경우 삽입, 탐색과는 달리 상황이 좀 더 복잡해지는데, (1) 자식이 없는 노드, (2) 자식이 하나인 노드, (3) 자식이 두 개인 노드를 삭제할 때를 각각 고려해야 합니다.

**node: (double pointer) 이진 트리 노드 주소의 주소
value: (int) 삭제할 값

deleteBSTNode 구현하기

// 이진 탐색 트리에서 주어진 값을 가진 노드를 삭제하는 함수
void deleteBSTNode(BSTNode **node, int value) {
    if (*node == NULL) return;  // 삭제할 값이 없으면 return

    if (value == (*node)->item) {
        // Case 1: 자식이 없는 경우
        if ((*node)->left == NULL && (*node)->right == NULL) {
            free(*node);
            *node = NULL;
        }
        // Case 2: 왼쪽 자식만 있는 경우
        else if ((*node)->left != NULL && (*node)->right == NULL) {
            BSTNode *temp = *node;
            *node = (*node)->left;
            free(temp);
        }
        // Case 3: 오른쪽 자식만 있는 경우
        else if ((*node)->left == NULL && (*node)->right != NULL) {
            BSTNode *temp = *node;
            *node = (*node)->right;
            free(temp);
        }
        // Case 4: 자식이 둘 다 있는 경우
        else {
        	// inorder successor(오른쪽 서브트리에서 가장 작은 값, 후임자) 찾기
            BSTNode *cur = (*node)->right;
            while (cur->left != NULL)
                cur = cur->left;

            (*node)->item = cur->item;  // 값 복사
            deleteBSTNode(&((*node)->right), cur->item);  // 후임자 삭제
        }
    }
    // 삭제할 값이 현재 노드보다 작으면 왼쪽 서브트리로
    else if (value < (*node)->item) {
        deleteBSTNode(&((*node)->left), value);
    }
    // 삭제할 값이 현재 노드보다 크면 오른쪽 서브트리로
    else {
        deleteBSTNode(&((*node)->right), value);
    }
}

removeAll 함수

이진 탐색 트리 전체 노드를 삭제하는 함수

이진 탐색 트리의 각 자식은 또 다른 노드를 가리키는 포인터입니다. 따라서 자식 노드를 포함한 트리 구조 전체를 삭제하기 위해서는 그 포인터를 직접 조작할 수 있어야 하며, 이를 위해 함수에 이중 포인터(double pointer)를 전달해야 합니다.

**node: (double pointer) 이진 트리 노드 주소의 주소

removeAll 구현하기

// 이진 탐색 트리의 모든 노드를 제거하는 함수
void removeAll(BSTNode **node) {
	// 노드가 NULL이면 return
    if (*node == NULL) return;

    // 왼쪽 서브트리 제거
    removeAll(&(*node)->left);
    // 오른쪽 서브트리 제거
    removeAll(&(*node)->right);

    // 현재 노드 메모리 해제
    free(*node);
    // 포인터 초기화
    *node = NULL;
}

저작자표시 비영리 변경금지 (새창열림)

'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글

[C언어] Binary Search Tree (2) - inOrderIterative 함수 구현하기 (0)	2025.04.16
[C언어] Binary Search Tree (1) - levelOrderTraversal 함수 구현하기 (0)	2025.04.16
[C언어] Binary Tree (8) - hasGreatGrandchild 함수 구현하기 (0)	2025.04.14
[C언어] Binary Tree (7) - smallestValue 함수 구현하기 (0)	2025.04.14
[C언어] Binary Tree (6) - printSmallerValues 함수 구현하기 (0)	2025.04.14

이진 탐색 트리(Binary Search Tree) 구현 실습하기

필요한 구조체, 함수 정의하기

구조체

함수 (추천 구현 순서)

전체 실습 코드

이진 탐색 트리 구현하기

insertBSTNode 함수

insertBSTNode 구현하기

searchBSTNode 함수

searchBSTNode 구현하기

deleteBSTNode 함수

deleteBSTNode 구현하기

removeAll 함수

removeAll 구현하기

'크래프톤 정글 > Code 정글(C언어)' 카테고리의 다른 글

티스토리툴바