트리 구조와 계층 데이터 다루기

2026-06-03Views 61약 6분생성형 AI 활용

Summary

왜 트리가 필요한가

배열은 값을 한 줄로 나열할 때 좋습니다. 해시는 어떤 값이 있는지 빠르게 확인할 때 좋습니다. 하지만 데이터가 "위아래 관계"를 가지면 이야기가 달라집니다.

예를 들어 컴퓨터의 폴더 구조를 떠올려 봅시다.

프로젝트
├─ src
│  ├─ main.py
│  └─ util.py
└─ docs
   └─ readme.md

프로젝트 안에 src와 docs가 있고, src 안에는 다시 파일들이 있습니다. 회사 조직도도 비슷합니다. 대표 아래에 부서장이 있고, 부서장 아래에 팀원이 있습니다. 댓글과 대댓글 구조도 마찬가지입니다.

이처럼 데이터가 부모와 자식 관계로 이어질 때 사용하는 자료구조가 트리입니다. 트리는 계층적인 데이터를 표현하고, 원하는 항목을 찾거나, 전체 구조를 일정한 순서로 살펴보는 데 사용됩니다.

트리는 앞 장에서 배운 재귀와도 잘 맞습니다. 어떤 노드 아래에 있는 자식들도 다시 작은 트리로 볼 수 있기 때문입니다.

트리 구조와 계층 데이터 다루기 AI 생성 이미지

트리를 이루는 기본 용어

먼저 작은 트리를 하나 보겠습니다.

        A
      /   \
     B     C
    /      \
   D   E     F

이 그림에서 A, B, C, D, E, F는 각각 하나의 데이터입니다. 트리에서는 이런 데이터 하나를 노드라고 부릅니다.

노드와 노드를 연결하는 선은 간선입니다. 위 그림에서는 A-B, A-C, B-D, B-E, C-F가 간선입니다.

가장 위에 있는 A는 루트입니다. 루트는 트리의 시작점입니다. 파일 시스템으로 생각하면 최상위 폴더에 해당합니다.

A는 B와 C의 부모입니다. 반대로 B와 C는 A의 자식입니다. 같은 부모를 가진 B와 C는 형제 관계라고 볼 수 있습니다.

D, E, F처럼 자식이 없는 노드는 리프입니다. 나뭇잎처럼 더 아래로 뻗지 않는 끝 노드라는 뜻입니다.

깊이는 루트에서 얼마나 떨어져 있는지를 나타냅니다.

깊이 0: A
깊이 1: B, C
깊이 2: D, E, F

보통 루트의 깊이는 0으로 둡니다. 문제에 따라 루트 깊이를 1로 정의하기도 하므로, 깊이를 계산하는 문제에서는 기준을 먼저 확인해야 합니다.

또 하나 중요한 특징이 있습니다. 트리에서는 어떤 노드에서 아래쪽으로 이어진 부분도 다시 트리입니다.

     B
    / \
   D   E

이 부분을 B를 루트로 하는 서브트리라고 합니다. "큰 트리 안에 작은 트리가 들어 있다"는 관점은 재귀로 트리를 처리할 때 매우 중요합니다.

트리는 어떻게 저장할까

트리를 그림으로만 볼 수는 없습니다. 알고리즘에서는 트리를 코드로 표현해야 합니다.

자식 수가 정해져 있지 않은 일반 트리는 보통 각 노드가 자식 목록을 가지도록 저장합니다.

children[A] = [B, C]
children[B] = [D, E]
children[C] = [F]
children[D] = []
children[E] = []
children[F] = []

의사코드로 쓰면 다음과 같습니다.

children = {
    A: [B, C],
    B: [D, E],
    C: [F],
    D: [],
    E: [],
    F: []
}

반면 자식이 최대 두 개인 트리는 이진 트리라고 합니다. 이진 트리에서는 왼쪽 자식과 오른쪽 자식을 따로 저장합니다.

node.value
node.left
node.right

예를 들어 A의 왼쪽 자식이 B, 오른쪽 자식이 C라면 다음처럼 생각할 수 있습니다.

A.left = B
A.right = C

트리 문제를 만났을 때는 먼저 질문해야 합니다.

자식이 여러 명인가, 최대 두 명인가?
루트가 주어지는가?
부모에서 자식으로만 내려가면 되는가?
모든 노드를 한 번씩 방문해야 하는가?
특정 값을 빠르게 찾아야 하는가?

이 질문에 따라 저장 방식과 알고리즘이 달라집니다.

순회: 트리의 모든 노드를 방문하는 방법

트리에서 순회란 노드를 일정한 순서로 모두 방문하는 과정입니다. 배열은 왼쪽에서 오른쪽으로 순회하면 됩니다. 하지만 트리는 가지가 나뉘므로 "어느 노드를 먼저 볼 것인가"를 정해야 합니다.

대표적인 깊이 우선 순회에는 세 가지가 있습니다.

