27. 이진 트리

🎯 이 장의 목표

트리 자료구조의 개념과 용어를 안다.
이진 탐색 트리(BST)를 직접 구현한다.
재귀로 트리를 순회하는 세 가지 방법을 익힌다.
트리가 왜 빠른 검색을 제공하는지 이해한다.

먼저: 트리가 뭔가요?

지금까지 본 자료구조(리스트·스택·큐)는 데이터가 한 줄로 늘어선 선형 구조였습니다. 트리(tree)는 데이터가 가지치기하며 뻗어 나가는 계층 구조입니다. 가계도, 회사 조직도, 폴더 구조를 떠올리면 됩니다(나무를 뒤집어, 뿌리가 위에 있는 모양).

트리 용어부터 정리합시다.

flowchart TD
    Root["50 (루트 root)"]:::root --> A["30"]:::data
    Root --> B["70"]:::data
    A --> C["20 (리프 leaf)"]:::leaf
    A --> D["40 (리프)"]:::leaf
    B --> E["60 (리프)"]:::leaf
    B --> F["80 (리프)"]:::leaf

    classDef root fill:#fff3b0,stroke:#e0a800,color:#5c4500
    classDef data fill:#a8dadc,stroke:#457b9d,color:#1d3557
    classDef leaf fill:#b8e6c1,stroke:#34a853,color:#14532d

용어	의미
노드(node)	트리의 각 데이터 점
루트(root)	맨 위 노드 (시작점)
자식(child)	한 노드 아래에 연결된 노드
부모(parent)	한 노드 위에 연결된 노드
리프(leaf)	자식이 없는 끝 노드
높이(height)	루트에서 가장 깊은 리프까지의 단계

이진 트리(binary tree)는 각 노드가 자식을 최대 2개(왼쪽·오른쪽)만 갖는 트리입니다. 이번 장의 주인공입니다.

노드 클래스 만들기

트리는 노드들의 연결로 이뤄집니다. 각 노드는 값 하나와, 왼쪽·오른쪽 자식을 가리키는 참조를 가집니다(중급편 11장 클래스).

PYTHON

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None      # 왼쪽 자식 (없으면 None)
        self.right = None     # 오른쪽 자식

이 단순한 클래스로 트리 전체를 구성합니다. 각 노드가 자식 노드를 가리키고, 그 자식이 또 자식을 가리키는 식으로요(중급 12장에서 본 "객체가 객체를 참조").

PYTHON

# 손으로 작은 트리 만들기
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
#        1
#       / \
#      2   3
#     /
#    4
print(root.value)             # 1
print(root.left.value)        # 2
print(root.left.left.value)   # 4

⭐ 이진 탐색 트리(BST)

그냥 트리는 검색이 빠르지 않습니다. 이진 탐색 트리(Binary Search Tree, BST)는 규칙을 하나 추가합니다.

모든 노드에서: 왼쪽 자식들 < 자기 값 ≤ 오른쪽 자식들

즉 작은 값은 왼쪽, 큰 값은 오른쪽으로 갑니다. 이 규칙 덕분에 26장의 이진 탐색처럼 매 단계 절반을 버리며 빠르게 찾을 수 있습니다.

PYTHON

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:              # 작으면 왼쪽
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(node.left, value)
        else:                               # 크거나 같으면 오른쪽
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(node.right, value)

insert는 재귀로 자리를 찾아 내려갑니다. 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 내려가다가 빈 자리에 새 노드를 답니다.

PYTHON

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)
# 위의 첫 다이어그램과 같은 트리가 만들어짐
print(tree.root.value)         # 50  (처음 넣은 값이 루트)
print(tree.root.left.value)    # 30  (50보다 작아 왼쪽)
print(tree.root.right.value)   # 70  (50보다 커 오른쪽)

📎 _insert처럼 앞에 밑줄을 붙인 메서드는 "내부용"이라는 신호입니다(중급 12장 캡슐화). 사용자는 insert만 쓰고, 재귀 실제 작업은 _insert가 합니다.

검색: 절반씩 버리며 찾기

