트리 기초: 용어와 세 가지 표현법

1. 일렬로는 담기 어려운 것들

폴더 안에 폴더가 있고 그 안에 파일이 있는 파일 시스템, 부서 아래 팀이 있는 조직도, 태그 안에 태그가 들어가는 HTML 문서는 모두 포함 관계가 겹겹이 쌓인 구조입니다. 이런 관계를 한 줄짜리 리스트에 담으면 "누가 누구 밑에 있는지"를 따로 기록해야 합니다.

트리는 이 관계를 구조 자체로 표현합니다. 각 원소가 자기 아래에 딸린 원소들을 직접 가리키므로, 계층이 곧 자료구조의 모양이 됩니다.

2. 용어

트리의 각 원소를 노드(node)라 하고, 노드를 잇는 선을 링크(link) 또는 엣지(edge)라고 합니다.

레벨 0                (A)  <- 루트 노드
                     /   \
                    /     \
레벨 1           (B)       (C)
                /   \         \
레벨 2       (D)     (E)       (F)  <- 리프 노드

  A-B-E 경로, 경로 길이 2 (지나간 엣지 수)
  출발 노드 A, 도착 노드 E
  B와 C는 형제 노드

• 루트 노드: 맨 위의 시작 노드. 부모가 없는 단 하나의 노드
• 리프 노드: 자식이 없는 끝 노드
• 부모/자식 노드: 링크로 바로 이어진 위아래 노드
• 형제 노드: 부모가 같은 노드들
• 레벨: 루트에서 몇 단계 내려왔는지
• 높이: 트리에서 가장 깊은 레벨. 위 그림은 2
• 경로: 한 노드에서 다른 노드로 가는 노드들의 나열. 출발 노드에서 도착 노드까지
• 경로 길이: 그 경로가 지나는 엣지의 개수

루트에서 어떤 노드로 가는 경로는 하나뿐입니다. 길이 여러 갈래면 트리가 아니라 그래프이고, 그래프는 16편부터 다룹니다.

3. 표현법 1: 리스트

자식이 최대 둘인 이진 트리는 리스트 하나로 표현할 수 있습니다. 노드를 레벨 순서대로, 같은 레벨에서는 왼쪽부터 칸에 채워 넣습니다.

index    0     1     2     3     4     5     6
       +-----+-----+-----+-----+-----+-----+-----+
       |  A  |  B  |  C  |  D  |  E  |     |  F  |
       +-----+-----+-----+-----+-----+-----+-----+

   i번 노드의 왼쪽 자식 = 2i + 1
              오른쪽 자식 = 2i + 2
              부모        = (i - 1) // 2

링크를 하나도 저장하지 않는데 부모와 자식을 찾을 수 있습니다. 자리가 곧 관계이기 때문입니다. C의 왼쪽 자식은 비어 있어서 5번 칸이 빕니다.

4. 표현법 2: 재귀적인 중첩 리스트

트리는 정의부터 재귀적입니다. 노드 하나와 그 아래 부트리들로 이루어지고, 부트리도 다시 같은 모양입니다. 이 성질을 그대로 옮기면 [키, 왼쪽 부트리, 오른쪽 부트리] 형태가 됩니다.

T = ['A',
     ['B', ['D', [], []],
           ['E', [], []]],
     ['C', [],
           ['F', [], []]]]

T[0]        # 'A'      루트의 키
T[1]        # B 부트리
T[2][2][0]  # 'F'

빈 부트리는 빈 리스트입니다. 트리 모양이 코드 모양에 그대로 드러나서, 재귀 함수를 쓸 때 부트리를 통째로 넘기기 편합니다.

5. 표현법 3: 노드 클래스

가장 일반적인 방식은 노드를 객체로 만들고 자식을 참조로 연결하는 것입니다. 05편의 연결 리스트에서 링크가 둘로 갈라진 형태로 보면 됩니다. (보강)

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None      # 필요하면 부모도 함께

자식이 셋 이상일 수 있는 트리라면 self.children = []처럼 리스트로 두면 됩니다.

6. 표현법 비교

셋 다 자식 접근은 상수 시간이고, 차이는 메모리와 다루기 편한 정도에서 납니다.