본문으로 건너뛰기

트리 (Trees)

Discrete Mathematics and its Applications · Kenneth H. Rosen · Ch. 10

Intuition

트리는 사이클(단순 회로)이 존재하지 않는 가장 효율적인 연결 구조로, 모든 정점 쌍 사이에 유일한 경로가 존재한다는 본질적 특성을 갖는다.

One-liner​

트리는 단순 회로가 없는 연결된 무향 그래프로, 데이터 계층 구조 모델링, 효율적인 탐색, 최적화 문제 해결의 핵심 도구이다.

Prerequisites​

이 챕터를 읽기 전에 알아야 할 개념·선행 챕터·수학적 배경.

Goals​

이 챕터를 읽고 나서 할 수 있어야 하는 것. 학습 목표.

  • 트리의 정의를 이해하고 주어진 그래프가 트리인지 판별한다.
  • 정점 수와 간선 수 사이의 관계 등 트리의 수학적 성질을 활용한다.
  • 이진 탐색 트리, 허프만 코딩, 결정 트리의 원리를 이해하고 적용한다.
  • 전위, 중위, 후위 순회 알고리즘을 수행하고 수식 트리를 구성한다.
  • DFS와 BFS를 사용하여 생성 트리를 찾고, Prim 및 Kruskal 알고리즘으로 MST를 구한다.

Core Concepts​

10.1 트리의 서론 (Introduction to Trees)​

Definition

Tree (트리): 단순 회로(Simple circuit)가 없는 연결된 무향 그래프이다. (p.683)

트리는 단순 회로를 가질 수 없으므로 다중 간선이나 루프를 포함할 수 없는 단순 그래프이다. 연결되지 않았으나 단순 회로가 없는 그래프는 Forest (포레스트)라고 하며, 각 연결 성분이 트리가 된다. (p.684)

  • Rooted Tree (루트 트리): 한 정점을 루트로 지정하고, 모든 간선이 루트에서 멀어지는 방향으로 유향 간선이 된 트리이다. (p.685)
  • Terminologies (용어): 부모(Parent), 자식(Child), 형제(Sibling), 조상(Ancestor), 자손(Descendant), 리프(Leaf, 자식이 없는 정점), 내부 정점(Internal vertex, 자식이 있는 정점). (p.686)
  • m-ary Tree (mm-진 트리): 모든 내부 정점이 최대 mm개의 자식을 갖는 루트 트리이다. 모든 내부 정점이 정확히 mm개의 자식을 가지면 Full m-ary tree라고 한다. (p.686)

10.2 트리의 응용 (Applications of Trees)​

  • Binary Search Tree (이진 탐색 트리): 각 정점에 키(Key)가 할당되어, 왼쪽 서브트리의 키는 부모보다 작고 오른쪽 서브트리의 키는 부모보다 큰 성질을 만족하는 이진 트리이다. (p.696)
  • Decision Tree (결정 트리): 각 내부 정점이 결정을 나타내고 리프가 가능한 해답을 나타내는 루트 트리이다. 정렬 알고리즘의 하한(Lower bound) 분석 등에 사용된다. (p.698)
  • Prefix Codes (접두사 코드): 어떤 문자의 코드도 다른 문자 코드의 시작 부분(접두사)이 되지 않는 부호화 방식이다. 이진 트리의 리프에 문자를 배치하여 구현한다. (p.701)
  • Huffman Coding (허프만 코딩): 문자의 출현 빈도에 따라 가변 길이 접두사 코드를 생성하는 탐욕 알고리즘(Greedy algorithm)으로, 데이터 압축에 최적의 성능을 낸다. (p.701)
  • Game Tree (게임 트리): 게임의 상태를 정점으로, 가능한 수를 간선으로 나타낸 트리이다. Minmax strategy (민맥스 전략)를 통해 최적의 수를 결정한다. (p.704)

