[자료구조] Tree

앞서 다룬 자료 구조들과 다르게, 지금부터 다룰 tree는 비선형(non-linear) 자료구조이다. 즉, 하나의 element 뒤에 여러 개의 element가 올 수 있다. 보다 정확히 얘기하면 전자와 후자가 부모자식 관계로 얽힌 hierarchy가 있는 것이다.

 

앞서 다뤘던 array, linked list, queue, stack 등의 선형(linear) 자료구조가 어떤 element '앞, 뒤에' 어떤 element가 오는지에 초점이 맞춰저 있었다면, tree는 어떤 element가 어떤 element의 '부모인지 자식인지'에 초점이 맞춰져 있다고 이해하였다.

 

Tree의 모든 element들은 (unique) parent를 가지고, 0개 이상의 children을 갖는다. 이 때, hierarchy의 맨 위에 있는 element는 부모가 없을 수 밖에 없는데, 이 element를 root element 또는 root node라고 한다.

 

앞으로 tree를 설명할 때는 각각의 element를 node라고 표현할 것이다. 지금 내가 사용하고 있는 교재, 교안, 기타 등등 tree를 다루는 대부분의 설명서에서 node라는 표현을 사용하기 때문에 이에 맞추기로 한다.

 

기본 구조

다음 그림을 통해 tree의 개념을 알아보자.

위 그림과 같은 tree가 있을 때,

1. A,B,C,D,E,F,G는 모두 node이다.

2. 각각 node들을 이어 주는 선을 edge(간선) 이라 한다.

3. A는 부모가 없는, 모든 다른 node들의 ancestor인 root node이다. 반대로, 모든 다른 node들은 A의 descendant이다.

4. B-C, D-E, F-G 는 같은 parent를 공유하는 sibling 관계이다.

5. A, C, D와 같이 child node를 가지고 있는 node를 internal node 라고 한다.

6. B, F, G, E와 같이 child node가 없는 node를 leaf node 라고 한다. 

7. root node를 시작으로, edge를 타고 내려갈 때마다 level이 올라간다. 즉 A의 level은 0, B와 C의 level은 1, D와 E의 level은 2이다. 이 때, 같은 level에 있는 node 간 같은 특성을 공유할 필요는 없다. 가령 E에 자식 H, I가 추가로 더 있다면, 해당 노드들은 F,G와 level이 같지만 같은 특성을 공유할 필요는 없을 것이다.

8. root node로부터 가장 많은 edge를 타고 내려가야 하는 node의 level이 해당 tree의 height가 된다. 즉 예시로 든 tree의 height는 3이다. 즉, max(level)=height 인 셈

 

subtree

어떤 node를 root node처럼 취급했을 때, 해당 node와 그 descendants들로 구성된 tree를 subtree라고 한다. 가령, 위 tree에서 D,F,G는 D를 원점으로 하는 subtree라고 한다.

 

이 표현은 내가 임의로 원서의 내용을 해석한 것이다 보니, 보다 정확한 표현을 위해 교재의 내용을 빌리면 D와 그 descendant들인 F,G는 'subtree rooted at D' 라고 할 수 있다. 

 

ordered tree

각 node의 children간에 순서가 지정된 tree를 ordered tree라고 한다. 가령 내가 자료구조를 다루는 책을 tree 구조로 표현한다고 생각해 보자.

구체적인 방식은 책마다 다르겠지만 아마도 Tree라는 파트가 있을 것이고, 해당 파트를 정점으로 하는 subtree를 만들어 본다면, 아마 그 children은
ch.1 비선형 자료구조와 선형 자료구조

ch.2 트리의 개념

ch.3 이진 트리

ch.4 이진 트리의 응용...

 

이런 식으로 "순서가 있는" 구조일 것이다. 이렇게 children 간에 순서가 정해져 있는 tree를 ordered tree라고 한다.

다음 포스팅에서는 ordered tree의 대표주자격인 Binary Tree에 대해 다뤄 보겠다.