BST (Binary Search Tree)

도입

BST(Binary Search Tree)는 정렬 규칙을 트리 구조 자체에 넣어, 루트에서 비교를 반복하며 검색 범위를 줄여 가는 이진 트리다.

배열에서 이진 탐색이 빠른 이유는 데이터가 정렬되어 있기 때문입니다. BST는 이 정렬 규칙을 배열이 아니라 트리 구조 안에 직접 반영한 자료구조라고 보면 이해가 쉽습니다.

즉 어떤 노드의 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값이 오도록 유지하면, 루트에서 시작해 비교를 반복하는 것만으로도 필요한 방향으로만 내려가 검색 범위를 빠르게 줄일 수 있습니다.

그래서 BST를 이해한다는 것은 단순히 이진 트리를 아는 것이 아니라, 정렬과 탐색 규칙을 구조에 녹여 넣는 방식을 이해하는 일에 가깝습니다.

필요성

정렬된 데이터에 대한 탐색과 삽입·삭제를 함께 처리해야 할 때, BST는 순차 구조보다 훨씬 더 자연스러운 선택이 된다

배열은 이진 탐색에는 강하지만, 중간 삽입과 삭제가 자주 일어나면 이동 비용이 커집니다. 반대로 연결 리스트는 삽입과 삭제는 편해도 정렬된 검색에는 비효율적입니다.

BST는 정렬 순서를 유지하면서도 트리 경로를 따라 탐색하고, 적절한 위치에 새 노드를 붙이거나 제거할 수 있게 해 줍니다. 즉 검색과 업데이트를 둘 다 다뤄야 하는 문제에서 자주 등장하는 이유가 여기에 있습니다.

다만 BST의 장점은 트리 높이가 지나치게 커지지 않을 때 잘 드러납니다. 이 점 때문에 BST를 배우고 나면 곧바로 균형 트리로 이어지는 흐름이 자연스럽습니다.

BST가 특히 강한 지점

• 정렬 순서를 유지한 채 검색을 빠르게 하고 싶을 때
• 삽입과 삭제가 단순 배열보다 더 자주 일어날 때
• 중위 순회로 정렬 순 출력을 얻고 싶을 때
• 탐색 범위를 비교를 통해 단계적으로 줄여 가고 싶을 때

정의

BST는 모든 노드에 대해 왼쪽 서브트리의 키는 더 작고, 오른쪽 서브트리의 키는 더 크다는 불변식을 가지는 이진 트리다

NIST 기준으로 BST는 각 노드의 왼쪽 서브트리에 있는 키들이 현재 노드의 키보다 작고, 오른쪽 서브트리의 키들은 더 큰 이진 트리입니다.

이 규칙은 루트에서 한 번만 맞는 것이 아니라, 모든 노드에서 재귀적으로 성립해야 합니다. 즉 각 서브트리도 다시 BST여야 합니다.

그래서 BST의 핵심은 노드 배치가 아니라 불변식입니다. 모양이 예쁘게 생겼는지가 아니라, 각 노드 기준으로 왼쪽은 더 작고 오른쪽은 더 큰 상태를 유지하는지가 진짜 조건입니다.

핵심 메시지

"BST의 본질은 트리 모양이 아니라

왼쪽은 더 작고 오른쪽은 더 크다는 검색 불변식을 구조 전체에 유지하는 데 있습니다."

핵심 원리

BST의 검색·삽입·삭제는 모두 루트에서 어떤 노드까지의 경로를 따라가는 연산이며, 실제 비용은 노드 수보다 트리 높이에 더 직접적으로 좌우된다

Open Data Structures 기준으로 BST에서 find(x), add(x), remove(x) 는 모두 루트에서 시작해 현재 값과 비교하며 왼쪽 또는 오른쪽으로 내려갑니다. 결국 공통점은 하나의 경로를 따라간다는 점입니다.

이 말은 곧 연산 비용이 트리의 높이에 비례한다는 뜻입니다. 균형이 잘 잡혀 있으면 경로가 짧고, 한쪽으로 편향되면 경로가 길어집니다.

즉 BST를 이해할 때는 단순히 “검색 트리다”가 아니라, “모든 핵심 연산이 root-to-node path 길이에 의존한다”는 사실을 먼저 잡는 편이 훨씬 중요합니다.

