이진탐색트리로 정렬·탐색·삭제를 다루는 법

정렬 상태를 유지하는 트리의 조건

이진탐색트리(Binary Search Tree, BST)는 각 노드가 최대 두 자식을 가지는 구조다. 임의 노드 v에서 left(v)의 모든 키는 key(v)보다 작고, right(v)의 모든 키는 key(v)보다 커야 한다. 이 규칙은 모든 서브트리에 재귀적으로 적용된다.

이 순서 불변식이 유지되면 루트에서 키를 비교하면서 왼쪽 또는 오른쪽으로만 내려가 검색할 수 있다. 정렬된 순회, 범위 질의, 동적 삽입과 삭제가 필요한 인메모리 인덱스에 적합한 이유다.

트리의 높이 h는 평균적으로 O(log n)이지만, 정렬된 입력처럼 편향된 데이터가 들어오면 최악 O(n)에 도달한다. 중복 키를 어떻게 다룰지도 미리 정해야 한다. 무시할지, 카운트를 저장할지, 한쪽 서브트리에만 삽입할지에 따라 구현이 달라진다.

탐색·삽입·삭제에서 지켜야 할 불변식

검색은 루트부터 키를 비교해 좌우 서브트리 중 하나로 이동하는 과정이다. 평균 시간복잡도는 O(log n), 불균형 상태에서는 O(n)이다.

삽입은 검색 경로를 따라가 리프 위치를 찾은 뒤 새 노드를 연결한다. 이때 중복 키 정책을 적용해야 한다.

삭제는 노드의 자식 상태에 따라 처리 방식이 갈린다.

• 리프 노드는 바로 제거한다.
• 자식이 하나라면 해당 자식으로 대체한다.
• 양쪽 자식이 있다면 후계자인 오른쪽 서브트리의 최소 키 또는 전임자인 왼쪽 서브트리의 최대 키로 교체한 뒤, 해당 노드를 재귀적으로 삭제한다.

포인터로 연결된 구조이므로 삽입과 삭제에서는 부모-자식 링크의 일관성이 중요하다. 연산 실패나 예외가 발생했을 때는 롤백하거나 일관된 상태를 보장해야 하며, 널 포인터와 메모리 해제 실패도 방어 대상이다.

중위 순회와 범위 질의가 필요한 곳

중위 순회(Inorder)는 항상 오름차순 정렬 시퀀스를 반환한다. 하한과 상한을 기준으로 필요한 서브트리만 방문할 수 있어 범위 질의에도 유리하다.

BST는 다음과 같은 구조의 기반으로 쓸 수 있다.

• 인메모리 정렬 인덱스와 Ordered Map: 키 범위 순회와 최근접 값 탐색을 지원한다.
• 스케줄러와 이벤트 타임라인: 다음 실행 시점인 최소 키를 추출하고 동적으로 갱신한다.
• 간단한 랭킹과 리더보드: 점수 순서를 유지하고 구간 집계의 기반이 된다. 통계가 필요하면 Order-Statistic Tree로 확장할 수 있다.

노드는 키와 좌·우 포인터로 구성되며 메모리 오버헤드는 2포인터 고정이다. 중복을 허용한다면 카운트 필드나 동일 키 연결 리스트를 둘 수 있다.

높이가 성능을 결정한다

검색·삽입·삭제는 평균 O(log n)이며, 범위 질의는 O(k + log n)으로 처리할 수 있다. 여기서 k는 반환 원소 수다. 정렬 유지 비용 없이 실시간 삽입과 삭제를 지원하고, 중위 순회로 순차 접근할 수 있다.

반면 불균형 입력에서는 성능이 저하되고, 연속 메모리 구조보다 캐시 친화성도 낮다. 높이를 O(log n)으로 보장해야 한다면 AVL 또는 Red-Black 같은 자가 균형 트리를 사용한다. 대규모 데이터에서는 B-Tree류나 해시·정렬 파일과 혼합하는 설계가 필요할 수 있다.

연산	평균	최악(불균형)
검색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

삭제 경로와 예외 처리

삭제 연산의 입력은 루트 포인터와 삭제 대상 키다. 키 비교로 대상을 찾고, 리프·단일 자식·양쪽 자식의 경우로 분기한 뒤 링크를 재배치하거나 대체한다. 처리 후에는 순서 불변식이 유지되는지 확인한다.

존재하지 않는 키는 no-op으로 반환하고, 널 포인터를 방어하며, 메모리 해제 실패도 대비한다.

⤢✕

C 구현에서 확인할 부분

아래 예시는 C17과 GCC/Clang을 전제로 하며, gcc -std=c17 -O2 bst.c -o bst로 빌드한다. 중복 키 삽입은 무시한다.

// bst.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
    int key;
    struct TreeNode *left, *right;
} TreeNode;

static TreeNode* new_node(int key) {
    TreeNode* n = (TreeNode*)malloc(sizeof(TreeNode));
    if (!n) { perror("malloc"); exit(EXIT_FAILURE); }
    n->key = key; n->left = n->right = NULL;
    return n;
}

TreeNode* search(TreeNode* root, int key) {
    while (root) {
        if (key == root->key) return root;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new_node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    // equal: ignore
    return root;
}

static TreeNode* find_min(TreeNode* node) {
    if (!node) return NULL;
    while (node->left) node = node->left;
    return node;
}

TreeNode* delete(TreeNode* root, int key) {
    if (!root) return NULL;

    if (key < root->key) {
        root->left = delete(root->left, key);
    } else if (key > root->key) {
        root->right = delete(root->right, key);
    } else {
        // found
        if (!root->left && !root->right) {
            free(root);
            return NULL;
        } else if (!root->left) {
            TreeNode* r = root->right;
            free(root);
            return r;
        } else if (!root->right) {
            TreeNode* l = root->left;
            free(root);
            return l;
        } else {
            TreeNode* succ = find_min(root->right);
            root->key = succ->key;
            root->right = delete(root->right, succ->key);
        }
    }
    return root;
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

void free_tree(TreeNode* root) {
    if (!root) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    size_t n = sizeof(keys)/sizeof(keys[0]);
    TreeNode* root = NULL;

    for (size_t i = 0; i < n; ++i)
        root = insert(root, keys[i]);

    printf("Inorder: ");
    inorder(root); puts("");

    int q = 40;
    printf("Search %d: %s\n", q, search(root, q) ? "Found" : "Not Found");

    root = delete(root, 50); // 양쪽 자식 보유 노드 삭제
    printf("After delete 50, inorder: ");
    inorder(root); puts("");

    free_tree(root);
    return 0;
}

기존 구현을 점검할 때는 검색 함수의 변수 오타와 재귀 호출 결과 반환 여부를 먼저 본다. 삽입에서는 루트 포인터를 값으로 전달하면 갱신할 수 없으므로 새 루트를 반환하거나 이중 포인터를 사용해야 한다. 삭제는 반환 타입을 일치시키고, 양쪽 자식이 있는 경우 대체한 노드를 서브트리에서 재귀적으로 삭제한 뒤 새 루트를 다시 연결해야 한다.