트리(Tree): 계층적 데이터 구조

프롤로그 - 배열만 쓰다가 막막했던 순간

처음 프로그래밍을 배울 때 나는 배열과 리스트만 알고 있었다. 데이터를 일렬로 쭉 나열하는 구조. 학생 명단, 쇼핑 리스트, 할 일 목록 같은 것들을 저장하기엔 완벽했다. 그런데 실제 프로젝트를 하다 보니 "일렬로 세울 수 없는" 데이터들이 나타나기 시작했다.

회사 조직도를 데이터로 저장해야 하는 상황이 있었다. CEO 밑에 CTO와 CFO가 있고, CTO 밑에 개발팀장이 있고, 그 밑에 개발자들이 있는 구조. 배열로 이걸 어떻게 표현하지? ["CEO", "CTO", "CFO", "개발팀장", "개발자1", "개발자2"] 이렇게? 그럼 누가 누구 밑에 있는지 어떻게 알지?

파일 탐색기를 보면서 깨달았다. 내 컴퓨터의 폴더 구조는 절대 일렬로 정렬될 수 없다. C:\ 밑에 Users, Program Files가 있고, Users 밑에 또 내 이름의 폴더가 있고, 그 안에 Documents, Downloads가 있다. 이건 계층(Hierarchy)이다. 위아래가 있고, 부모-자식 관계가 있다.

그때 배운 게 트리(Tree) 자료구조였다.

처음엔 이해 못 했다 - "왜 나무인데 거꾸로야?"

트리라는 이름을 처음 들었을 때 당황했다. 나무는 뿌리가 아래 있고 가지가 위로 뻗어나가는데, CS에서 트리는 반대다. Root(뿌리)가 맨 위에 있고, 가지가 아래로 뻗어나간다. 왜 거꾸로 그리는 거지?

나중에 이해했다. 이건 "그림의 편의"였다. 컴퓨터에서 데이터를 표현할 때 "시작점"을 위에 두는 게 직관적이기 때문이다. 조직도를 생각해 보라. CEO를 맨 위에 그리고, 밑으로 부서장들을 그리고, 더 밑으로 팀원들을 그린다. 족보도 마찬가지다. 시조 할아버지를 맨 위에 두고 자손들을 밑으로 뻗어나가게 그린다.

결국 "거꾸로 된 나무"가 아니라, "시작점이 위에 있는 계층도"라고 받아들였다.

용어의 늪: Root, Parent, Child, Leaf, Depth, Height...

트리를 배우면서 제일 짜증 났던 게 용어가 너무 많다는 것이었다. Root, Parent, Child, Sibling, Leaf, Internal Node, Depth, Height, Level... 대체 이게 뭐가 다른 건지 헷갈렸다.

나는 이렇게 정리했다. 가족 족보 + 회사 조직도로 비유하면 모든 용어가 명확해진다.

Root (뿌리)

가장 꼭대기에 있는 노드. 시조 할아버지. 회사로 치면 CEO. 컴퓨터 파일 시스템으로 치면 C:\ 드라이브. 트리는 반드시 Root가 하나만 존재한다. 두 개면 그건 숲(Forest)이다.

Parent (부모)와 Child (자식)

직속 상하 관계. 내 바로 위 상사가 Parent, 내 바로 아래 부하가 Child다. 한 노드는 여러 Child를 가질 수 있지만, Parent는 단 하나만 갖는다. (Root는 Parent가 없다.)

Sibling (형제)

같은 Parent를 가진 노드들. 같은 상사 밑에서 일하는 동료들.

Leaf (잎)

더 이상 Child가 없는 노드. 말단 사원. 인턴. 파일 시스템으로 치면 실제 파일(폴더가 아닌).

Internal Node (내부 노드)

적어도 하나 이상의 Child를 가진 노드. Root도 Child가 있으면 Internal Node다. 팀장급 이상.

Depth (깊이)

Root로부터 얼마나 멀리 떨어져 있는가. Root의 Depth는 0이다. Root의 Child들은 Depth 1, 그 Child들은 Depth 2... 회사로 치면 "몇 단계 아래 직원인가".

Height (높이)

어떤 노드에서 가장 멀리 떨어진 Leaf까지의 거리. Leaf의 Height는 0이다. 트리 전체의 Height는 Root의 Height다. "이 노드 밑에 몇 계급이 더 남았는가".

Level (레벨)

Depth와 같은 의미로 쓰이기도 하는데, 보통 "같은 Depth에 있는 노드들의 집합"을 의미한다. Level 0은 Root만, Level 1은 Root의 자식들, Level 2는 손자들...

