트리

트리는 데이터를 뿌리 하나에서 갈래로 뻗어 나가게 담습니다. 위에서 아래로 갈라지기만 합니다. 한 번 갈라진 갈래끼리는 다시 만나지 않습니다. 그래서 무엇을 찾든 갈래 하나를 고르는 순간 나머지 갈래는 볼 필요가 없어집니다.

상세

트리를 이루는 부품과 이름을 먼저 정합니다. 그다음 트리를 트리이게 만드는 제한 두 개를 봅니다. 그 제한이 성능으로 이어지는 길까지 따라갑니다.

뿌리와 잎, 부모와 자식

트리는 값을 담은 상자와 상자를 잇는 선으로 이루어집니다. 값을 담은 상자는 노드입니다. 노드와 노드를 잇는 선은 간선입니다.

맨 위에 있는 노드는 하나뿐입니다. 이 노드가 루트, 곧 뿌리입니다.

어떤 노드 바로 위에 붙은 노드는 그 노드의 부모입니다. 바로 아래에 붙은 노드들은 자식입니다. 자식이 하나도 없는 노드는 리프, 곧 잎입니다.

한 노드와 그 아래에 딸린 것을 전부 떼어 내면 그것도 다시 트리입니다. 이렇게 떼어 낸 조각이 서브트리입니다. 한 조각이 원래와 똑같이 생겼으니, 트리를 다루는 함수는 그 조각에 자기 자신을 다시 쓸 수 있습니다(뒤 「높이를 재는 코드」).

flowchart TD
    R["뿌리 · A"] --> B["B"]
    R --> C["C"]
    subgraph SUB["서브트리"]
        B --> D["잎 · D"]
        B --> E["잎 · E"]
    end
    C --> F["잎 · F"]

그림에서 B 의 부모는 A 입니다. 자식은 D 와 E 입니다. D·E·F 는 아래에 아무것도 없으니 잎입니다.

B 와 그 아래 D·E 를 묶은 상자가 서브트리입니다. 그것만 떼어 봐도 뿌리가 B 인 트리입니다.

트리를 트리이게 하는 제한 두 개

트리에는 제한이 둘 걸립니다. 노드마다 부모가 하나뿐입니다. 그리고 간선을 따라가다 출발한 노드로 되돌아오는 길이 없습니다.

이 제한이 풀린 것이 그래프입니다. 그래프에서는 한 노드로 간선이 여럿 들어와도 됩니다. 빙 돌아 제자리로 오는 길이 있어도 됩니다.

flowchart TD
    subgraph 두부모["부모가 둘 · 트리 아님"]
        A1["A"] --> C1["C"]
        B1["B"] --> C1
    end
    subgraph 되돌이["되돌아오는 길 · 트리 아님"]
        A2["A"] --> B2["B"]
        B2 --> C2["C"]
        C2 --> A2
    end

둘 중 하나라도 있으면 트리가 아니라 그래프입니다.

제한을 건 대가로 보장을 하나 얻습니다. 뿌리에서 어떤 노드까지 가는 길이 언제나 딱 하나입니다. 길이 하나뿐이라 훑는 쪽은 이미 다녀온 노드인지 표시해 두지 않아도 됩니다. 같은 노드를 두 번 세는 일도 생기지 않습니다.

트리의 높이와 찾는 비용

뿌리에서 가장 먼 잎까지 내려가며 거치는 노드 수가 트리의 높이입니다. 트리에서 무언가를 찾는 비용은 대개 이 높이가 정합니다. 한 층 내려갈 때마다 볼 필요가 없어지는 갈래가 생기기 때문입니다.

자식을 둘까지만 둡니다. 왼쪽에는 작은 값, 오른쪽에는 큰 값을 담기로 정합니다. 그러면 이 효과가 또렷해집니다.