그래서 BST는 검색 규칙을 배우는 자료구조이면서 동시에, 왜 균형이 중요한지 이해하게 만드는 출발점이기도 합니다.

BST Operation Model
1) 루트에서 시작한다
2) 현재 노드의 값과 목표 값을 비교한다
3) 더 작으면 왼쪽, 더 크면 오른쪽으로 내려간다
4) 찾거나, 빈 자리에 도달하거나, 대체 노드를 찾을 때까지 반복한다
5) 연산 비용은 이 경로 길이, 즉 height에 좌우된다

핵심 불변식

BST를 BST답게 만드는 것은 노드 연결 자체보다도, 각 노드 기준으로 왼쪽과 오른쪽이 어떤 범위를 담당하는지 유지하는 규칙이다

구성 요소	의미	실무 해석
Left Subtree	현재 노드보다 작은 값들	검색 시 target이 더 작으면 이쪽만 보면 됨
Current Node	비교 기준점	현재 분기 판단의 중심
Right Subtree	현재 노드보다 큰 값들	검색 시 target이 더 크면 이쪽만 보면 됨
Recursive Validity	각 서브트리도 다시 BST여야 함	루트 한 곳만 맞아서는 충분하지 않음
Height Dependence	연산은 결국 경로 길이에 비례	성능은 node count보다 tree shape에 민감

기본 구조

BST는 보통 값과 왼쪽·오른쪽 자식 참조를 가진 노드들의 연결로 구현되며, 필요에 따라 부모 포인터를 함께 둔다

binary-search-tree/
├── root
└── node
    ├── key
    ├── left
    ├── right
    └── parent (optional but often useful)

Open Data Structures는 기본 binary tree 노드 표현으로 left, right, parent 참조를 함께 두는 방식을 설명합니다. BST도 이 표현 위에 검색 불변식을 추가한 구조로 이해하면 자연스럽습니다.

특히 삭제나 상위로 다시 올라가는 연산에서는 parent 포인터가 편한 경우가 많습니다. 반면 공간을 아끼거나 구현을 단순화하기 위해 parent 없이 재귀나 명시적 스택으로 처리하는 구현도 가능합니다.

기본 구현

BST를 이해하는 가장 빠른 방법은 검색과 삽입 코드가 거의 같은 경로를 따라간다는 점을 직접 보는 것이다

class Node {
    int key;
    Node left;
    Node right;
    Node parent;

    Node(int key) {
        this.key = key;
    }
}

Node find(Node root, int x) {
    Node u = root;
    while (u != null) {
        if (x < u.key) {
            u = u.left;
        } else if (x > u.key) {
            u = u.right;
        } else {
            return u;
        }
    }
    return null;
}

Node insert(Node root, int x) {
    if (root == null) return new Node(x);

    Node u = root;
    Node p = null;

    while (u != null) {
        p = u;
        if (x < u.key) {
            u = u.left;
        } else if (x > u.key) {
            u = u.right;
        } else {
            return root; // already exists
        }
    }

    Node n = new Node(x);
    n.parent = p;

    if (x < p.key) p.left = n;
    else p.right = n;

    return root;
}

실전 포인트

검색과 삽입의 핵심은 거의 같습니다. 차이는 검색은 찾다가 끝나고, 삽입은 끝까지 내려간 뒤 마지막으로 만난 노드 밑에 새 노드를 붙인다는 점입니다. 그래서 BST 구현을 익힐 때는 이 두 연산을 함께 보는 편이 훨씬 빠릅니다.

패턴 1. 검색과 lower bound

BST 검색은 값을 찾는 것에 그치지 않고, 찾지 못했을 때도 어느 값이 바로 다음 후보인지에 대한 정보를 남겨 준다

Open Data Structures는 BST 검색에서 값을 못 찾는 경우에도 의미 있는 정보를 얻을 수 있다고 설명합니다. 예를 들어 탐색 중 마지막으로 “왼쪽으로 내려갔던 노드”를 기억하면, 그것이 트리 안에서 목표값 이상인 가장 작은 값 후보가 될 수 있습니다.

즉 BST는 단순 membership test 구조가 아니라, 정렬 순서 위에서 predecessor나 successor, lower bound 같은 질의를 자연스럽게 다룰 수 있는 구조입니다.