처음엔 Depth랑 Height를 헷갈렸는데, 이렇게 이해했다. Depth는 위에서부터 재고, Height는 아래에서부터 잰다. 마치 건물을 생각하면 된다. 1층, 2층, 3층은 Depth고, "이 건물은 10층 높이야"는 Height다.

트리의 종류 - Binary Tree가 제일 흔하다

트리에는 여러 종류가 있는데, 나는 처음에 "트리는 트리지, 뭐가 다르냐"고 생각했다. 하지만 Child의 개수 제한에 따라 성질이 완전히 달라진다는 걸 알았다.

일반 트리 (General Tree / N-ary Tree)

Child 개수에 제한이 없다. CEO 밑에 10명의 임원이 있어도 되고, 50명이 있어도 된다. 폴더 안에 파일이 1,000개 있어도 된다. 유연하지만, 알고리즘 설계가 복잡해진다.

이진 트리 (Binary Tree)

각 노드가 최대 2개의 Child만 가질 수 있는 트리. Left Child와 Right Child. 알고리즘 문제의 90%가 이진 트리다. 왜냐하면 구현이 단순하고, 재귀 구조로 다루기 쉽기 때문이다.

나는 이진 트리를 "스무고개"로 이해했다. 질문을 하나 할 때마다 가능성을 둘로 쪼갠다. "동물이야?" → Yes/No → 다시 "날 수 있어?" → Yes/No... 이런 식으로 계속 반으로 나누면 빠르게 정답에 도달한다.

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

이진 트리의 특수한 형태. 왼쪽 Child는 Parent보다 작고, 오른쪽 Child는 Parent보다 크다는 규칙이 있다. 이 규칙 덕분에 검색이 엄청 빨라진다.

예를 들어 [1, 3, 5, 7, 9, 11, 13]이라는 정렬된 배열이 있다면, BST로 만들면 다음과 같다:

7을 찾고 싶으면 Root 확인, 끝. 1을 찾고 싶으면 Root보다 작으니 왼쪽, 3보다 작으니 또 왼쪽, 찾았다. 최대 3번만에 찾는다. 배열에서 순차 탐색하면 7번 걸릴 수도 있는데.

하지만 BST의 문제는 "균형이 깨지면" 효율이 개판된다는 것이다. [1, 2, 3, 4, 5]를 순서대로 BST에 넣으면:

이건 그냥 일렬로 늘어선 배열이랑 똑같다. 검색 시간이 O(n)으로 폭망한다.

균형 잡힌 트리 (Balanced Tree)

그래서 나온 게 AVL Tree, Red-Black Tree 같은 "자동으로 균형을 맞춰주는" 트리들이다. 노드를 삽입/삭제할 때마다 트리를 재배치해서 Height를 최소화한다. 덕분에 검색 시간이 항상 O(log n)으로 보장된다.

나는 데이터베이스 인덱스가 B-Tree라는 균형 트리로 구현된다는 걸 알았을 때 "아, 그래서 DB가 빠른 거구나" 싶었다.

Aha Moment: "파일 탐색기가 트리였구나"

트리를 이해한 결정적 순간은 Windows 탐색기를 보면서였다. 왼쪽 폴더 트리 구조를 보는데, 갑자기 전구가 켜졌다. "이게 바로 트리잖아?"

C:\ → Root
Users, Program Files → Root의 Children
Users\RATIA → Users의 Child
RATIA\Documents\report.docx → Leaf (실제 파일)

폴더를 클릭하면 펼쳐지고, 다시 클릭하면 접히는 것도 트리의 "탐색(Traversal)"이었다. 나는 매일 트리를 사용하고 있었던 거다.

웹 페이지의 HTML DOM도 마찬가지였다. <html> 태그가 Root고, <head>와 <body>가 Children이고, <div>, <p>, <span> 이런 게 다 노드들이다. 브라우저가 페이지를 렌더링할 때 이 트리를 순회하면서 각 요소를 그린다.

회사 조직도, 족보, 토너먼트 대진표, 의사결정 흐름도... 모든 게 트리였다.

트리 순회 - 어떤 순서로 방문할 것인가?

트리를 만들었으면 이제 "모든 노드를 빠짐없이 방문"해야 하는 경우가 있다. 파일 시스템에서 모든 파일 크기를 합산한다거나, DOM에서 모든 텍스트를 추출한다거나.

문제는 트리는 "일렬로 늘어선 게 아니라서" 순서가 명확하지 않다는 것이다. 배열은 앞에서부터 뒤로 가면 그만이지만, 트리는 "위에서 아래로" 갈 때도 여러 갈래가 있다.