찾는 값이 지금 노드보다 작으면 오른쪽 서브트리는 볼 필요가 없습니다. 한 번 비교할 때마다 후보가 절반으로 줄어듭니다. 이 규칙을 지키는 트리가 이진 탐색 트리입니다.

flowchart TD
    subgraph 경로["3 을 찾아 내려간 길"]
        P1["4"] --> P2["2"]
        P2 --> P3["3"]
    end
    subgraph 컷1["1차 비교에서 잘림 · 노드 3개"]
        X1["6"] --> X2["5"]
        X1 --> X3["7"]
    end
    subgraph 컷2["2차 비교에서 잘림 · 노드 1개"]
        Y1["1"]
    end

3 은 4 보다 작으니 오른쪽 6 쪽 셋이 통째로 떨어집니다. 3 은 2 보다 크니 이번에는 왼쪽 1 이 떨어집니다. 두 번 비교하고 3 에 닿습니다.

노드가 n 개일 때 높이가 log n 언저리로 유지되면 찾기·넣기·지우기가 모두 O(log n) 입니다. 노드가 백만 개로 불어나도 뿌리에서 내려가는 층은 스무 남짓이라는 뜻입니다.

값 일곱 개를 그 규칙대로 담은 모습이 아래입니다. 층마다 고르게 퍼져 있어 어느 값을 찾아도 세 번 안에 닿습니다.

flowchart TD
    subgraph 고르게["고르게 퍼진 트리 · 높이 3"]
        A1["4"] --> B1["2"]
        A1 --> C1["6"]
        B1 --> D1["1"]
        B1 --> E1["3"]
        C1 --> F1["5"]
        C1 --> G1["7"]
    end

한쪽으로 치우친 트리

같은 규칙(왼쪽에 작은 값, 오른쪽에 큰 값)으로 1 부터 7 까지를 넣되 넣는 순서만 바꿔 봅니다. 제한 두 개는 모양까지 정해 주지 않습니다.

작은 값부터 차례로 넣으면 모든 노드가 오른쪽 자식만 갖습니다. 트리가 연결 리스트와 같은 한 줄이 됩니다.

flowchart TD
    subgraph 치우침["차례로 넣어 치우친 트리 · 높이 7"]
        A2["1"] --> B2["2"] --> C2["3"] --> D2["4"] --> E2["5"] --> F2["6"] --> G2["7"]
    end

고르게 퍼진 쪽과 치우친 쪽은 담긴 값이 같습니다. 높이만 3 과 7 로 갈립니다. 치우친 쪽에서 7 을 찾으려면 노드를 전부 거쳐야 하므로 찾는 비용이 O(n) 으로 올라갑니다. 트리를 쓰는 값어치가 사라지는 것입니다.

그래서 넣고 지울 때마다 모양을 손봐 높이를 낮게 붙잡아 두는 종류가 따로 있습니다. 이 손질이 균형입니다. 디스크에 담는 B-tree 는 한 노드가 자식을 수백 개까지 두는 쪽으로 높이를 더 낮춥니다.

높이를 재는 코드

떼어 낸 조각이 다시 트리라는 성질은 코드에서 바로 드러납니다. 높이를 재는 함수가 자기 자신을 다시 부릅니다.

class Node:
    def __init__(self, v):
        self.v, self.kids = v, []

def height(n):
    if not n.kids:
        return 1                 # 잎이면 1
    return 1 + max(height(k) for k in n.kids)

root = Node("A")
root.kids = [Node("B"), Node("C")]
root.kids[0].kids = [Node("D")]

height(root)                     # 3
height(root.kids[0])             # 2

height 는 자식들의 높이를 구한 뒤 가장 큰 값에 자기 층 하나를 더합니다. 자식이 없으면 거기서 멈춥니다. 이렇게 함수가 자기를 다시 부르는 방식이 재귀입니다.

flowchart TD
    HA["A · 3"] --> HB["B · 2"]
    HA --> HC["C · 1"]
    HB --> HD["D · 1"]

