이진 탐색 트리 — 삽입, 삭제, 그리고 균형이 깨지는 순간

배열에서 이진 탐색을 하면 O(log n)인데, 삽입도 O(log n)으로 할 수는 없을까요?

이진 탐색 트리란

이진 탐색 트리(Binary Search Tree, BST)는 다음 속성을 만족하는 이진 트리입니다.

왼쪽 서브트리의 모든 값은 현재 노드보다 작습니다
오른쪽 서브트리의 모든 값은 현재 노드보다 ** 큽니다**
왼쪽과 오른쪽 서브트리도 각각 BST입니다

PLAINTEXT

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

이 구조 덕분에 검색할 때 매 단계마다 절반을 버릴 수 있어, 이진 탐색과 같은 효과를 냅니다.

왜 필요한가

정렬된 배열은 검색이 O(log n)이지만, 삽입/삭제가 O(n)입니다 (요소를 밀어야 하므로). BST는 ** 검색, 삽입, 삭제를 모두 O(log n)**에 처리하는 것을 목표로 합니다.

연산	정렬된 배열	BST (평균)	BST (최악)
검색	O(log n)	O(log n)	O(n)
삽입	O(n)	O(log n)	O(n)
삭제	O(n)	O(log n)	O(n)

노드 구조

JAVA

class BSTNode<T extends Comparable<T>> {
    T value;
    BSTNode<T> left;
    BSTNode<T> right;

    BSTNode(T value) {
        this.value = value;
    }
}

검색

현재 노드와 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동합니다.

JAVA

BSTNode<T> search(BSTNode<T> node, T target) {
    if (node == null) return null;

    int cmp = target.compareTo(node.value);
    if (cmp == 0) return node;           // 찾음
    if (cmp < 0) return search(node.left, target);   // 왼쪽으로
    return search(node.right, target);                // 오른쪽으로
}

반복문 버전도 가능합니다.

JAVA

BSTNode<T> searchIterative(BSTNode<T> root, T target) {
    BSTNode<T> current = root;
    while (current != null) {
        int cmp = target.compareTo(current.value);
        if (cmp == 0) return current;
        current = (cmp < 0) ? current.left : current.right;
    }
    return null;
}

삽입

새 값을 넣을 위치를 찾아 리프 노드로 추가합니다.

JAVA

BSTNode<T> insert(BSTNode<T> node, T value) {
    if (node == null) return new BSTNode<>(value);

    int cmp = value.compareTo(node.value);
    if (cmp < 0) {
        node.left = insert(node.left, value);
    } else if (cmp > 0) {
        node.right = insert(node.right, value);
    }
    // cmp == 0이면 중복, 아무것도 하지 않음
    return node;
}

삽입 예시

PLAINTEXT

[5]에 3을 삽입:     [5]에 7을 삽입:     [5]에 4를 삽입:
    5                   5                   5
   /                   / \                 / \
  3                   3   7               3   7
                                           \
                                            4

삭제

삭제는 BST에서 가장 복잡한 연산입니다. 세 가지 경우로 나뉩니다.

Case 1: 리프 노드 삭제

자식이 없으므로 그냥 제거합니다.

PLAINTEXT

    5        →      5
   / \             / \
  3   7           3   7
 /
1  ← 삭제

Case 2: 자식이 1개인 노드 삭제

자식이 부모의 자리를 대신합니다.

PLAINTEXT

    5        →      5
   / \               \
  3   7    ← 삭제     7
   \
    4

잠깐, 이렇게 하면 4가 사라집니다. 실제로는 다음과 같습니다.

PLAINTEXT

    5        →      5
   / \             / \
  3   7           4   7
   \
    4

3을 삭제하면 유일한 자식 4가 3의 위치를 대체합니다.

Case 3: 자식이 2개인 노드 삭제

** 중위 후속자(in-order successor)**로 대체합니다. 중위 후속자는 오른쪽 서브트리에서 가장 작은 값입니다.

PLAINTEXT

    5  ← 삭제       6
   / \     →       / \
  3   7           3   7
     /
    6

5를 삭제 → 중위 후속자 6으로 대체

JAVA

