컴퓨터공학 300 주제 시리즈의 010번째 글이다. 전체 지도는 여기.

한 줄 요약

트리는 사이클이 없는 연결 무향 그래프다. 정점이 n 개면 간선은 정확히 n−1 개이고, 두 정점 사이의 경로는 정확히 하나다. 이 성질들은 서로 동치이며, 귀납법으로 깔끔하게 증명된다.

왜 필요한가

파일 시스템, DOM, 구문 트리(AST), 조직도, 이진 탐색 트리, 힙, B-트리, 머클 트리, 결정 트리. 컴퓨터공학에서 트리는 가장 많이 쓰는 구조다.

트리의 수학적 성질은 그대로 알고리즘의 근거가 된다. “간선이 n−1 개” 는 신장 트리 알고리즘이 언제 멈추는지 알려 주고, “경로가 유일하다” 는 라우팅 루프가 없다는 보장이 되며, “높이 h 인 이진 트리의 잎은 많아야 2ʰ 개” 는 비교 정렬이 n log n 보다 빠를 수 없다는 하한 증명의 핵심이 된다.

핵심 개념

정의와 동치 조건

정점 n 개(n ≥ 1)인 무향 그래프 T 에 대해 다음은 모두 동치다.

  1. T 는 연결되어 있고 사이클이 없다. (트리의 정의)
  2. T 의 임의의 두 정점 사이에 경로가 정확히 하나 있다.
  3. T 는 연결되어 있고 간선이 n−1 개다.
  4. T 는 사이클이 없고 간선이 n−1 개다.
  5. T 는 연결되어 있지만, 어떤 간선을 하나 빼도 끊어진다(최소 연결).
  6. T 는 사이클이 없지만, 어떤 간선을 하나 더해도 사이클이 생긴다(최대 비순환).

사이클이 없는 그래프(연결 여부 무관)는 숲(forest) 이라 한다. 숲의 각 연결 요소는 트리다.

핵심 보조정리: 잎이 있다

보조정리. 정점이 2 개 이상인 트리에는 차수 1 인 정점(잎)이 적어도 두 개 있다.

증명. 트리에서 가장 긴 경로 v₀, v₁, …, vₖ 를 하나 잡자(k ≥ 1). v₀ 의 이웃이 v₁ 말고 또 있다고 해 보자. 그 이웃 w 가 경로 위에 있으면 v₀ … w 를 잇는 사이클이 생기므로 모순이다. 경로 밖에 있으면 w, v₀, …, vₖ 가 더 긴 경로가 되므로 모순이다. 따라서 v₀ 의 차수는 1 이다. vₖ 도 같다. ∎

“가장 긴 것을 잡고, 더 긴 것이 생기면 모순” 이라는 논법은 극단 원리(extremal principle)라 부르며 자주 쓰인다.

정리: 간선은 n−1 개

정리. 정점 n 개인 트리의 간선은 n−1 개다.

증명. n 에 대한 귀납법. 기저 n = 1: 정점 하나, 간선 0 개. 귀납 단계: 정점 k 개인 모든 트리가 간선 k−1 개라고 가정하고, 정점 k+1 개인 트리 T 를 보자. 보조정리로 T 에는 잎 v 가 있다. v 와 그 간선 하나를 지운 T’ 은 여전히 연결되어 있고(v 를 지나는 경로는 v 에서 끝나므로 다른 정점 사이 경로에 쓰이지 않는다) 사이클도 없다. 따라서 T’ 은 정점 k 개인 트리이고 가정에 따라 간선 k−1 개다. 지운 간선을 되돌리면 T 의 간선은 k 개다. ∎

따름정리. 연결 요소가 c 개인 숲의 간선은 n − c 개다.

정리: 경로가 유일하다

증명. 두 정점 u, v 사이에 서로 다른 두 경로 P, Q 가 있다고 가정하자(귀류법). 두 경로가 처음 갈라지는 정점을 x, 그 이후 처음 다시 만나는 정점을 y 라 하자. P 의 x→y 구간과 Q 의 y→x 구간을 이으면 사이클이 된다. 트리에는 사이클이 없으므로 모순이다. ∎

뿌리 있는 트리와 이진 트리

정점 하나를 뿌리(root) 로 정하면 부모·자식·조상·자손·깊이·높이가 정의된다. 뿌리가 있는 트리는 004번 글의 구조적 귀납법으로 다루기 좋다. “트리는 뿌리 하나와 그 자식들을 뿌리로 하는 부분 트리들이다” 라는 재귀적 정의가 성립하기 때문이다.

이진 트리에서 각 정점의 자식은 많아야 둘이다. 높이 h(뿌리의 깊이 0)인 이진 트리에 대해 다음이 성립한다.

성질 값
깊이 d 의 정점 수 최대 2ᵈ
잎 수 최대 2ʰ
전체 정점 수 최대 2ʰ⁺¹ − 1 (포화 이진 트리)
정점 n 개일 때 높이 최소 ⌈log₂(n+1)⌉ − 1
정 이진 트리(자식 0 또는 2)에서 잎 수 = 내부 정점 수 + 1

응용: 비교 정렬의 하한