나는 트리 순회(Tree Traversal)의 4가지 방법을 처음 배울 때 "이게 대체 왜 필요하냐"고 생각했다. 그런데 각각의 순회 방식이 해결하는 문제가 다르다는 걸 알고 나서 이해했다.

전위 순회 (Preorder Traversal): Root → Left → Right

"나 먼저, 그 다음 자식들"

폴더를 복사할 때 이 순서다. 먼저 폴더를 만들고, 그 안의 파일들을 복사한다. Root부터 처리해야 하는 경우에 쓴다.

def preorder(node):
    if node is None:
        return
    print(node.value)  # 나 먼저
    preorder(node.left)  # 왼쪽 자식
    preorder(node.right)  # 오른쪽 자식

중위 순회 (Inorder Traversal): Left → Root → Right

"왼쪽 끝까지 가고, 나, 그 다음 오른쪽"

BST에서 이 순서로 순회하면 정렬된 순서로 출력된다! 이게 진짜 신기했다. BST의 특성(왼쪽 < Root < 오른쪽) 때문에 자동으로 오름차순 정렬이 된다.

def inorder(node):
    if node is None:
        return
    inorder(node.left)  # 왼쪽 끝까지
    print(node.value)  # 나
    inorder(node.right)  # 오른쪽

후위 순회 (Postorder Traversal): Left → Right → Root

"자식들 먼저, 그 다음 나"

폴더를 삭제할 때 이 순서다. 먼저 안의 파일들을 다 지우고, 마지막에 폴더 자체를 지운다. 파일 크기를 계산할 때도 이 방식이다. 하위 폴더들의 크기를 먼저 계산하고, 그걸 합쳐서 상위 폴더 크기를 구한다.

def postorder(node):
    if node is None:
        return
    postorder(node.left)  # 왼쪽 자식들
    postorder(node.right)  # 오른쪽 자식들
    print(node.value)  # 마지막에 나

레벨 순서 순회 (Level-order Traversal) - 위에서 아래로, 같은 레벨끼리

BFS(Breadth-First Search)라고도 한다. Root부터 시작해서 같은 깊이에 있는 노드들을 먼저 다 방문하고, 그 다음 깊이로 내려간다.

조직도에서 "1급 임원들 → 2급 팀장들 → 3급 팀원들" 순서로 방문하는 것과 같다. 큐(Queue)를 사용해서 구현한다.

from collections import deque