BSTNode<T> delete(BSTNode<T> node, T value) {
    if (node == null) return null;

    int cmp = value.compareTo(node.value);
    if (cmp < 0) {
        node.left = delete(node.left, value);
    } else if (cmp > 0) {
        node.right = delete(node.right, value);
    } else {
        // 삭제 대상 노드 발견

        // Case 1 & 2: 자식이 0개 또는 1개
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;

        // Case 3: 자식이 2개 → 중위 후속자로 대체
        BSTNode<T> successor = findMin(node.right);
        node.value = successor.value;
        node.right = delete(node.right, successor.value);
    }
    return node;
}

BSTNode<T> findMin(BSTNode<T> node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

순회

BST를 순회하는 세 가지 방법이 있습니다.

JAVA

// 중위 순회 (In-order): 오름차순 정렬 결과
void inOrder(BSTNode<T> node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

// 전위 순회 (Pre-order): 트리 구조 복제에 유용
void preOrder(BSTNode<T> node) {
    if (node == null) return;
    System.out.print(node.value + " ");
    preOrder(node.left);
    preOrder(node.right);
}

// 후위 순회 (Post-order): 삭제나 메모리 해제에 유용
void postOrder(BSTNode<T> node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.value + " ");
}

** 중위 순회가 특히 중요합니다** — BST를 중위 순회하면 오름차순 정렬된 결과가 나옵니다.

편향 트리 — BST의 치명적 약점

정렬된 데이터를 순서대로 삽입하면 어떻게 될까요?

JAVA

// 1, 2, 3, 4, 5 순서로 삽입
BST에 1 삽입: 1
BST에 2 삽입: 1 → 2
BST에 3 삽입: 1 → 2 → 3
BST에 4 삽입: 1 → 2 → 3 → 4
BST에 5 삽입: 1 → 2 → 3 → 4 → 5

PLAINTEXT

이것은 사실상 ** 연결 리스트 **입니다. 검색이 O(n)이 됩니다.

이 문제를 해결하기 위해 ** 자가 균형 트리 **(AVL Tree, Red-Black Tree)가 등장합니다.

백엔드에서의 BST

Java의 TreeMap

TreeMap은 Red-Black Tree(자가 균형 BST)로 구현되어 있습니다.

JAVA

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 3);
map.put("apple", 1);
map.put("cherry", 2);

// 키가 정렬된 상태로 유지됩니다
map.firstKey();   // "apple"
map.lastKey();    // "cherry"

// 범위 쿼리
map.subMap("apple", "cherry"); // apple <= key < cherry

DB 인덱스

데이터베이스의 B-Tree 인덱스는 BST의 확장입니다. BST의 원리를 이해하면 DB 인덱스의 동작도 이해할 수 있습니다.

SQL

-- B-Tree 인덱스가 BST 원리를 확장한 것
CREATE INDEX idx_name ON users(name);

-- 이 쿼리가 인덱스를 타는 이유: BST처럼 범위 검색이 가능하기 때문
SELECT * FROM users WHERE name BETWEEN 'A' AND 'M';

Spring 빈 의존성 해결

Spring 컨테이너가 빈을 정렬하거나 우선순위를 정할 때 내부적으로 TreeMap을 사용하기도 합니다.

BST 유효성 검증

주어진 트리가 BST인지 확인하는 것은 자주 등장하는 문제입니다.

JAVA

// 올바른 방법: 범위를 전달
boolean isValidBST(BSTNode<Integer> node, Integer min, Integer max) {
    if (node == null) return true;

    if (min != null && node.value <= min) return false;
    if (max != null && node.value >= max) return false;

    return isValidBST(node.left, min, node.value) &&
           isValidBST(node.right, node.value, max);
}

// 호출: isValidBST(root, null, null)

주의할 점은, 단순히 왼쪽 < 현재 < 오른쪽만 확인하면 안 됩니다. 서브트리 전체 가 범위를 만족해야 합니다.

정리

BST는 왼쪽 < 현재 < 오른쪽 속성으로 검색, 삽입, 삭제를 평균 O(log n)에 수행합니다.
삭제 시 자식이 2개인 노드는 ** 중위 후속자 **로 대체합니다.
** 편향 트리** 문제가 있어 최악의 경우 O(n)이 됩니다. 이를 해결하기 위해 AVL, Red-Black Tree 같은 균형 트리가 등장합니다.
Java의 TreeMap은 Red-Black Tree 기반이며, DB의 B-Tree 인덱스도 BST의 확장입니다.
BST의 중위 순회는 ** 오름차순 정렬 결과 **를 제공합니다.