Search Cases
1) x < u.key  -> go left
2) x > u.key  -> go right
3) x == u.key -> found

Not found?
- 마지막으로 왼쪽으로 꺾은 노드는
  "x 이상인 가장 작은 값" 후보가 될 수 있음

패턴 2. 중위 순회와 정렬

BST에서는 중위 순회가 곧 정렬 순 방문이 되기 때문에, 정렬된 출력과 검색 구조가 자연스럽게 연결된다

중위 순회는 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 방문합니다. BST에서는 왼쪽이 더 작고 오른쪽이 더 크므로, 이 순회 순서가 그대로 오름차순 방문이 됩니다.

NIST의 treesort 설명도 이 원리를 사용합니다. 먼저 키들을 BST에 넣고, 그다음 in-order traversal로 값을 꺼내면 정렬 순으로 접근할 수 있습니다.

void inorder(Node u) {
    if (u == null) return;
    inorder(u.left);
    System.out.println(u.key);
    inorder(u.right);
}

패턴 3. 삽입과 삭제

삽입은 마지막으로 도달한 위치 아래에 새 노드를 붙이는 일이고, 삭제는 자식 수에 따라 leaf 제거, splice, successor 치환으로 나뉜다

삽입은 비교를 반복해 빈 위치를 찾고 그 자리에 새 노드를 붙이면 됩니다. 구현 난이도는 비교적 낮습니다.

삭제는 더 복잡합니다. 자식이 없으면 그냥 떼어 내면 되고, 자식이 하나면 그 자식이 부모에게 바로 연결되도록 splice 하면 됩니다.

가장 까다로운 경우는 자식이 둘인 노드입니다. Open Data Structures는 이 경우 오른쪽 서브트리에서 가장 작은 값, 즉 in-order successor를 찾아 현재 값을 대체한 뒤, 실제 successor 노드를 제거하는 방식으로 설명합니다.

Delete Cases
1) child 0개
   - 그냥 제거

2) child 1개
   - splice: 부모가 그 자식을 직접 입양

3) child 2개
   - 오른쪽 서브트리의 최소값(successor)으로 대체
   - 실제 successor 노드를 삭제

패턴 4. 왜 균형 트리가 필요한가

BST의 모든 핵심 연산은 root-to-node path를 따라가므로, 트리가 한쪽으로 치우치면 장점이 거의 사라지고 결국 균형 유지가 다음 단계 문제로 등장한다

Open Data Structures는 BST의 find, add, remove 가 모두 루트에서 어떤 노드까지의 경로를 따라간다고 설명합니다. 따라서 트리의 높이가 커지면 모든 기본 연산도 함께 느려집니다.

NIST도 balanced BST나 height-balanced BST를 별도로 설명하면서, 이런 구조는 membership, insert, delete를 로그 시간으로 지원한다고 정리합니다. 즉 BST 다음에 AVL이나 red-black tree가 나오는 이유는 이론적 장식이 아니라, 편향 문제를 해결하기 위해서입니다.

핵심 포인트

BST는 검색 규칙 자체를 배우기에는 가장 좋은 구조지만, 실무에서 그대로 쓰기엔 편향이 큰 약점이 될 수 있습니다. 그래서 BST는 종착점이라기보다 균형 검색 트리로 들어가기 전의 핵심 출발점에 더 가깝습니다.

한계와 주의점

BST는 아름다운 검색 규칙을 가지지만, 균형을 스스로 보장하지 않기 때문에 삽입 순서가 나쁘면 성능이 쉽게 무너진다

가장 큰 문제는 편향입니다. 예를 들어 이미 정렬된 순서대로 값을 삽입하면 BST는 한쪽으로 길게 늘어져 사실상 연결 리스트처럼 될 수 있습니다.

이 경우 검색·삽입·삭제는 더 이상 짧은 경로를 보장하지 못하고, 연산 하나가 트리 높이만큼 길어집니다. 결국 BST property만으로는 충분하지 않고, 모양을 제어하는 별도 전략이 필요해집니다.

또 삭제 구현은 검색보다 훨씬 실수가 많습니다. 특히 자식이 둘인 노드에서 successor 치환과 실제 노드 제거를 제대로 분리하지 않으면 구조가 깨지기 쉽습니다.

주의해야 할 지점

