트리의 정의
우리가 여태 알아본 연결 리스트, 스택, 큐와 같은 자료구조들은 선형으로 나열된 선형 자료구조입니다. 반면 오늘 알아볼 "트리"는 대표적인 계층적 구조를 가진 자료구조입니다. 즉, 비선형 자료구조입니다. 비선형 자료구조는 자료들의 앞뒤 관계가 1:n 또는 n:n인 자료들을 구현하기에 적절합니다. "트리"는 이렇게 계층적인 구조를 표현하는데 아주 적합한 자료구조입니다.
트리 자료구조를 제대로 이해하기 위해서는 알아야 하는 용어들이 많습니다. 차근차근 살펴보도록 하겠습니다.
- 노드(Node): 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J입니다.
- 루트(Root): 계층적인 구조에서 가장 높은 곳에 있는 노드(A)가 루트입니다.
- 서브트리(Sub-Tree): 기존의 트리에서 하위의 트리구조( {B, D, H, I, E, J}, {C, F, G} )입니다. 서브트리 아래에 또 서브트리가 생성될 수 있습니다.
- 간선(Edge): 루트와 서브트리를 연결한 선입니다.
- 부모 노드(Parent Node): A는 B와 C의 부모 노드입니다.
- 자식 노드(Children Node): D와 E는 B의 자식 노드입니다.
- 형제 노드(Sibling Node): F와 G는 형제 관계에 있는 노드입니다.
- 단말 노드(Leaf Node, Terminal Node): 자식이 없는 노드를 단말 노드라고 합니다.
- 비단말 노드(Nonterminal Node): 단말 노드와 반대로 자식이 있는 노드가 비단말 노드입니다.'
- 차수(Degree): 어떤 노드가 가지고 있는 자식 노드의 개수입니다. 가장 많은 자식 수로 차수를 정합니다. 위의 트리의 차수는 2입니다.
- 레벨(Level): 트리의 각층에 번호를 매기는 것입니다. 루트의 레벨은 1이며, 한 칸씩 아래로 내려갈 수록 1씩 증가합니다.
- 높이(Height): 트리가 가지고 있는 최대 레벨을 말합니다.
이진 트리의 정의
트리 중 가장 많이 사용되는 "이진 트리(Binary Tree)"는 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 의미합니다. 즉, 모든 노드의 차수는 2 이하가 되며 서브트리는 공집합일 수 있습니다. 이진 트리에는 서브 트리간의 순서가 존재하기에 왼쪽 트리와 오른쪽 트리는 서로 구별됩니다.
이진 트리의 특별한 성질들이 있는데, 이를 알아보도록 하겠습니다. (증명은 생략합니다.)
- $n$개의 노드를 가진 이진트리는 정확하게 $n - 1$개의 간선을 가진다.
- 높이가 $h$인 이진트리는 최소 $h$개의 노드를 가지며 최대 $2^h - 1$개의 노드를 가진다.
- 하나의 노드는 최대 2개의 자식을 가질 수 있기에 레벨 $i$에서의 노드 최대 개수는 $2^i - 1$이 된다.
- 전체의 노드 개수는 $\displaystyle\sum_{i=1}^{h}{2^h -1}$이 된다.
- $n$개의 노드를 가지는 이진트리의 높이는 최대 $n$이거나 최소 $[\log_2(n + 1)]$이 된다.
이진 트리의 종류로는 "포화 이진 트리", "완전 이진 트리", "기타 이진 트리"가 있습니다.
- 포화 이진 트리(Full Binary Tree): 트리가 각 레벨에 꽉 차 있는 이진트리를 말합니다. 포화 이진 트리에서는 각 노드에 번호를 붙일 수 있는데, 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙이면 됩니다. 예를 들면 (a)그림의 포화 이진 트리에 C의 번호는 항상 3인 것입니다.
- 완전 이진 트리(Complete Binary Tree): 트리의 높이가 $k$일 때 레벨 1부터 $k-1$까지는 모두가 완전 채워져있으나 마지막 레벨에서는 노드가 꽉차있지 않는 노드입니다. 이때 주의할 것은 마지막 레벨에서 노드가 비어있을 때는 항상 끝에만 비어있어야 한다는 것입니다. 즉, 중간에 노드가 비어서는 안된다는 것입니다. 그렇기에 포화 이진 트리와 마찬가지로 1:1로 번호 부여가 가능합니다.
- 기타 이진 트리: 포화 이진 트리도, 완전 이진 트리도 아닌 트리를 말합니다.
이진 트리 구현
이진 트리는 "배열을 이용하여" 구현하는 방법이 있고, "포인터(연결 리스트 형식)를 이용하여" 구현하는 방법이 있습니다.
배열 표현법
저장하고자 하는 이진 트리를 완전 이진트리라고 가정하고 이진트리의 깊이가 $k$이면 최대 $2^k - 1$개의 공간을 연속적으로 할당한 다음, 완전 이진 트리의 번호대로 노드들을 저장합니다. 이때 배열의 인덱스 0을 사용하지 않습니다. 그래야 이진 트리 계산을 간단하게 진행할 수 있습니다.
링크 표현법
트리에서의 노드를 구조체로 표현하고, 각 노드를 포인터를 통하여 연결하는 방법입니다. 연결 리스트와 상당히 흡사한 모양이라는 것을 알 수 있습니다.
C 코드 구현
C언어로 구현한 이진 트리는 다음과 같습니다. (링크 표현법으로 구현한 이진 트리)
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// n1
// / |
// n2 n3
int main() {
TreeNode *n1, *n2, *n3;
n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));
n1->data = 10; // 첫 번째 노드를 설정한다.
n1->left = n2;
n1->right = n3;
n2->data = 20; // 두 번째 노드를 설정한다.
n2->left = NULL;
n2->right = NULL;
n3->data = 30; // 세 번째 노드를 설정한다.
n3->left = NULL;
n3->right = NULL;
free(n1); free(n2); free(n3);
return 0;
}