이진 탐색 트리 (Binary Search Tree)

2026. 07. 29

들어가는 말

이진 탐색은 정렬된 배열에서 원하는 값의 존재 여부와 위치를 빠르게 찾는 알고리즘이다.
이진 탐색은 말 그대로 탐색만을 위한 것이라 배열에 값을 삽입하거나 삭제하면 정렬 상태를 다시 맞추는 데 많은 비용이 든다.
그래서 정렬 상태를 유지하면서 삽입과 삭제도 효율적으로 처리하기 위해 이진 탐색 트리(Binary Search Tree, BST)를 사용한다.
이진 탐색 트리는 탐색에 유리한 정렬 상태를 동적으로 유지하는 트리 자료구조다.

동작 원리

배열 9, 5, 2, 1, 3, 4, 13, 11, 12를 BST로 만들면 다음과 같다.

          9
        /   \
       5     13
      /      /
     2      11
    / \       \
   1   3       12
        \
         4

이진 탐색 트리의 조건

이진 탐색 트리는 모든 노드가 정렬 규칙을 지키는 이진 트리다.
어떤 노드에서든 왼쪽 서브트리의 모든 값은 현재 노드의 값보다 작고, 오른쪽 서브트리의 모든 값은 현재 노드의 값보다 커야 한다.
이 규칙은 직계 자식 노드뿐 아니라 서브트리에 속한 모든 자손 노드에 적용된다.
예를 들어 루트 노드가 9라면 왼쪽 서브트리에는 9보다 작은 값만, 오른쪽 서브트리에는 9보다 큰 값만 있어야 한다.

부모와 자식 사이에 대소 관계가 있다는 점에서는 힙과 비슷해 보인다.
하지만 힙은 부모와 자식 사이의 우선순위만 보장한다.
반면 이진 탐색 트리는 각 노드를 기준으로 왼쪽과 오른쪽 서브트리 전체의 대소 관계를 보장한다.

예를 들어 6, 3, 5, 2를 순서대로 삽입해 보자.

Max Heap

    6
   / \
  3   5
 /
2

Binary Search Tree

    6
   /
  3
 / \
2   5

그래서 힙은 최솟값이나 최댓값을 빠르게 꺼내는 데 적합하다.
이진 탐색 트리는 값을 정렬된 순서로 유지하면서 특정 값을 찾거나 삽입하고 삭제하는 데 적합하다.

중복 값을 허용해야 한다면 같은 값을 항상 한쪽 서브트리에 삽입하도록 규칙을 정할 수 있다.
예를 들어 같은 값이 두 개라면, 하나는 부모 노드가 되고 다른 하나는 그 자식 노드로 들어가야 한다.
이때 같은 값을 오른쪽 서브트리에 넣도록 정하면, 왼쪽 서브트리의 값은 현재 노드보다 작고 오른쪽 서브트리의 값은 현재 노드보다 크거나 같아야 한다.
이 글에서는 중복 원소가 없다고 가정하고 진행한다.

탐색

현재 노드의 값이 찾으려는 값과 같다면 탐색을 마친다.
그렇지 않고 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 자식으로 이동하고, 크면 오른쪽 자식으로 이동한다.
값을 찾거나 더 이상 이동할 노드가 없을 때까지 이 과정을 반복한다.

삽입

삽입할 값은 탐색하듯 현재 노드와 비교하며, 비어 있는 자식 위치까지 내려간 뒤 그 자리에 놓는다.
예를 들어 3을 삽입하면 9와 5보다 작으므로 두 노드의 왼쪽으로 차례로 이동한다.
이후 2보다 크므로 오른쪽으로 이동하고, 그 자리가 비어 있으므로 3을 삽입한다.

선임자(predecessor)

선임자는 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드다.

노드 9의 선임자: 5
노드 5의 선임자: 4
노드 4의 선임자: 3

후임자(successor)

후임자는 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드다.

노드 9의 후임자: 11
노드 5의 후임자: 9
노드 4의 후임자: 5

삭제

삭제하려면 해당 값이 존재하는지 확인해야 하므로 탐색 과정이 필요하다.
삭제할 값이 존재한다면 삭제하는 경우의 수는 4가지다.
자식 노드가 둘 다 있는 노드를 삭제하는 방법에는 delete by merge 방식과 delete by copy 방식이 있다.
여기서는 delete by copy 방식으로 설명한다.