전위 순회: 현재 노드를 먼저 방문한다.
중위 순회: 왼쪽을 방문한 뒤 현재 노드를 방문한다.
후위 순회: 자식들을 먼저 방문한 뒤 현재 노드를 방문한다.

다음 이진 트리를 기준으로 비교해 보겠습니다.

        A
      /   \
     B     C
    /      \
   D   E     F

전위 순회: 나를 먼저 보고 내려가기

전위 순회는 현재 노드를 먼저 방문합니다. 그다음 왼쪽 서브트리, 오른쪽 서브트리 순서로 내려갑니다.

방문 순서: A → B → D → E → C → F

의사코드는 다음과 같습니다.

preorder(node):
    if node is null:
        return

    visit(node)
    preorder(node.left)
    preorder(node.right)

전위 순회는 폴더 구조를 출력할 때 자연스럽습니다. 먼저 현재 폴더 이름을 출력하고, 그 안의 하위 폴더와 파일을 출력하는 방식입니다.

중위 순회: 왼쪽, 나, 오른쪽

중위 순회는 왼쪽 서브트리를 먼저 방문하고, 그다음 현재 노드, 마지막으로 오른쪽 서브트리를 방문합니다.

방문 순서: D → B → E → A → C → F

의사코드는 다음과 같습니다.

inorder(node):
    if node is null:
        return

    inorder(node.left)
    visit(node)
    inorder(node.right)

중위 순회는 특히 이진 탐색 트리에서 중요합니다. 왼쪽에는 작은 값, 오른쪽에는 큰 값이 있다는 규칙이 있으면 중위 순회 결과가 정렬된 순서로 나오기 때문입니다.

일반적인 트리에서는 중위 순회가 항상 특별한 의미를 갖지는 않습니다. 자식이 여러 명인 트리에는 "왼쪽과 오른쪽"이라는 기준이 분명하지 않을 수 있습니다.

후위 순회: 아래를 끝내고 나를 처리하기

후위 순회는 자식 노드를 모두 방문한 뒤 현재 노드를 방문합니다.

방문 순서: D → E → B → F → C → A

의사코드는 다음과 같습니다.

postorder(node):
    if node is null:
        return

    postorder(node.left)
    postorder(node.right)
    visit(node)

후위 순회는 하위 작업을 먼저 끝내야 할 때 사용합니다. 예를 들어 폴더를 삭제할 때는 폴더 안의 파일과 하위 폴더를 먼저 삭제해야 합니다. 비어 있지 않은 폴더를 바로 지우면 문제가 생길 수 있기 때문입니다.

트리 순회는 대부분의 경우 모든 노드를 한 번씩 방문합니다. 노드 수를 n이라고 하면 시간 복잡도는 보통 O(n)입니다. 재귀 호출을 사용하면 트리의 높이만큼 호출 스택이 쌓이므로, 공간도 함께 고려해야 합니다.

이진 탐색 트리: 규칙이 있으면 더 빨리 찾을 수 있다

트리가 단순히 계층을 표현하는 데만 쓰이는 것은 아닙니다. 값을 빠르게 찾기 위해 특별한 규칙을 가진 트리도 있습니다. 대표적인 예가 이진 탐색 트리입니다.

이진 탐색 트리는 다음 규칙을 가집니다.

왼쪽 서브트리의 값은 현재 노드보다 작다.
오른쪽 서브트리의 값은 현재 노드보다 크다.
이 규칙은 모든 노드에서 반복된다.

예를 들어 다음 트리를 봅시다.

        8
      /   \
     3     10
    /       \
   1   6      14

6을 찾는다고 해 봅시다.

루트 8과 비교합니다. 6은 8보다 작으므로 왼쪽으로 갑니다.
3과 비교합니다. 6은 3보다 크므로 오른쪽으로 갑니다.
6을 찾았습니다.

전체 노드를 다 보지 않았습니다. 비교할 때마다 한쪽 서브트리를 버렸습니다. 이 점이 이진 탐색과 비슷합니다.

탐색 의사코드는 다음과 같습니다.

search(node, target):
    if node is null:
        return false

    if node.value == target:
        return true

    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)

트리의 높이가 낮게 유지되면 탐색 시간은 O(log n)에 가깝습니다. 하지만 값이 한쪽으로만 들어오면 문제가 생깁니다.

이런 모양은 사실상 연결 리스트처럼 됩니다. 이 경우 탐색은 최악의 경우 O(n)이 될 수 있습니다. 그래서 이진 탐색 트리는 "규칙"뿐 아니라 "균형"도 중요합니다.

중위 순회를 하면 값이 정렬된 순서로 나온다는 점도 기억해 둡시다.

중위 순회 결과: 1 → 3 → 6 → 8 → 10 → 14

이 성질은 정렬된 출력, 범위 검색, 순위 계산 같은 문제에서 자주 활용됩니다.

힙: 가장 중요한 값을 빠르게 꺼내기

힙도 트리의 한 종류입니다. 힙은 "부모와 자식 사이의 우선순위"를 지키는 자료구조입니다.