def level_order(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

나는 Level-order를 "폭 우선 탐색"이라고 외우는 대신, "같은 계급끼리 먼저 처리"라고 기억했다.

코드로 구현 - 노드 클래스부터 시작

이론은 알겠는데, 실제로 코드로 어떻게 만들지? 나는 처음에 트리를 "배열로 표현"하려고 했다가 망했다. 배열의 인덱스를 계산하는 게 너무 복잡했다.

결국 노드 클래스를 만드는 게 제일 직관적이라는 걸 깨달았다. 각 노드는 자기 값(value)과 자식들에 대한 포인터(reference)를 갖는다.

이진 트리 노드 구현

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

# 트리 만들기
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

#       1
#      / \
#     2   3
#    / \
#   4   5

간단하다. 각 노드는 value, left, right 세 개의 속성만 갖는다. left와 right는 다른 노드를 가리키거나, 없으면 None이다.

BST에 노드 삽입하기

BST는 규칙이 있으니까 삽입도 자동으로 위치가 정해진다. "작으면 왼쪽, 크면 오른쪽"을 반복하면 된다.

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

    def insert(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = TreeNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = TreeNode(value)
            else:
                self._insert_recursive(node.right, value)

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

# 사용 예시
bst = BST()
bst.insert(7)
bst.insert(3)
bst.insert(11)
bst.insert(1)
bst.insert(5)

print(bst.search(5))  # True
print(bst.search(10))  # False

재귀(Recursion)를 사용하니까 코드가 깔끔하다. 트리는 "자기 자신과 같은 구조"를 반복하는 재귀적 구조이기 때문에, 재귀 함수로 구현하는 게 자연스럽다.

처음엔 재귀가 어려웠는데, "내가 할 일만 하고 나머지는 자식한테 맡긴다"는 마인드로 접근하니까 이해가 됐다. insert 함수는 "이 값이 내 왼쪽인지 오른쪽인지만 판단"하고, 실제 삽입은 자식 노드의 insert에게 위임한다.

실제 응용 - 파일 시스템 크기 계산

이론과 코드를 배웠으니, 실제 문제를 풀어보자. "폴더의 전체 크기를 계산하는 함수"를 만든다고 해 보자. 폴더 안에 파일도 있고, 하위 폴더도 있다. 하위 폴더 안에 또 파일과 폴더가 있을 수 있다.

이건 전형적인 트리 문제다. 폴더가 노드고, 하위 폴더/파일이 자식들이다. 후위 순회로 풀어야 한다. 왜냐하면 하위 폴더들의 크기를 먼저 알아야 상위 폴더 크기를 계산할 수 있기 때문이다.

class FileNode:
    def __init__(self, name, size=0, is_folder=False):
        self.name = name
        self.size = size  # 파일이면 실제 크기, 폴더면 0
        self.is_folder = is_folder
        self.children = []  # 폴더만 자식을 가짐

    def add_child(self, child):
        self.children.append(child)

def calculate_folder_size(node):
    if not node.is_folder:
        # 파일이면 자기 크기 반환
        return node.size

    # 폴더면 모든 자식의 크기를 합산
    total_size = 0
    for child in node.children:
        total_size += calculate_folder_size(child)  # 재귀

    return total_size

# 파일 시스템 구조 만들기
root = FileNode("C:", is_folder=True)
users = FileNode("Users", is_folder=True)
documents = FileNode("Documents", is_folder=True)
file1 = FileNode("report.docx", size=500)
file2 = FileNode("image.png", size=1200)

documents.add_child(file1)
documents.add_child(file2)
users.add_child(documents)
root.add_child(users)

print(f"Total size: {calculate_folder_size(root)} KB")  # 1700

이 코드를 돌려보니 "아, 내가 트리를 이해한 거구나" 싶었다. 재귀로 자식들을 먼저 처리하고, 그 결과를 합쳐서 부모의 결과를 만든다. 이게 바로 후위 순회의 핵심이다.

다른 응용 - DOM에서 모든 텍스트 추출

웹 페이지에서 모든 텍스트를 추출한다고 해 보자. HTML DOM은 트리 구조다. <div> 안에 <p>가 있고, <p> 안에 텍스트가 있다. 모든 노드를 방문하면서 텍스트를 모아야 한다.

이건 전위 순회나 중위 순회나 상관없다. 모든 노드를 방문하기만 하면 된다.

function extractAllText(element) {
    let text = '';

    // 텍스트 노드면 그대로 추가
    if (element.nodeType === Node.TEXT_NODE) {
        return element.textContent;
    }

    // 요소 노드면 자식들 순회
    for (let child of element.childNodes) {
        text += extractAllText(child);
    }

    return text;
}

// 사용 예시
const bodyText = extractAllText(document.body);
console.log(bodyText);

이것도 재귀다. "나의 텍스트 + 자식들의 텍스트"를 합치면 끝.

정리 - 트리는 "관계"를 표현하는 도구다

처음 트리를 배울 때 나는 "이게 배열이랑 뭐가 다르지? 더 복잡하기만 한데?"라고 생각했다. 하지만 실제로 쓰다 보니 깨달았다. 트리는 "관계"를 표현하는 도구다.

배열은 "순서"를 표현한다. 1등, 2등, 3등. 첫 번째 아이템, 두 번째 아이템. 하지만 현실 세계의 많은 것들은 순서가 아니라 "계층"이다. 상사-부하, 부모-자식, 폴더-파일, 카테고리-하위카테고리.

나는 이제 이런 상황에서 자연스럽게 트리를 떠올린다:

조직도를 만들어야 한다 → 트리
파일 시스템을 탐색해야 한다 → 트리
웹 페이지를 파싱해야 한다 → 트리 (DOM)
빠른 검색이 필요하다 → BST 또는 균형 트리
라우팅 규칙을 관리해야 한다 → 트리 (Trie)

트리의 진짜 힘은 재귀적 구조 때문이다. 트리의 부분도 트리다. 서브트리(Subtree)라고 한다. 이 성질 덕분에 재귀 알고리즘이 딱 맞아떨어진다. 문제를 더 작은 문제로 쪼개고, 쪼개고, 쪼개서 해결한다.

결론적으로, 나는 트리를 이렇게 정리해본다:

트리는 "하나의 시작점(Root)에서 여러 갈래로 뻗어나가는 계층 구조"다. 부모-자식 관계가 명확하고, 순환(Cycle)이 없다. 파일 시스템, 조직도, DOM, 데이터베이스 인덱스 등 현실의 수많은 계층 구조를 표현하는 데 쓰인다. 재귀적 특성 덕분에 코드 구현도 재귀 함수로 깔끔하게 떨어진다.

배열만 알던 시절로는 돌아갈 수 없다. 트리를 알고 나니 세상이 다르게 보인다.