이진 탐색 트리 (BST, Binary Search Tree)

JayJi·2026년 4월 12일

목록 보기

19/30

문제	난이도	핵심
5639번 — 이진 검색 트리	골드 V	전위 순회로 트리 복원
2250번 — 트리의 높이와 너비	골드 II	중위 순회 활용
1305번 — 두 수의 합	실버 I	BST 탐색

1. 개념

이진 탐색 트리(BST)는 모든 노드가 다음 조건을 만족하는 이진 트리다.

왼쪽 서브트리의 모든 값 < 현재 노드 < 오른쪽 서브트리의 모든 값

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

이 구조 덕분에 탐색, 삽입, 삭제가 평균 O(log N) 에 가능하다.

2. 동작 과정

탐색 — 6을 찾는 경우

단계	현재 노드	비교	이동
1	8	6 < 8	왼쪽
2	3	6 > 3	오른쪽
3	6	6 == 6	탐색 성공 ✅

삽입 — 5를 삽입하는 경우

단계	현재 노드	비교	이동
1	8	5 < 8	왼쪽
2	3	5 > 3	오른쪽
3	6	5 < 6	왼쪽
4	4	5 > 4	오른쪽 → null → 삽입 ✅

3. 순회 방식 3가지

BST를 순회하는 방식에 따라 결과가 달라진다.

순회 방식	순서	결과 (위 트리 기준)	특징
중위 순회 (In-order)	왼 → 현재 → 오	1 3 4 6 7 8 10 13 14	오름차순 정렬
전위 순회 (Pre-order)	현재 → 왼 → 오	8 3 1 6 4 7 10 14 13	트리 구조 복원
후위 순회 (Post-order)	왼 → 오 → 현재	1 4 7 6 3 13 14 10 8	트리 삭제

BST를 중위 순회하면 항상 오름차순 정렬된 결과가 나온다.

4. 핵심 포인트 2가지

균형이 무너지면 O(N)으로 느려진다

정렬된 순서로 삽입하면 한쪽으로만 치우친 편향 트리(Skewed Tree) 가 된다.

1, 2, 3, 4, 5 순서로 삽입 시:

1
 \
  2
   \
    3
     \
      4
       \
        5

이 경우 탐색/삽입/삭제가 O(N)으로 저하된다.
이를 해결하기 위해 AVL 트리, 레드-블랙 트리 같은 균형 BST가 사용된다.
Java의 TreeSet / TreeMap은 레드-블랙 트리로 구현되어 항상 O(log N)을 보장한다.

삭제는 3가지 경우로 나뉜다

경우	처리 방법
자식이 없는 경우 (리프)	그냥 제거
자식이 1개인 경우	해당 자식으로 대체
자식이 2개인 경우	오른쪽 서브트리의 최솟값(후계자)으로 대체

5. 코드

노드 클래스

class Node {
    int val;
    Node left, right;

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

탐색

Node search(Node root, int target) {
    if (root == null) return null;          // 탐색 실패
    if (root.val == target) return root;    // 탐색 성공

    if (target < root.val) return search(root.left, target);   // 왼쪽 탐색
    else return search(root.right, target);                     // 오른쪽 탐색
}

삽입

Node insert(Node root, int val) {
    if (root == null) return new Node(val);  // 빈 자리에 삽입

    if (val < root.val) root.left = insert(root.left, val);
    else if (val > root.val) root.right = insert(root.right, val);
    // val == root.val 이면 중복이므로 무시

    return root;
}

삭제

Node delete(Node root, int val) {
    if (root == null) return null;

    if (val < root.val) root.left = delete(root.left, val);
    else if (val > root.val) root.right = delete(root.right, val);
    else {
        // 자식이 없거나 1개
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;

        // 자식이 2개 → 오른쪽 서브트리의 최솟값으로 대체
        Node successor = getMin(root.right);
        root.val = successor.val;
        root.right = delete(root.right, successor.val);
    }
    return root;
}

Node getMin(Node node) {
    while (node.left != null) node = node.left;
    return node;
}

중위 순회 (오름차순 출력)

void inOrder(Node root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

6. 시간복잡도

연산	평균	최악 (편향 트리)
탐색	O(log N)	O(N)
삽입	O(log N)	O(N)
삭제	O(log N)	O(N)

최악을 방지하려면 균형 BST(TreeSet/TreeMap)를 사용하라.

7. 주의사항

중복 값 처리 방식을 미리 정해라. 중복을 허용할지, 무시할지, 카운트로 관리할지 문제에 따라 다르다.
직접 BST를 구현하는 문제는 드물다. 대부분 TreeSet / TreeMap으로 해결 가능하므로, 순회 방식과 구조 이해에 집중하라.
편향 트리에 주의하라. 정렬된 데이터를 그대로 삽입하면 O(N)으로 시간 초과가 날 수 있다.
전위 순회 결과만 주어지면 BST를 복원할 수 있다. BST의 성질 덕분에 전위 순회만으로 트리 구조가 유일하게 결정된다.