자식 노드가 없는 경우

해당 노드를 바로 제거한다.
예를 들어 1을 삭제하면 2의 왼쪽 자식이 NULL이 된다.
오른쪽 자식 노드만 있는 경우

오른쪽 자식 노드가 삭제할 노드의 위치를 대신한다.
예를 들어 3을 삭제하면, 3의 오른쪽 자식인 4가 2의 오른쪽 자식으로 연결된다.
왼쪽 자식 노드만 있는 경우

왼쪽 자식 노드가 삭제할 노드의 위치를 대신한다.
예를 들어 13을 삭제하면, 13의 왼쪽 자식인 11이 9의 오른쪽 자식으로 연결된다.
자식 노드가 둘 다 있는 경우

먼저 삭제할 노드의 값을 선임자나 후임자의 값으로 바꾼다.
이때 같은 값을 가진 노드가 두 개가 되므로, 원래 선임자나 후임자 노드를 한 번 더 삭제한다.
예를 들어 9를 삭제하면, 후임자 11의 값을 9에 복사한 뒤 원래 11을 삭제한다.

순회

순회는 트리에서 이미 살펴보았으므로, 이 글에서는 설명을 생략한다.

시간 복잡도

균형 잡힌 이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 모두 O(log n)이다.
하지만 1, 2, 3, 4, 5처럼 정렬된 순서로 값을 삽입하면 트리가 한쪽으로 편향된다.
편향된 트리는 높이가 O(n)이 되어 탐색, 삽입, 삭제의 시간 복잡도도 모두 O(n)이다.

소스 코드

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

typedef struct node
{
    int value;
    struct node* left;
    struct node* right;
} Node;

Node* create_node(int value)
{
    Node* new_node = malloc(sizeof(Node));

    if (new_node == NULL)
        return NULL;

    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;

    return new_node;
}

Node* insert_node(Node* root, int value)
{
    if (root == NULL)
        return create_node(value);

    if (value < root->value)
        root->left = insert_node(root->left, value);
    else if (value > root->value)
        root->right = insert_node(root->right, value);

    return root;
}

Node* find_node(Node* root, int value)
{
    if (root == NULL || root->value == value)
        return root;

    if (value < root->value)
        return find_node(root->left, value);

    return find_node(root->right, value);
}

Node* find_min_node(Node* root)
{
    while (root->left != NULL)
        root = root->left;

    return root;
}

Node* delete_node(Node* root, int value)
{
    if (root == NULL)
        return NULL;

    if (value < root->value)
        root->left = delete_node(root->left, value);
    else if (value > root->value)
        root->right = delete_node(root->right, value);
    else // value == root->value
    {
        if (root->left == NULL)
        {
            Node* right_node = root->right;
            free(root);
            return right_node;
        }

        if (root->right == NULL)
        {
            Node* left_node = root->left;
            free(root);
            return left_node;
        }

        Node* successor = find_min_node(root->right);

        root->value = successor->value;
        root->right = delete_node(root->right, successor->value);
    }

    return root;
}

void print_inorder(Node* root)
{
    if (root == NULL)
        return;

    print_inorder(root->left);
    printf("%d ", root->value);
    print_inorder(root->right);
}

void print_reverse_inorder(Node* root)
{
    if (root == NULL)
        return;

    print_reverse_inorder(root->right);
    printf("%d ", root->value);
    print_reverse_inorder(root->left);
}

void destroy_tree(Node* root)
{
    if (root == NULL)
        return;

    destroy_tree(root->left);
    destroy_tree(root->right);
    free(root);
}

int main(void)
{
    int arr[] = { 9, 5, 2, 1, 3, 4, 13, 11, 12 };
    Node* root = NULL;

    for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        root = insert_node(root, arr[i]);

    if (find_node(root, 5) != NULL)
        printf("Found 5.\n\n");

    if (find_node(root, 6) == NULL)
        printf("6 not found.\n\n");

    printf("Before deletion:\n");
    print_inorder(root); // 1 2 3 4 5 9 11 12 13
    printf("\n");

    print_reverse_inorder(root); // 13 12 11 9 5 4 3 2 1
    printf("\n\n");

    root = delete_node(root, 1);  // Case 1: The target has no children.
    root = delete_node(root, 3);  // Case 2: The target has only a right child.
    root = delete_node(root, 13); // Case 3: The target has only a left child.
    root = delete_node(root, 9);  // Case 4: The target has both children.

    printf("After deletion:\n");
    print_inorder(root); // 2 4 5 11 12
    printf("\n");

    print_reverse_inorder(root); // 12 11 5 4 2
    printf("\n\n");

    destroy_tree(root);

    return 0;
}

