트리는 그래프의 한 종류로써, 유닉스 및 리눅스의 파일 시스템과 검색 엔진 등에서 널리 사용되고 있는 자료구조이다. 트리는 컴퓨터공학의 모든 자료구조 중에서도 가장 많은 변형이 있으며, 대부분의 경우에 배열(array)보다 유연하고 연결 리스트(linked list)보다 효율적이다.
[그림 1] 트리 구조의 활용
위의 [그림 1]과 같이 트리의 개념은 컴퓨터공학뿐만 아니라 생명과학, 게임 등 다양한 분야에서 이용되고 있다.
트리의 개념을 이해하기 위해서는 먼저 이산 수학(discrete mathematics)의 그래프(graph)를 이해할 필요가 있다. 그래프 $G$는 $G = (V, E)$와 같이 표현되며, $V$는 그래프 내의 어떠한 지점을 가리키는 vertex의 집합이고, $E$는 두 vertex를 연결하는 선의 집합이다. 아래의 [그림 2]는 그래프에 대한 몇 가지 예시를 나타낸다.
[그림 2] 그래프의 예시
그래프에서는 walk, path, cycle이라는 중요한 개념이 활용된다. 각각의 정의는 다음과 같다.
- walk: 그래프 내에 존재하는 vertex의 연속
- path: edge가 반복되지 않는 walk
- cycle: 시작 vertex와 마지막 vertex가 같은 path
아래의 [그림 3]에서 (a)는 A-B-D-A로 이루어진 cycle을 나타내고, (b)는 B-A-D-C로 이루어진 path를 나타낸다. 또한, (c)는 A-B-C-A-D로 vertex A가 중복으로 나타나는 walk 또는 path를 나타낸다
[그림 3] Digraph의 cycle, path, walk
이산 수학 또는 그래프 이론에서 트리는 방향성이 없는 undirected graph이며, 모든 두 vertex가 하나의 유일한 path로만 연결된 그래프를 의미한다. 두 vertex가 유일한 path로만 연결되어 있다는 것은 그래프에 cycle이 존재하지 않는다는 것과 동치이다.
많은 글이나 책에서는 root node(vertex)를 갖고, 나머지 노드들은 또다시 트리로 분리되는 것으로 트리를 정의하고 있지만, 이것은 rooted tree라는 트리의 한 종류이다. 아래의 [그림 4]에서 (a)는 트리이고, (b)와 (c)는 트리가 아니다.
[그림 4] 트리의 예시
[그림 4]에서 (b)는 A에서 C로 이동하는 path가 2개(A-B-C, A-C) 존재하므로 트리가 아니다. 또는 A-B-C-A로 이루어진 cycle이 존재하므로 트리가 아니다. (c)는 cycle이 존재하지는 않지만, A 또는 B에서 C로 이동하는 path가 존재하지 않는다. 트리는 모든 두 vertex 사이에 하나의 유일한 path가 존재해야하므로, (c) 또한 트리가 아니다.
자료구조에서는 트리를 그래프 이론에서와 약간 다르게 정의한다. 자료구조에서 트리의 정의는 다음과 같다.
(a) root node라는 특별한 노드가 존재한다.
(b) 나머지 노드들은 각각이 트리이면서, 교차하지 않는 집합으로 분할된다.
자료구조에서는 그래프 이론의 rooted tree를 트리라고 정의한다. 아래의 [그림 5]는 트리 구조와 트리가 아닌 구조의 예시를 나타낸다.
[그림 5] 트리 구조와 트리가 아닌 구조
트리에서 노드(node)는 [그림 5]에서 A, B, C, D와 같이 어떠한 데이터와 다른 노드의 포인터를 갖고 있는 것을 의미한다. 트리에서는 아래와 같은 개념이 이용된다.
degree: 어떠한 노드가 갖고 있는 subtree의 수, 노드 A의 degree는 2이고, C의 degree는 1이다.
leaf 또는 terminal node: degree가 0인 노드, (a)는 leaf node로 D, E, F를 갖는다.
level: 어떠한 노드와 root node 사이에 존재하는 edge의 수에 1을 더한 값, 노드 E의 level은 3이다(2 + 1).
depth: 트리에 포함된 노드들이 갖는 level중에서 가장 큰 level, (a)에서 가장 큰 level은 3이므로 (a)의 depth는 3이다.
child node: 어떠한 노드에서 파생되는 노드, D와 E는 B의 child node이며, B는 D와 E의 parent node이다.
자료구조에서 일반적으로 depth가 증가할수록 트리의 연산 성능이 급감하기 때문에 트리를 설계할 때는 depth를 최소화하는 것이 매우 중요하다.
Child node의 수가 결정되어 있지 않는 트리에서는 연결 리스트를 이용하여 트리 구조를 표현한다. [그림 6]은 [그림 5]의 (a)를 연결 리스트로 표현한 것이다.
[그림 6] 연결 리스트를 이용한 트리 구현
그러나 고정된 $n$개의 child node를 갖는 트리의 경우에는 연결 리스트가 아닌, Node라는 class를 별도로 정의하여 구현한다. 예를 들어, 모든 노드가 최대 2개의 child node를 갖는 트리(binary tree)는 연결 리스트를 이용하는 것이 아니라, [그림 7]과 같은 Node class를 별도로 정의하여 구현한다.
[그림 7] Binary tree를 구성하는 Node class의 구조