힙에는 대표적으로 두 종류가 있습니다.

최소 힙: 부모가 자식보다 작거나 같다. 따라서 루트가 최솟값이다.
최대 힙: 부모가 자식보다 크거나 같다. 따라서 루트가 최댓값이다.

최소 힙 예시는 다음과 같습니다.

루트 1이 가장 작습니다. 부모는 자식보다 작거나 같습니다. 하지만 전체가 완전히 정렬되어 있는 것은 아닙니다. 예를 들어 4가 5보다 작지만, 반드시 5보다 위에 있어야 하는 것은 아닙니다. 힙에서 중요한 규칙은 부모와 자식 사이의 관계입니다.

힙은 보통 배열로 구현합니다. 트리를 배열에 담으면 인덱스로 부모와 자식을 계산할 수 있습니다.

index i의 왼쪽 자식  = 2 * i + 1
index i의 오른쪽 자식 = 2 * i + 2
index i의 부모       = (i - 1) // 2

최소 힙에서 값을 넣을 때는 일단 마지막에 추가한 뒤, 부모보다 작으면 위로 올립니다.

heap_push(heap, value):
    heap.append(value)
    i = last index

    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        swap(heap[parent], heap[i])
        i = parent

최솟값을 꺼낼 때는 루트를 제거해야 합니다. 하지만 루트를 바로 빼면 트리 모양이 깨지므로, 마지막 값을 루트로 옮긴 뒤 아래로 내려보내며 규칙을 복구합니다.

heap_pop(heap):
    answer = heap[0]
    heap[0] = heap[last index]
    remove last element

    i = 0
    while left child exists:
        smaller = left child index
        if right child exists and heap[right] < heap[left]:
            smaller = right child index

        if heap[i] <= heap[smaller]:
            break

        swap(heap[i], heap[smaller])
        i = smaller

    return answer

힙에서는 루트 확인이 O(1)입니다. 값을 넣거나 꺼낼 때는 위아래로 이동하며 트리 높이만큼만 비교하므로 보통 O(log n)입니다.

힙은 다음과 같은 상황에서 자주 쓰입니다.

가장 작은 값부터 처리해야 할 때
가장 큰 값 k개를 유지해야 할 때
우선순위가 높은 작업을 먼저 처리해야 할 때
뒤에서 배울 최단 경로 알고리즘처럼, 현재 가장 유리한 후보를 빠르게 꺼내야 할 때

여기서 주의할 점은 힙과 이진 탐색 트리가 다르다는 것입니다. 이진 탐색 트리는 왼쪽이 작고 오른쪽이 큽니다. 힙은 부모가 자식보다 우선한다는 규칙만 지킵니다. 그래서 힙에서 특정 값을 찾는 것은 빠르지 않습니다. 힙은 "최댓값 또는 최솟값을 빠르게 꺼내는 데" 강합니다.

자주 틀리는 부분

첫째, 트리와 그래프를 혼동하기 쉽습니다. 트리는 연결 관계를 가진다는 점에서 그래프와 비슷하지만, 보통 하나의 루트에서 시작하고 부모-자식 계층이 뚜렷합니다. 또한 노드가 n개인 트리는 간선이 n - 1개입니다.

둘째, 깊이 기준을 확인하지 않고 계산하면 답이 어긋납니다. 어떤 문제는 루트 깊이를 0으로 두고, 어떤 문제는 1로 둡니다. 구현보다 먼저 기준을 읽어야 합니다.

셋째, 순회 순서를 헷갈리기 쉽습니다. 전위는 "나 먼저", 중위는 "왼쪽-나-오른쪽", 후위는 "나중에 나"입니다. 외우기보다 작은 트리에 직접 방문 번호를 적어 보면 실수가 줄어듭니다.

넷째, 빈 자식을 처리하지 않으면 오류가 납니다. 재귀 순회에서는 node is null일 때 바로 돌아가는 종료 조건이 필요합니다.

다섯째, 이진 탐색 트리가 항상 빠르다고 생각하면 안 됩니다. 균형이 무너지면 높이가 커지고, 탐색도 느려집니다. "왼쪽은 작고 오른쪽은 크다"는 규칙과 "높이가 낮다"는 조건이 함께 있어야 빠릅니다.

여섯째, 힙을 정렬된 배열처럼 생각하면 안 됩니다. 힙은 루트가 최솟값 또는 최댓값이라는 점이 핵심입니다. 전체 원소가 순서대로 정렬되어 있지는 않습니다.

트리는 계층을 표현하는 기본 도구입니다. 순회는 트리 전체를 읽는 방법이고, 이진 탐색 트리와 힙은 규칙을 추가해 특정 작업을 빠르게 만든 구조입니다. 다음 장에서 다룰 그래프는 트리보다 더 자유로운 연결 관계를 표현합니다. 트리를 먼저 이해하면 그래프 탐색도 훨씬 자연스럽게 받아들일 수 있습니다.

책 목록

쉽게 배우는 프로그래밍 알고리즘

전체 목차 보기