구현 설명

삽입

insert_node는 재귀적으로 적절한 빈 위치를 찾아 새 노드를 삽입한다.
삽입할 값이 현재 노드의 값보다 작은지 큰지에 따라 각각 왼쪽이나 오른쪽 서브트리를 재귀적으로 호출한다.
root가 NULL이라는 것은 삽입 위치에 도달한 것이므로 create_node로 새 노드를 만들어 반환한다.
반환된 새 노드는 호출자에게 돌아가 root->left 또는 root->right에 대입된다.
이미 존재하는 노드도 재귀 호출이 끝날 때마다 반환되어 부모 노드의 root->left 또는 root->right에 다시 대입된다.

삭제

삭제할 노드 탐색

if (root == NULL)
    return NULL;

if (value < root->value)
    root->left = delete_node(root->left, value);
else if (value > root->value)
    root->right = delete_node(root->right, value);

삭제할 값을 찾기 위해 먼저 탐색을 수행한다.
삭제할 값이 현재 노드의 값보다 작으면 왼쪽 서브트리를, 크면 오른쪽 서브트리를 재귀적으로 호출한다.
이 과정을 반복하다 NULL에 도달하면 해당 값은 트리에 없으므로 delete_node는 NULL을 반환한다.

왼쪽 자식이 없는 경우

if (root->left == NULL)
{
    Node* right_node = root->right;
    free(root);
    return right_node;
}

왼쪽 자식이 없으면 오른쪽 자식은 존재할 수도 있고 NULL일 수도 있다.
하지만 어느 경우든 삭제할 노드의 오른쪽 자식이 삭제할 노드의 자리를 대신한다.
return right_node의 반환값은 호출한 쪽에서 root->left 또는 root->right에 대입되므로,
삭제할 노드가 부모의 어느 쪽 자식이었는지에 맞춰 연결이 유지된다.
root를 먼저 free하면 root->right에 접근할 수 없으므로, 오른쪽 자식 포인터를 지역 변수에 저장한 뒤 free를 호출한다.

오른쪽 자식이 없는 경우

if (root->right == NULL)
{
    Node* left_node = root->left;
    free(root);
    return left_node;
}

이 코드가 실행되기 전 root->left == NULL 조건에 걸리지 않았으므로 왼쪽 자식은 존재하고 오른쪽 자식은 존재하지 않는 상황이다.
return left_node의 반환값은 호출한 쪽에서 root->left 또는 root->right에 대입되므로,
삭제할 노드가 부모의 어느 쪽 자식이었는지에 맞춰 연결이 유지된다.
root를 먼저 free하면 root->left에 접근할 수 없으므로, 왼쪽 자식 포인터를 지역 변수에 저장한 뒤 free를 호출한다.

자식이 둘인 경우

Node* successor = find_min_node(root->right);

root->value = successor->value;
root->right = delete_node(root->right, successor->value);

앞선 두 조건에 걸리지 않았으므로 삭제할 노드는 왼쪽과 오른쪽 자식을 모두 가진다.
이 경우 삭제할 노드의 자리는 하나지만 자식은 둘이므로, 삭제한 뒤에도 두 서브트리를 모두 올바르게 연결해야 한다.
여기서는 삭제할 노드의 값을 후임자의 값으로 바꾸는 방식을 사용한다.
후임자는 삭제할 노드보다 큰 값 중 가장 작은 값이며, 오른쪽 서브트리에서 가장 왼쪽에 있는 노드다.
따라서 find_min_node로 오른쪽 서브트리의 가장 왼쪽 노드를 찾는다.
후임자의 값을 복사하면 같은 값을 가진 노드가 두 개가 된다.
따라서 오른쪽 서브트리에서 원래 후임자 노드를 재귀적으로 삭제한다.