비교만으로 정렬하는 알고리즘은 결정 트리로 볼 수 있다. 내부 정점은 비교 한 번, 잎은 결론(입력의 순열 하나)이다. 서로 다른 n! 개의 순열을 구분하려면 잎이 n! 개 이상 필요하다. 높이 h 인 이진 트리의 잎은 많아야 2ʰ 개이므로 2ʰ ≥ n!, 즉 h ≥ log₂(n!) 이고, 이는 Θ(n log n) 이다. 최악의 비교 횟수가 h 이므로 어떤 비교 정렬도 최악에 Ω(n log n) 번 비교한다.

신장 트리

연결 그래프 G 의 신장 트리는 G 의 모든 정점을 포함하는 트리 모양의 부분 그래프다. 연결 그래프에는 항상 신장 트리가 있다. 사이클이 있는 한 그 위의 간선 하나를 지워도 연결이 유지되므로, 사이클이 없어질 때까지 지우면 된다. 가중치 합이 가장 작은 것이 최소 신장 트리(MST)이며, 알고리즘 파트에서 크루스칼과 프림 알고리즘으로 다룬다.

직접 해 보기

그래프가 트리인지 판정하는 함수를 “간선 n−1 개 + 연결” 조건으로 짠다. 연결 여부는 유니온-파인드(서로소 집합)로 확인하는데, 간선을 하나 추가할 때 양 끝이 이미 같은 묶음이면 사이클이 생긴다는 원리를 쓴다. 마지막에는 정렬 하한 log₂(n!) 을 계산한다.

import math

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def is_tree(n, edges):
    if len(edges) != n - 1:
        return False, "간선 수가 n-1 이 아님"
    parent = list(range(n))
    for u, v in edges:
        ru, rv = find(parent, u), find(parent, v)
        if ru == rv:
            return False, f"간선 {(u, v)} 가 사이클을 만듦"
        parent[ru] = rv
    return True, "트리"

print(is_tree(5, [(0, 1), (0, 2), (2, 3), (2, 4)]))
print(is_tree(5, [(0, 1), (1, 2), (2, 0), (3, 4)]))   # 간선 4개지만 사이클 + 끊김
print(is_tree(4, [(0, 1), (1, 2)]))

# 비교 정렬 하한: ceil(log2(n!))
for n in [3, 10, 100, 1000]:
    lb = math.ceil(math.lgamma(n + 1) / math.log(2))
    print(n, lb, round(n * math.log2(n)))

실행 결과다.

(True, '트리')
(False, '간선 (2, 0) 가 사이클을 만듦')
(False, '간선 수가 n-1 이 아님')
3 3 5
10 22 33
100 525 664
1000 8530 9966

둘째 예는 간선 수가 n−1 = 4 로 맞지만 트리가 아니다. 간선 수 조건만으로는 부족하고 “연결” 또는 “비순환” 중 하나가 함께 있어야 한다는 동치 조건 3, 4 를 그대로 보여 준다. 원소 3 개를 비교로 정렬하려면 최악에 적어도 3 번 비교해야 한다.

현업에서는

  • 스패닝 트리 프로토콜. 이더넷 스위치를 여러 경로로 연결하면 프레임이 사이클을 돌며 폭주한다. 스패닝 트리 프로토콜은 링크 일부를 막아 스위치 연결을 트리로 만든다. “경로가 유일하다” 는 성질이 곧 루프가 없다는 보장이다.
  • Git 의 트리 객체. Git 은 디렉터리를 tree 객체로, 파일을 blob 객체로 저장하고 tree 가 하위 tree 와 blob 을 가리킨다(Pro Git, Git Objects). 커밋 이력은 병합 커밋 때문에 트리가 아니라 DAG 라는 점도 함께 기억해 둔다.
  • 쿠버네티스 오브젝트 계층. 디플로이먼트 → 레플리카셋 → 파드의 소유 관계는 대개 트리 모양이다. 상위 오브젝트를 지우면 가비지 컬렉터가 하위로 내려가며 정리한다(Kubernetes, Garbage Collection).
  • 인덱스 높이 추정. B-트리 계열 인덱스의 높이는 팬아웃을 밑으로 하는 로그에 비례한다. 위 표의 이진 트리 성질을 차수 k 로 일반화하면, 행이 수억 개여도 높이가 한 자릿수에 머무는 이유가 보인다.

확인 문제

  1. 정점 50 개, 연결 요소 3 개인 숲의 간선 수는?
  2. 정점 n 개인 트리에 간선을 하나 더하면 사이클은 몇 개 생기는가?
  3. 높이 10 인 이진 트리의 정점은 최대 몇 개인가?
  4. 정 이진 트리에서 잎이 64 개면 내부 정점은 몇 개인가?

풀이

  1. 50 − 3 = 47.
  2. 정확히 하나다. 새 간선 (u, v) 와 원래 트리의 유일한 u–v 경로가 사이클을 이룬다. 다른 사이클이 생기려면 u–v 경로가 둘 이상이어야 한다.
  3. 2¹¹ − 1 = 2047.
  4. 63 개.

더 읽을거리 (References)