BST의 핵심 이점입니다. 찾는 값이 현재 노드보다 작으면 왼쪽만, 크면 오른쪽만 보면 됩니다. 나머지 절반은 볼 필요가 없습니다.

PYTHON

class BST:
    # ... (위에 이어서)
    def contains(self, value):
        return self._contains(self.root, value)

    def _contains(self, node, value):
        if node is None:
            return False                    # 끝까지 못 찾음
        if value == node.value:
            return True                     # 찾음!
        elif value < node.value:
            return self._contains(node.left, value)    # 왼쪽만
        else:
            return self._contains(node.right, value)   # 오른쪽만

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)
print(tree.contains(60))    # True
print(tree.contains(99))    # False

flowchart TD
    R["50"]:::p -->|"60 > 50<br/>오른쪽"| B["70"]:::p
    B -->|"60 < 70<br/>왼쪽"| E["60 ✅ 찾음!"]:::g
    R -.->|왼쪽 가지<br/>볼 필요 없음| A["30 (생략)"]:::data

    classDef p fill:#7fd8d8,stroke:#2a9d8f,color:#14532d
    classDef g fill:#b8e6c1,stroke:#34a853,color:#14532d
    classDef data fill:#d8d8d8,stroke:#999,color:#666

📌 핵심

핵심: BST는 "작으면 왼쪽, 크면 오른쪽" 규칙으로 매 단계 절반을 버린다. 균형 잡힌 트리에서 검색은 O(log n)이다. 26장 이진 탐색을 트리로 구현한 셈이다.

⭐ 트리 순회: 모든 노드 방문하기

트리의 모든 노드를 한 번씩 방문하는 것을 순회(traversal)라 합니다. 방문 순서에 따라 세 가지가 있고, 모두 재귀로 구현합니다.

순회	순서	특징
전위(preorder)	루트 → 왼쪽 → 오른쪽	트리 복사·구조 저장
중위(inorder)	왼쪽 → 루트 → 오른쪽	BST에서 정렬된 순서!
후위(postorder)	왼쪽 → 오른쪽 → 루트	트리 삭제·계산

세 함수의 차이는 append를 어디에 두느냐뿐입니다.

PYTHON

def preorder(node, result):     # 루트 먼저
    if node:
        result.append(node.value)       # ← 방문
        preorder(node.left, result)
        preorder(node.right, result)

def inorder(node, result):      # 루트 가운데
    if node:
        inorder(node.left, result)
        result.append(node.value)       # ← 방문
        inorder(node.right, result)

def postorder(node, result):    # 루트 마지막
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.value)       # ← 방문

위에서 만든 트리(50이 루트)로 실행하면:

PYTHON

r = []
inorder(tree.root, r)
print(r)    # [20, 30, 40, 50, 60, 70, 80]   ← 정렬되어 나옴!

중위 순회의 마법

BST를 중위 순회하면 값이 정렬된 순서로 나옵니다. "왼쪽(작은 값) → 자기 → 오른쪽(큰 값)" 순서로 방문하기 때문입니다. BST에 값을 넣어두고 중위 순회하면 곧 정렬이 됩니다.

💡 팁

순회가 모두 재귀인 이유: 트리는 "노드 + 왼쪽 서브트리 + 오른쪽 서브트리"인데, 서브트리도 또 트리입니다. 이런 "자기 안에 자기 구조가 든" 형태는 재귀로 다루는 게 자연스럽습니다(각 서브트리에 같은 함수를 적용).

📎 재귀(recursion)는 함수가 자기 자신을 부르는 것입니다. 트리 순회에서 inorder가 inorder(node.left)를 부르는 것처럼요. 각 호출이 더 작은 서브트리를 맡고, 노드가 없으면(if node:이 거짓) 멈춥니다.

트리의 높이

루트에서 가장 깊은 리프까지의 단계를 높이라 합니다. 검색 속도가 높이에 비례하므로 중요합니다. 재귀로 간단히 구합니다.

PYTHON

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

"내 높이 = 1 + (더 높은 쪽 자식의 높이)"라는 재귀입니다. 빈 곳(None)은 0입니다.

⚠️ 균형의 중요성