위 코드가 세운 트리입니다. 노드 옆 숫자가 그 노드에서 잰 높이입니다. 잎 D 가 1 을 돌려줍니다. 한 층 올라갈 때마다 1 씩 붙어 뿌리 A 에서 3 이 됩니다.

트리를 다루는 코드가 대부분 이 꼴인 것은, 서브트리가 원래 트리와 똑같이 생겨서 같은 함수를 그대로 다시 쓸 수 있기 때문입니다.

트리를 남김없이 훑는 방향은 둘로 갈립니다. 한 갈래를 끝까지 내려갔다가 되돌아 나오는 방식이 깊이 우선 탐색입니다. 같은 층을 먼저 다 훑고 아래 층으로 내려가는 방식이 너비 우선 탐색입니다. 위 height 는 깊이 우선으로 내려갑니다.

flowchart TD
    subgraph 깊이["깊이 우선 · A B D E C F"]
        S1["1 · A"] --> S2["2 · B"]
        S2 --> S3["3 · D"]
        S2 --> S4["4 · E"]
        S1 --> S5["5 · C"]
        S5 --> S6["6 · F"]
    end
    subgraph 너비["너비 우선 · A B C D E F"]
        T1["1 · A"] --> T2["2 · B"]
        T1 --> T3["3 · C"]
        T2 --> T4["4 · D"]
        T2 --> T5["5 · E"]
        T3 --> T6["6 · F"]
    end

앞의 A~F 트리에 방문 순서를 매긴 것입니다. 노드 앞 숫자가 몇 번째로 들르는지입니다.

트리 모양으로 담기는 데이터

파일 시스템의 폴더와 파일이 트리입니다. 웹 페이지의 문서 구조를 다루는 DOM(Document Object Model, 문서 객체 모델)도 트리입니다. 소스 코드를 읽어 만든 추상 구문 트리도 트리입니다. 데이터베이스의 인덱스도 대개 트리로 담깁니다.

Git 은 한 폴더에 무엇이 들었는지 담는 객체에 아예 트리라는 이름을 붙였습니다. 폴더가 폴더를 담고 그 폴더가 파일을 담는 모양이 그대로 트리이기 때문입니다.

공통점은 하나입니다. 담을 데이터에 「무엇이 무엇에 속한다」가 있어야 합니다. 그 속함이 뒤엉키지 않고 한 방향으로만 갈라질 때 트리가 맞습니다.

한 항목이 여러 곳에 동시에 속해야 한다면 부모가 하나라는 제한이 깨집니다. 그때는 그래프로 갑니다.

관련 항목

트리가 속하는 상위 분류

자료구조 · 그래프 · DAG · 계층 구조 · 비선형 자료구조

트리를 이루는 구성 요소

노드 · 간선 · 루트 노드 · 리프 노드 · 부모 노드 · 자식 노드 · 서브트리 · 포인터

트리의 하위 종류

이진 트리 · 이진 탐색 트리 · 균형 이진 트리 · AVL 트리 · 레드-블랙 트리 · B-tree · B+tree · 트라이 · 힙 · 머클 트리 · 신장 트리 · LSM 트리 · 세그먼트 트리

트리를 훑는 순회 방법

깊이 우선 탐색 · 너비 우선 탐색 · 전위 순회 · 중위 순회 · 후위 순회 · 재귀 · 백트래킹

트리의 성능을 재는 지표

시간 복잡도 · 트리 높이 · 트리 균형 · 분기 계수 · 캐시 지역성

트리로 데이터를 담는 시스템과 도구

파일 시스템 · 디렉터리 · DOM · 추상 구문 트리 · Git · 트리 객체 · 인덱스 · 네임스페이스 · XML · JSON

트리와 겨루는 다른 담는 모양

배열 · 연결 리스트 · 해시테이블 · 스택 · 큐 · 집합