트리(Trees)

용어 정의

트리의 표현

트리의 이진 트리 표현

용어 정의

트리는 자료 사이의 계층적 구조를 나타내는 자료구조이다.

레벨

0

1

2

3

노드(node); 에지(edge)

부모 노드(parent); 자식 노드(child)

형제 노드(sibling)

조부모 노드(grandparent); 손자 노드(grandchild)

조상 노드(ancestors); 후손 노드(descendants)

분지수(degree), 차수

리프(leaf), 단말 노드(terminal), 외부 노드(external node)

nonleaf, 비단말 노드(nonterminal), 내부 노드(internal node)

레벨(level)

높이(height), 깊이(depth)

용어 정의 (계속)

트리는 다음과 같이 재귀적으로 정의할 수 있다:

트리는 하나 이상의 노드로 구성된 유한 집합으로써,

(a) 특별히 지정된 노드인 루트(root)가 있고,

(b) 루트를 제외한 나머지 노드들은 각각이 트리이면서 서로 교차하지 않는 분리된 집합 [eqn: T_1], [eqn: T_2], [eqn: ldots], [eqn: T_k]로 분할된다. 이 때 각각의 [eqn: T_i]를 루트의 부트리(subtree)라고 한다.

주의. 여기서 말하는 트리는 루트가 있는 트리(rooted tree)이다. 루트를 정의하지 않는 트리를 자유 트리(free tree)라고 말한다. 이 때는 트리를 연결되어 있는 사이클이 없는 그래프를 말한다.

트리의 표현

앞에서 본 트리는 아래와 같이 괄호를 이용하여 리스트 표현을 할 수 있다. 이 때 각 부트리는 역시 리스트 표현을 한다.

A(B(D(I),E,F),C(G(J,K,L),H(M)))

연결 리스트를 이용하여 표현한다면, 각 노드는 data 필드와 트리의 분지수에 해당하는 link 필드를 가진다. 각 노드의 link는 왼쪽부터 차례로 그 노드의 자식 노드를 가리킨다.

data	link 1	link 2	...	link k

이와 같은 표현에 트리 T의 분지수가 k이고 노드 수가 n이라면 필요한 링크의 수는 nk이고 이 중 NULL이 아닌 링크의 수는 n-1이므로 NULL 링크의 수가 n(k-1)+1로 링크를 위한 메모리 낭비가 심하다.

트리의 이진 트리 표현

트리의 분지수에 관계없이 모든 트리를 이진 트리(binary tree)로 표현할 수 있다. 이진 트리란 분지수가 2 이하인 트리를 말한다. 이 때 각 노드의 link는 부모-자식의 관계를 표현하는 것이 아니라, 하나는 왼쪽 첫 번째 자식 노드를 가리키고 다른 하나는 오른쪽 첫 번째 형제 노드를 가리킨다. 앞의 트리 예제를 이와 같이 나타내면 다음과 같다.