BST의 O(log n)은 트리가 균형 잡혔을 때 이야기입니다. 만약 정렬된 값을 순서대로 넣으면(1, 2, 3, 4, 5), 트리가 한쪽으로만 기울어 사실상 리스트가 됩니다.

flowchart TD
    N1["1"]:::r --> N2["2"]:::r
    N2 --> N3["3"]:::r
    N3 --> N4["4 ...한쪽으로만"]:::r

    classDef r fill:#f4b6b6,stroke:#d64545,color:#7a1f1f

이렇게 기울면 검색이 O(n)으로 느려집니다. 실무에서는 자동으로 균형을 맞추는 트리(AVL 트리, 레드-블랙 트리 등)를 쓰지만, 구현이 복잡합니다.

💡 팁

그래서 실무에서는 BST를 직접 구현하기보다, 이미 잘 만들어진 자료구조를 씁니다. Python의 딕셔너리·세트는 내부적으로 해시 테이블로 O(1) 검색을 제공하고, 정렬 유지가 필요하면 sortedcontainers 같은 라이브러리를 씁니다. 트리를 직접 배우는 이유는 "자료구조가 어떻게 효율을 만드는지" 원리를 이해하기 위함입니다.

📌 핵심

핵심: BST는 균형 잡혔을 때만 O(log n)이다. 한쪽으로 기울면 O(n)이 된다. 원리 이해가 목적이고, 실무에선 검증된 자료구조(dict·set)나 라이브러리를 쓴다.

이 장에서 배운 것

트리는 계층 구조다. 루트·자식·부모·리프·높이 용어를 안다. 이진 트리는 자식이 최대 2개.
이진 탐색 트리(BST)는 "작으면 왼쪽, 크면 오른쪽" 규칙으로 매 단계 절반을 버려 O(log n) 검색을 한다.
노드는 값과 left·right 참조를 가진 클래스로 만들고, insert·contains는 재귀로 내려간다.
순회는 세 가지: 전위·중위·후위. append 위치만 다르다. BST의 중위 순회는 정렬된 순서를 준다.
BST는 균형 잡혔을 때만 빠르다. 원리 이해가 목적이고, 실무에선 dict·set이나 검증된 라이브러리를 쓴다.

🧪 실습 문제

문제 1. 다음 BST에 [40, 20, 60, 10, 30]을 순서대로 insert하면 루트와 그 두 자식은 각각 무엇이 될까요?

문제 2. 트리 용어를 맞히세요: (a) 맨 위 노드, (b) 자식이 없는 끝 노드.

문제 3. BST를 중위 순회하면 왜 정렬된 순서가 나오는지 한 문장으로 설명하세요.

문제 4. 다음 트리를 전위·중위·후위 순회한 결과를 각각 적으세요.

TEXT

      A
     / \
    B   C
   / \
  D   E

문제 5. BST에 1, 2, 3, 4, 5를 순서대로 넣으면 트리 모양이 어떻게 되고, 검색 복잡도는 어떻게 될까요?

1. 루트 40(처음 값), 왼쪽 자식 20(40보다 작음), 오른쪽 자식 60(40보다 큼). 이후 10은 20의 왼쪽, 30은 20의 오른쪽으로 갑니다.

2. (a) 루트(root), (b) 리프(leaf).

3. 중위 순회는 "왼쪽(작은 값들) → 자기 → 오른쪽(큰 값들)" 순으로 방문하는데, BST는 왼쪽이 항상 작고 오른쪽이 항상 크므로 결과가 오름차순이 됩니다.

전위(루트→왼→오): A, B, D, E, C
중위(왼→루트→오): D, B, E, A, C
후위(왼→오→루트): D, E, B, C, A

5. 오른쪽으로만 길게 뻗은 사실상 리스트 모양(한쪽으로 기운 트리)이 됩니다. 검색 복잡도는 O(log n)이 아니라 O(n)으로 나빠집니다. 균형이 깨졌기 때문입니다.

</details>

◀️ 이전 장: 26. 복잡도와 핵심 자료구조 ｜ ▶️ 다음 장: 28. 미니 프로젝트: 로그 분석기

← 이전26. 복잡도와 핵심 자료구조다음 →28. 미니 프로젝트: 로그 분석기