트리(Tree)

지금까지 선형 자료구조에 대해 포스팅을 했었습니다.

만약 데이터가 선형 구조가 아닌 계층적인 구조(hierarchical structure)를 가지고 있다면 어떻게 해야 할까요?

예를 들어 조상과 자손, 전체와 부분, 상사와 부하 직원, 컴퓨터의 디렉터리 구조 등의 

계층적인 관계를 표현하고 싶은 경우에는 선형 구조는 적합하지 않습니다.

트리(Tree)는 이러한 계층적인 자료를 표현하는 데 이용되는 자료구조 입니다.

컴퓨터 용어 사전에 기재 된 트리의 정의는

나무가 하나의 뿌리(root)에서 줄기(trunk)가 나와 가지(branch)로 나누어지는 것처럼, 어떤 하나의 집합으로부터

하위 레벨(lower level)로 가지가 나오는 집합 관계를 갖는 계층 구조를 말한다.

부분적으로도 결코 루트를 형성하는 경우는 없다. 따라서 처음에 가지가 나오기 시작되고 있는 집합으로부터

차례대로 가지(branch)를 더듬어가면 목적의 집합을 찾을 수 있다.

트리는 뿌리(root), 가지(branch), 잎(leaf) 세가지 요소로 이루어져 있다.

뿌리, 가지, 잎 모두 실제로는 똑같은 노드이다. 이들은 트리 내 위치에 따라 명칭만 다를 뿐이다.

뿌리인 루트는 트리의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이의 모든 노드를 일컫는다.

그리고 가지의 끝에 매달려 있는 노드를 잎이라고 한다. 잎 노드는 끝에 있다고 하여 단말노드라고도 한다.

위 그림에서 B는 C와 D의 부모(Parent)이고, C와 D는 B의 자식(Children)이다.

그리고 한 부모 밑에 있는 C와 D는 형제(Sibling)이다.

한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 노드들의 순서를 경로(path)라 하며,

출발 노드에서 목적지 노드까지 거쳐야하는 노드의 개수를 길이(length)라 한다.

또 노드의 깊이(depth)는 루트 노드에서 해당 노드 경로까지의 경로의 길이를 뜻한다.

즉 G노드는 루트 노드인 A로 부터의 경로의 길이가 1이므로 깊이가 1이고, K노드는 A노드로부터 경로의 길이가 3이므로 깊이 역시 3이다.

마지막으로 차수(degree)는 그 노드의 자식 노드 개수를 말한다.

트리의 차수라함은 트리내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수를 말한다.

A노드는 자식 노드의 개수가 3이므로 차수가 3이고, B노드는 자식 노드가 2개이므로 차수가 2이다.

다음으로 트리 중에서 가장 많이 쓰이는 이진 트리에 대해 알아보자.

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다.

이진 트리에서도 여러 가지 이진 트리의 형태가 있다.

이 형태의 이진 트리는 포화 이진 트리라고 부른다.

말 그대로 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리를 의미한다.

높이가 k인 포화 이진 트리는 정확하게 개의 노드를 가진다.

이 형태의 이진 트리는 완전 이진 트리라고 부른다.

잎(leaf)의 레벨을 제외한 모든 부분은 포화상태이며, 잎(leaf) 부분은 왼쪽에서 오른쪽으로 순서대로 채워져 있어야 한다.

마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있어서는 안 된다.

따라서 포화 이진 트리는 항상 완전 이진 트리이지만 그 역은 항상 성립하지 않는다.

위와 같은 트리 형태가 아닌 다른 이진 트리들은 그냥 이진 트리이다.

다음은 트리의 모든 노드를 살펴보는 것인 트리 순회에 대하여 알아보자.

이진 트리를 순회하는 표준적인 방법에는 전위(preorder), 중위(inorder), 후위(postorder)의 3가지 방법이 있다.

이는 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분 된다.

왼쪽의 서브 트리를 L로 보고 루트를 V 오른쪽의 서브 트리를 R로 생각한다면

전위 순회(preorder traversal) : VLR (루트 - 왼쪽 - 오른쪽)

중위 순회(inorder traversal) : LVR (왼쪽 - 루트 - 오른쪽)

후위 순회(postorder traversal) : LRV (왼쪽 - 오른쪽 - 루트)

자세히 살펴보면 루트를 기준으로 전위, 중위, 후위라는 것을 알 수 있다.

이상으로 트리의 기본적인 개념과 구조에 대해 알아보았습니다.

용어들과 개념들을 잘 이해 하시면 도움이 될 것 입니다.