10.3 트리 순회 (Tree Traversal)​

  • Universal Address System (유니버설 주소 체계): 루트 트리의 정점을 0,1,1.1,1.2,2…0, 1, 1.1, 1.2, 2 \dots와 같이 사전식 순서로 정렬하는 체계이다. (p.711)
  • Traversal Algorithms (순회 알고리즘):
    • Preorder (전위): 루트 →\to 왼쪽 서브트리 →\to 오른쪽 서브트리 순으로 방문한다.
    • Inorder (중위): 왼쪽 서브트리 →\to 루트 →\to 오른쪽 서브트리 순으로 방문한다.
    • Postorder (후위): 왼쪽 서브트리 →\to 오른쪽 서브트리 →\to 루트 순으로 방문한다. (p.712-716)
  • Notations (수식 표기법): 중위 표기법(Infix), 전위/폴란드 표기법(Prefix/Polish), 후위/역폴란드 표기법(Postfix/Reverse Polish). (p.719-720)

10.4 생성 트리 (Spanning Trees)​

Definition

Spanning Tree (생성 트리): 그래프 GG의 부분 그래프이면서 GG의 모든 정점을 포함하는 트리이다. (p.724)

  • Depth-First Search (DFS, 깊이 우선 탐색): 한 경로를 따라 가능한 깊게 탐색하다가 막히면 백트래킹(Backtracking)하는 방식이다. (p.727)
  • Breadth-First Search (BFS, 너비 우선 탐색): 인접한 정점들을 먼저 모두 방문하고 다음 레벨로 넘어가는 방식이다. (p.729)

10.5 최소 생성 트리 (Minimum Spanning Trees)​

가중치 그래프에서 간선 가중치의 합이 최소인 생성 트리를 의미한다. (p.737)

  • Prim's Algorithm (프림 알고리즘): 임의의 정점에서 시작하여, 현재 트리에 인접한 간선 중 가중치가 가장 작은 간선을 선택하며 트리를 확장한다. (p.738)
  • Kruskal's Algorithm (크루스칼 알고리즘): 그래프의 모든 간선을 가중치 순으로 정렬한 후, 회로를 형성하지 않는 범위 내에서 가장 작은 간선부터 차례로 선택한다. (p.739)

Key Theorems & Formulas​

Theorem 1 (유일 경로 정리)

조건: 무향 그래프 GG.

결론: GG가 트리인 것과 GG의 임의의 두 정점 사이에 유일한 단순 경로가 존재하는 것은 동치이다. (p.684)

Theorem 2 (정점-간선 관계)

조건: nn개의 정점을 가진 트리 TT.

결론: TT는 n−1n-1개의 간선을 가진다. (p.690)

Theorem 3 (Full m-ary 트리의 정점 수)

조건: ii개의 내부 정점을 가진 Full mm-ary 트리.

결론: 전체 정점 수 n=mi+1n = mi + 1이다. (p.690)

Corollary 1 (높이와 리프의 관계)

조건: 높이가 hh이고 리프가 ll개인 mm-ary 트리.

결론: h≥⌈log⁡ml⌉h \ge \lceil \log_m l \rceil 이며, 트리가 Full이고 Balanced이면 h=⌈log⁡ml⌉h = \lceil \log_m l \rceil이다. (p.693)

Intuitions​

  • 트리의 본질: 연결되어 있으면서 최소한의 간선(n−1n-1개)만을 사용하여 모든 정점을 잇는 구조이다. 간선을 하나라도 더하면 회로가 생기고, 하나라도 빼면 연결이 끊긴다.
  • 순회 알고리즘: 전위 순서는 루트를 먼저 보는 '탐색' 중심, 후위 순서는 하위 노드의 결과를 합쳐 올라오는 '계산' 중심의 사고방식을 반영한다.
  • Greedy MST: Prim은 정점 중심의 '근시안적 확장'이지만 최종적으로 최적해를 보장하며, Kruskal은 간선 중심의 '전역적 선택'을 통해 최적해에 도달한다.

Worked Examples​

Example 1: Full m-ary 트리 계산​

문제: 100명이 받은 체인레터에서 4명씩에게 전달하라고 되어 있다. 100명이 편지를 읽기만 하고 보내지 않았을 때, 전체 편지를 본 사람 수와 편지를 보낸 사람 수는? (p.691)