• BST는 균형을 자동으로 보장하지 않음
• 삽입 순서가 나쁘면 height가 커져 성능이 급격히 나빠질 수 있음
• 삭제는 0개, 1개, 2개 자식 케이스를 분리해서 생각해야 함
• BST와 balanced BST를 같은 것으로 생각하면 안 됨

자주 하는 실수

BST를 어렵게 만드는 가장 흔한 원인은 정의 자체보다도, BST property와 균형 보장을 같은 것으로 착각하는 데 있다

• BST이면 자동으로 항상 빠를 것이라고 생각함
• 중위 순회가 모든 이진 트리에서 정렬 순이라고 착각함
• 삭제에서 자식 수에 따른 경우 분기를 제대로 나누지 않음
• 루트 교체가 필요한 삭제 케이스를 놓침
• BST와 heap을 비슷한 검색 구조로 생각함
• 편향된 트리의 height 문제를 노드 수만 보고 놓침

실무 루틴

BST를 사용할 때는 먼저 정렬 검색이 정말 필요한지 판단하고, 그다음 unbalanced BST로 충분한지 아니면 곧바로 balanced tree가 필요한지 결정하는 편이 안전하다

1. 먼저 데이터에 정렬 기반 탐색 이 필요한지 확인한다.
2. 검색, 삽입, 삭제가 모두 필요한지 보고 BST가 문제와 맞는지 본다.
3. 입력 순서가 편향을 만들 가능성이 크면 처음부터 balanced BST 를 고려한다.
4. 중위 순회 결과가 기대한 정렬 순서와 맞는지 테스트한다.
5. 삭제 로직은 leaf, single child, two children 케이스를 분리해서 검증한다.
6. 연산 수뿐 아니라 실제 height 변화도 함께 모니터링한다.

디버깅

BST 디버깅은 값 하나를 보는 것이 아니라, BST property 와 중위 순회 결과와 트리 높이가 동시에 기대와 맞는지 확인하는 과정이다

1

먼저 모든 노드에서 왼쪽 서브트리 값이 더 작고 오른쪽 값이 더 큰지 BST property 를 확인한다.

2

중위 순회 결과가 오름차순으로 나오지 않으면 구조가 이미 깨졌다고 보면 된다.

3

삽입과 삭제 뒤에는 루트 참조와 부모/자식 링크가 제대로 갱신됐는지 확인한다.

4

성능이 이상하면 노드 수보다도 먼저 트리 높이와 편향 여부를 측정한다.

5

삭제 버그는 대부분 successor 선택, splice, 루트 갱신 중 하나에서 발생하므로 그 부분을 집중적으로 본다.

점검 체크리스트
- BST property 가 모든 노드에서 유지되는가
- inorder 결과가 정렬 순인가
- root / parent / child 링크가 정상인가
- remove 케이스 분기가 정확한가
- 트리 height 가 비정상적으로 커지지 않았는가

요약

BST의 핵심은 왼쪽은 더 작고 오른쪽은 더 크다는 불변식을 통해 검색 범위를 단계적으로 줄이는 데 있으며, 모든 연산이 트리 높이에 의존하기 때문에 균형 여부가 실제 성능을 결정한다

• ✅ BST는 정렬 규칙을 구조 자체에 반영한 이진 트리다.
• ✅ 모든 노드에서 왼쪽 서브트리 키는 더 작고 오른쪽 서브트리 키는 더 커야 한다.
• ✅ 검색, 삽입, 삭제는 모두 root-to-node path 를 따라간다.
• ✅ 연산 비용은 노드 수보다 tree height 에 더 직접적으로 좌우된다.
• ✅ 중위 순회는 BST에서 정렬 순 방문이 된다.
• ✅ 삭제는 자식 수에 따라 leaf 제거, splice, successor 치환으로 나뉜다.
• ✅ 편향된 BST는 성능이 쉽게 무너질 수 있다.
• ✅ 그래서 BST 다음 단계로 balanced BST, AVL, red-black tree가 자연스럽게 이어진다.

 

RELATED POST

힙(Heap) 은 BST 와 무엇이 다를까
AVL 트리는 왜 BST 다음 단계로 등장할까
중위 순회가 BST 에서 정렬 순이 되는 이유

 

REFERENCE

binary search tree
in-order traversal
treesort (1)
balanced binary search tree
height-balanced binary search tree
Open Data Structures - BinarySearchTree