20강. 이진 탐색 트리 | 코딩 테스트 합격 알고리즘 30강 · 중급 — 누구나패스

🎯 학습 목표

이 강을 마치면 이진 탐색 트리(BST)의 규칙을 설명하고 탐색·삽입·삭제를 구현할 수 있습니다. 그리고 왜 중위 순회가 정렬된 결과를 주는지, 왜 편향되면 O(n)으로 무너지는지를 이해하고, 파이썬에서 실전 대안으로 무엇을 쓸지 판단할 수 있게 됩니다.

BST는 10강 이분 탐색을 트리로 옮긴 것입니다. 이분 탐색이 정렬된 배열에서 절반씩 버렸다면, BST는 구조 자체에 그 규칙을 새겨 삽입·삭제까지 빠르게 만듭니다.

💡 규칙 하나가 만드는 성질

이진 탐색 트리의 규칙은 하나뿐입니다. 모든 노드에 대해, 왼쪽 서브트리의 값은 자기보다 작고 오른쪽 서브트리의 값은 자기보다 크다.

BST 구조

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

  ▲ 8을 기준으로
    왼쪽 {3,1,6,4,7} 은 전부 8보다 작다
    오른쪽 {10,14,13} 은 전부 8보다 크다
    이것이 '모든 노드'에서 성립해야 한다  ★

  ▲ 서브트리 전체가 조건을 만족해야 한다
    바로 아래 자식만 비교하는 것이 아니다.

    잘못된 예
                 8
               /
              3
               \
                9    ← 3보다 크지만 8보다도 크다 → BST 아님

  탐색 — 이분 탐색과 같은 원리 (10강)

   6을 찾는다
    8과 비교 → 6 < 8 → 왼쪽으로
    3과 비교 → 6 > 3 → 오른쪽으로
    6과 비교 → 찾았다

   ▲ 한 번 비교할 때마다 절반가량이 사라진다
     → 균형 잡혔다면 O(log n)

  왜 중위 순회가 정렬인가 (19강)

   중위 = 왼쪽 → 자기 → 오른쪽
   왼쪽은 나보다 작고 오른쪽은 나보다 크다
   → 작은 것들 → 나 → 큰 것들 순서로 나온다
   → 재귀적으로 성립하므로 전체가 오름차순

   위 트리의 중위 순회: 1, 3, 4, 6, 7, 8, 10, 13, 14

📖 균형이 무너지면

BST의 성능은 전적으로 높이에 달려 있습니다. 그리고 높이는 값이 들어온 순서에 좌우됩니다.

같은 값, 다른 입력 순서

  [8, 3, 10, 1, 6, 14] 순서로 삽입

           8
         /   \
        3     10
       / \      \
      1   6      14
  높이 2 → 탐색 O(log n)  ✅

  [1, 3, 6, 8, 10, 14] 정렬된 순서로 삽입

      1
       \
        3
         \
          6
           \
            8
             \
              10
               \
                14
  높이 5 → 사실상 연결 리스트 → 탐색 O(n)  ❌

  ▲ 가장 흔한 함정
    정렬된 데이터를 그대로 넣으면 최악의 트리가 된다.

  복잡도 정리

   연산      균형 잡힘     편향
   ─────────────────────────────────
   탐색      O(log n)     O(n)
   삽입      O(log n)     O(n)
   삭제      O(log n)     O(n)
   중위순회  O(n)         O(n)

  ▲ 해결책 — 자가 균형 트리
    AVL 트리, 레드-블랙 트리 등은 삽입·삭제 때
    스스로 회전해 높이를 O(log n)으로 유지한다.
    구현이 복잡해 코딩 테스트에서 직접 짜는 일은 드물다.

  ▲ 파이썬 실전 선택
    · 정렬 상태가 필요하다 → 리스트 + bisect (10강)
    · 최솟값·최댓값만 필요 → 힙 (21강)
    · 조회만 빠르면 된다   → 딕셔너리·집합 (7강)
    → BST 를 직접 구현할 일은 거의 없다.
      개념과 성질을 이해하는 것이 목적이다.

💻 실전 예제 — BST 구현

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    """삽입 → 평균 O(log n). 새 루트를 반환한다"""
    if not root:
        return BSTNode(value)      # 빈 자리에 도착 → 여기가 자리
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root                    # 같은 값은 무시


def search(root, value):
    """탐색 → 평균 O(log n)"""
    current = root
    while current:                 # 반복문이라 깊이 제한이 없다
        if value == current.value:
            return True
        current = current.left if value < current.value else current.right
    return False


def find_min(node):
    """서브트리의 최솟값 노드 → 가장 왼쪽"""
    while node.left:
        node = node.left
    return node


def delete(root, value):
    """삭제 → 세 가지 경우로 나뉜다"""
    if not root:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if not root.left:          # ① 자식이 없거나 오른쪽만
            return root.right
        if not root.right:         # ② 왼쪽만
            return root.left
        successor = find_min(root.right)      # ③ 자식이 둘  ★
        root.value = successor.value          # 후계자 값을 올린다
        root.right = delete(root.right, successor.value)
    return root