핵심 단계:

  1. 편지를 보낸 사람(내부 정점 ii), 보내지 않은 사람(리프 l=100l = 100), m=4m = 4.
  2. 정리 4(iii) 사용: i=(l−1)/(m−1)=(100−1)/(4−1)=33i = (l-1)/(m-1) = (100-1)/(4-1) = 33.
  3. 전체 정점 수 n=l+i=100+33=133n = l + i = 100 + 33 = 133.

요점: 루트 트리의 정점 수 공식을 실생활 문제에 대입하여 풀이할 수 있다.

Example 2: 허프만 코딩 구성​

문제: A: 0.08, B: 0.10, C: 0.12, D: 0.15, E: 0.20, F: 0.35 빈도를 가진 기호들의 허프만 코드를 구하라. (p.702)

핵심 단계:

  1. 가장 낮은 빈도 A, B를 묶어 0.18의 트리를 만든다.
  2. 다음 낮은 빈도 C, D를 묶어 0.27의 트리를 만든다.
  3. 0.18 트리와 E(0.20)를 묶어 0.38을 만든다.
  4. 0.27 트리와 F(0.35)를 묶어 0.62를 만든다.
  5. 0.38과 0.62를 묶어 루트(1.00)를 완성한다.

요점: 탐욕적 선택이 전체적인 코드 길이의 최적성(평균 비트 수 최소화)을 보장한다.

Common Pitfalls​

Pitfall

생성 트리의 유일성: 모든 연결 그래프가 생성 트리를 가지지만, 그 형태는 유일하지 않다. 간선을 제거하여 회로를 없애는 과정에서 어떤 간선을 택하느냐에 따라 다양한 생성 트리가 나올 수 있다. (p.725)

Pitfall

MST 알고리즘 차이: Prim은 항상 하나의 연결된 성분을 유지하며 확장하지만, Kruskal은 중간 단계에서 여러 개의 분리된 트리(포레스트)가 존재할 수 있다. (p.740)

Connections​

  • 선행 개념: Ch. 9 그래프의 연결성, 경로, 회로. Ch. 4 수학적 귀납법 (구조적 귀납법).
  • 후속 개념: 네트워크 유량(Network flow), 복잡한 데이터 구조 설계. Ch. 11 부울 대수 (결정 트리와 회로 최소화 연계).
  • 응용 분야: 파일 시스템 구조(p.689), 통신 네트워크 설계(p.737), IP 멀티캐스팅(p.726), 데이터 압축(허프만 코딩).

Critical Notes​

교재가 강조하는 것

  • 트리의 수학적 성질(간선 수와 정점 수의 관계)을 이용한 증명과 계산.
  • 루트 트리의 용어 및 mm-진 트리의 구조적 특성.
  • 알고리즘의 동작 과정을 단계별로 시각화하여 이해하는 것.

실제로 중요한 것

  • 알고리즘 복잡도: MST 알고리즘의 효율성(O(elog⁡v)O(e \log v) 등)이 대규모 네트워크 설계에서 결정적인 차이를 만든다. (p.741)
  • 수식 표기법 변환: 컴파일러 설계 등에서 트리를 이용한 구문 분석과 표기법 변환은 실무적으로 매우 중요하다.

교재가 생략하거나 얼버무리는 것

  • 허프만 코딩의 최적성 증명은 연습문제(Ex. 32)로 남겨져 있으며 본문에서는 직관적 설명 위주이다. (p.703)
  • MST 알고리즘에서 가중치가 동일한 간선이 있을 때의 deterministic한 선택 규칙은 세부적으로 다루지 않는다. (p.738)

Open Questions​

이해하지 못한 것

  • 게임 트리에서 알파-베타 가지치기(Alpha-beta pruning)가 실제 어느 정도의 연산량을 감소시키는지 수치적 감각을 보완할 필요가 있다.

더 알고 싶은 것

  • 교재에서 언급된 AVL 트리나 B-트리(Review Questions/Writing Projects)와 같이 실제 데이터베이스나 파일 시스템에서 쓰이는 고도화된 균형 트리의 구현 상세. (p.744-745)