Tree

대표적인 선형 자료구조가 Stack과 Queue라면, 대표적인 비선형 자료구조로는 Tree와 Graph가 있다고 이야기할 수 있다. 그래프 이론에서는 tree도 graph에 속하고(회로가 없는 연결 무향 그래프를 tree라고 하기 때문) 자료구조에서도 tree가 그래프의 일종이라고 보는 듯 하다.

'나무'라는 의미에 맞게, 뿌리와 가지, 잎 개념이 들어가 있는 계층적 구조를 띄고 있다. 주된 목적은 탐색이며, 따라서 검색 엔진, 데이터베이스, 라우터 알고리즘 등 계층적 데이터를 다루는 수많은 곳에서 응용되고 있다. 아래는 tree의 예다.

현실에서 볼 수 있는 나무와는 다르게 위에서 아래 방향으로 뻗어나오는 모양이다. 따라서 root(뿌리)도 맨 위에 있다. 트리는 기본적으로 Node와 Edge로 구성된다. A, B, C처럼 각각의 요소를 node라고 부르고, node들을 이어주는 간선을 edge라고 부른다. Node는 종류에 따라 아래처럼 나뉜다.

• Root node : tree의 시작점이 되는 노드. 위 그림에서는 A가 root node이며, tree에서 root node는 최대 하나다.
• Parent node : tree의 부분집합을 sub-tree라고 쳤을 때(위 그림에서는 D, H, I로 이뤄진 tree), sub-tree에서의 root node를 의미한다. Root node만 유일하게 parent node가 없다.
• Child node : Parent node에서 뻗어나온 노드를 의미한다. Parent node와 child node는 상대적인 개념이라, 위 그림에서 C는 A의 child node이면서 F와 G의 parent node이다.
• Leaf node : tree의 끝점이 되는 노드(Child node가 하나도 없는 노드). 단말(terminal) 노드라고도 부른다.
• Internal node : Leaf node가 아닌 노드를 의미한다.

Tree에는 해석학의 이론이 존재하기에, 해석에 관련된 몇가지 개념이 들어가 있다. 그들 중 가장 기본적인 게 차수, 높이, 레벨이다.

• 차수(degree) : 어떤 노드가 가지고 있는 child node의 수를 의미한다. 위 그림에서는 leaf node들을 제외하면 E만 차수가 1이다. leaf node는 child node가 없는 노드를 의미하므로 일반적으로 leaf node에 대해서는 차수를 이야기하지 않는다. Tree에서 발견되는 가장 높은 차수를 tree의 차수라고 말하기도 한다. binary tree, ternary tree 등 n-ary tree의 조건이 되는 개념이다.
• 높이(height) : Root node부터 시작하여, 가장 깊게 뻗어나가 있는 leaf node까지의 깊이를 말한다. root node는 높이를 0으로 둔다.
• 레벨(level) : 각 층의 번호를 의미한다. root node의 level은 0이다.

따라서 위 tree의 차수는 2, 높이는 3이며, root node는 A다. 노드 C는 level 1에 있으며 parent node로 A를, child node로 leaf node인 F와 G를 두고 있는 internal node라고 이야기할 수 있다.