def inorder(node, out):
    if not node:
        return
    inorder(node.left, out)
    out.append(node.value)
    inorder(node.right, out)


root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)

out = []
inorder(root, out)
print(out)                  # [1, 3, 4, 6, 7, 8, 10, 13, 14] — 정렬됨
print(search(root, 6), search(root, 5))   # True False

root = delete(root, 3)      # 자식이 둘인 노드 삭제
out = []
inorder(root, out)
print(out)                  # [1, 4, 6, 7, 8, 10, 13, 14]

코드를 줄 단위로 보겠습니다.

if not root: return BSTNode(value) — 내려가다 빈 자리에 닿으면 거기가 새 노드의 자리입니다. 이 반환값이 부모의 left·right에 연결됩니다.
root.left = insert(root.left, value) — 반환값을 다시 대입하는 패턴입니다. 트리를 수정하는 재귀 함수의 표준 형태이고, 이렇게 하면 부모 참조를 따로 관리할 필요가 없습니다.
while current: — 탐색은 반복문으로 구현했습니다. 편향 트리여도 재귀 깊이 제한에 걸리지 않습니다(13강).
current.left if ... else current.right — 조건 표현식으로 한 줄에 방향을 정합니다.
find_min(root.right) — 삭제의 핵심입니다. 자식이 둘인 노드를 지우려면 오른쪽 서브트리의 최솟값(중위 순회 기준 바로 다음 값)을 올려야 BST 규칙이 유지됩니다. 왼쪽 서브트리의 최댓값을 써도 됩니다.
root.value = successor.value — 노드를 옮기지 않고 값만 복사합니다. 그 뒤 후계자 노드를 삭제합니다. 후계자는 왼쪽 자식이 없으므로 ①·② 경우로 간단히 처리됩니다.
elif value > root.value — 같은 값은 어느 쪽으로도 가지 않아 중복이 무시됩니다. 중복을 허용하려면 개수를 세는 필드를 두는 방식이 일반적입니다.

삽입 순서가 [8, 3, 10, ...]이라 균형이 잡힌 트리가 만들어졌습니다. 같은 값들을 정렬된 순서로 넣으면 어떻게 되는지 직접 확인해 보면 편향 문제를 체감할 수 있습니다.

⚠️ 자주 하는 실수

첫째, 반환값을 대입하지 않습니다. insert(root.left, value)만 쓰고 root.left =를 빼면 새 노드가 트리에 연결되지 않습니다. 겉보기에는 동작하는 것 같아 찾기 어려운 버그입니다.

둘째, BST 판별에서 바로 아래 자식만 비교합니다. 서브트리 전체가 조건을 만족해야 합니다. 판별 함수를 만들 때는 허용 범위(min, max)를 인자로 내려보내는 방식이 정석입니다.

셋째, 정렬된 입력을 그대로 넣습니다. 최악의 편향 트리가 만들어집니다. 직접 구현한 BST를 쓸 때는 입력 순서를 섞는 것만으로도 크게 개선됩니다.

넷째, 삭제에서 자식이 둘인 경우를 대충 처리합니다. 아무 자식이나 끌어올리면 BST 규칙이 깨집니다. 반드시 중위 후계자 또는 중위 선행자를 써야 합니다.

다섯째, 코딩 테스트에서 BST를 직접 구현합니다. 시간도 오래 걸리고 균형도 보장되지 않습니다. bisect·힙·딕셔너리 중 하나로 대체할 수 있는지 먼저 검토하세요.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	규칙: 왼쪽 < 자기 < 오른쪽, 서브트리 전체에
2	탐색은 이분 탐색과 같은 원리
3	중위 순회 = 오름차순
4	성능은 높이에 달렸다 — 편향되면 O(n)
5	정렬된 입력이 최악을 만든다
6	수정 재귀는 반환값을 다시 대입
7	삭제 시 자식이 둘이면 중위 후계자

지금 해 볼 것은 같은 9개 값을 정렬된 순서 [1,3,4,6,7,8,10,13,14]로 삽입한 뒤 높이를 재 보는 것입니다. 19강의 height 함수를 그대로 쓰면 됩니다. 2와 8이라는 차이를 직접 보면 균형의 중요성이 각인됩니다.

다음 21강 「힙과 우선순위 큐」에서는 완전 이진 트리를 배열로 구현한 자료구조를 다룹니다. 전체를 정렬하지 않고도 최솟값·최댓값만 O(log n)에 꺼내는 구조이고, 25강 최단 경로의 필수 도구입니다.

이진 탐색 트리

🎯 학습 목표

💡 규칙 하나가 만드는 성질

📖 균형이 무너지면

💻 실전 예제 — BST 구현

⚠️ 자주 하는 실수

📝 핵심 요약 + 다음 강 예고

📚 참고 자료

관련 주제

코딩 테스트 합격 알고리즘 30강

댓글