05. 자료구조론 - 트리 (Tree)

트리 (Tree)

트리는 cycle없이 간선(edge)들로 연결된 노드들의 집합입니다.

트리에 cycle이 존재한다는 것은 특정 노드에서 출발하여 한번 지난 간선을 다시 방문하지 않고 처음 출발한 노드로 돌아올 수 있는 경로가 존재한다는 것입니다.

만약 간선으로 연결된 노드들의 집합에서 cycle이 존재한다면 그것은 트리가 아닌 그래프(graph)이고, 따라서 트리는 그래프의 한 종류가 됩니다.

트리의 최상단 노드는 root 노드입니다.

특정 노드의 하위에 달린 모든 노드들은 해당 노드의 child가 되고, 해당 루트 노드는 child 노드들의 parent가 됩니다.

그리고 특정 노드의 child노드들은 서로의 silbling이 됩니다.

특정 노드의 degree는 해당 노드의 child의 수이며, 전체 트리의 degree는 노드들의 degree 중 최댓값이 됩니다.

위 그림에서는 트리의 degree는 a의 degree인 3이 됩니다.

그리고 leaf 노드는 트리의 끝에 달려있는 노드로, degree가 0인 노드들을 의미합니다. 

 

트리에서 지칭하는 몇가지 용어들의 의미를 알아보겠습니다.

1. 두 노드 사이의 경로(Path) : 노드들의 sequence로 나타낼 수 있으며, sequence에서 이전노드는 다음노드의 parent여야 합니다.
ex) c에서 i까지의 Path : c, g, i

2. 경로(Path)의 길이(length) : 경로 상에 있는 edge의 개수 (= 노드의 개수 - 1)
ex) c에서 i까지의 Path의 length : 2

3. 노드의 depth (level) : 루트노드로부터 해당 노드까지의 경로의 길이
ex) 루트(a)노드의 level : 0, i노드의 level : 3

4. 노드의 height : 해당 노드부터 leaf 노드까지의 최장경로의 길이
ex) a 노드의 height : 3 (a노드에서 leaf 노드인 d까지는 경로의 길이가 1이고, e까지는 2이지만, h, i, j까지는 3이고, height는 가장 긴 길이를 의미하기 때문에 3이 됩니다.)

5. 트리의 height : 루트노드의 height

트리를 코드로 구현하려면 어떻게 해야할까요?

링크드리스트를 이용하여 특정 노드에 연결된 child 노드들의 포인터들을 모두 저장해두는 방식을 생각해볼 수 있습니다. 

하지만 한 노드 당 고정된 개수의 포인터만을 저장하여 트리를 구현할 수 있는 방법이 있습니다.

트리의 모든 노드들은 최대 하나의 leftmost child 노드가 있고, 최대 하나의 가장 가까운 오른쪽 sibling 노드를 가지고 있습니다. 이러한 특징을 이용하여 각 노드마다 leftmost child와 closest right sibling 을 가리키는 두개의 포인터만을 저장해두면 트리를 나타낼 수 있게됩니다. 

게시글 처음에 나온 트리를 위의 방식으로 저장하려면 다음과 같이 노드마다 빨간색과 파란색의 포인터를 저장하면 됩니다. 

그러면 특정 노드의 child 노드를 탐색하고자한다면 leftmost child로 간 이후에 계속 right sibling 포인터를 따라가면 모든 child 노드에 접근할 수 있습니다. 

typedef struct _TreeNode {
    int element;
    struct _TreeNode* leftmost_child;
    struct _TreeNode* right_sibling;
} TreeNode;

트리 노드에 대한 구조체는 위처럼 구현할 수 있습니다. 

 

이진 트리 (Binary Tree)

이진트리는 child 노드가 최대 2개까지 가능한 트리입니다. 

이진트리에서는 위와 같이 오른쪽에 자식이 달린 트리와 왼쪽에 자식이 달린 트리는 다른 트리로 구별됩니다.

 

이진트리에는 몇가지 속성이 있습니다.

1. 이진트리에서 i번째 level에 있는 노드의 최대 개수는 $2^i$ 개입니다. ($i >= 0$)

간단하게 증명하자면, 귀납법을 통해 증명할 수 있습니다. 
1. level 0에서 노드의 최대 개수는 항상 1개(루트노드) 이므로 위 문장은 성립합니다. ($2^0 = 1$)
2. level i-1 에 있는 노드의 최대 개수가 $2^{i-1}$ 이라고 가정합니다.
3. 그렇다면 각 노드에는 최대 2개의 child노드가 존재할 수 있으므로 level i에 있는 노드의 최대 개수는 2 * (level i에 있는 노드의 최대 개수) = $2 * 2^{i-1} = 2^i$ 가 됩니다.

 

2. 그렇다면 depth 가 k인 binary tree에 존재할 수 있는 노드의 최대 개수는 위 공식에 등비수열의 합 공식을 적용하여 모두 더하면 $2^{k+1} - 1$ 이 됩니다. ($k >= 0$)

 

3. 이진트리에서 전체 노드의 개수를 $n$, leaf 노드의 개수를 $n_0$ 라고하고, 하나의 child를 갖는 노드(degree 1)의 개수를 $n_1$, degree 2를 갖는 노드의 개수를 $n_2$ 라고 할 때, 다음과 같은 식이 성립합니다. 

$$n_0 = n_2 + 1$$

이것도 간단하게 증명하자면, 
$n = n_0 + n_1 + n_2$ 가 성립하고
$B$를 트리의 edge의 개수라고 하면, 루트노드를 제외하고 모든 노드는 parent 노드로 향하는 edge를 딱 하나씩 가지고 있으므로
$n = B + 1$ 이 성립합니다.
또한 $B = n_1 + 2n_2$ 으로 나타낼 수 있으므로
따라서 $n_0 + n_1 + n_2 = n_1 + 2n_2 + 1$ 이 되고, 이를 정리하면
$n_0 = n_2 + 1$ 이라는 위의 식이 도출되게 됩니다.

---

이진트리에는 여러가지 종류가 있습니다.

• Full binary tree : 모든 노드가 0개 또는 2개의 자식노드를 갖는 binary tree
• Complete binary tree : 마지막 level을 제외한 모든 레벨에 노드들이 완전히 채워져있고, 마지막 레벨에서는 노드들이 왼쪽부터 채워져있는 binary tree

• Perfect binary tree : leaf 노드가 아닌 모든 내부 노드들은 2개의 child를 가지고 있고, 모든 leaf 노드들은 같은 레벨에 존재하는 binary tree

이진트리는 자식노드의 개수가 최대 2개로 정해져있기 때문에 배열을 이용하여 구현할 수도 있고,  linked list를 이용하여 구현할 수도 있습니다.

배열을 이용한 이진트리 구현

위와 같은 트리가 있을 때, 아래와 같이 배열에 트리의 노드들을 순차적으로 저장해놓습니다.

이렇게 저장된 배열에서 특정 노드의 인덱스가 주어졌을 때, 해당 노드의 왼쪽, 오른쪽 child노드와 parent노드는 다음과 같이 접근할 수 있습니다. 

index i번째 노드가 주어졌을 때, (총 노드의 개수는 n개라고 하자)
1. 왼쪽 자식 노드의 index : $2i$ ($2i <= n$)
2. 오른쪽 자식 노드의 index : $2i+1$ ($2i+1 <= n$)
3. Parent노드의 index : $\lfloor i/2 \rfloor$ ($i >= 1$)

 

위의 예시는 complete binary tree였기 때문에 배열에 빈 공간이 없이 모든 노드들이 들어갈 수 있었습니다.

하지만 만약 아래와 같은 트리를 위와 같이 배열에 저장하려고 한다면 배열의 1, 2, 4, 8, 16, 32...와 같은 위치에만 유효한 노드가 들어가게 되고, 나머지 공간은 낭비되게 됩니다. 11개의 노드만 저장하려고해도 배열에는 1000개가 넘는 공간이 필요하게 됩니다. 

이를 해결하기 위해 모든 트리 노드들을 linked list로 연결하는 방법을 사용할 수 있습니다. 

링크드리스트를 이용한 이진트리 구현

이진트리에서 모든 노드들은 최대 2개의 자식노드를 가질 수 있고, 각각의 자식노드들은 새로운 subtree의 루트노드로 볼 수 있습니다. 따라서 이진트리의 노드는 다음과 같은 구조체로 나타낼 수 있습니다. 

typedef struct _TreeNode {
    int data;
    struct _TreeNode* left;
    struct _TreeNode* right;
} TreeNode;

이러한 방식으로 바로 위의 트리를 나타내면, 다음과 같은 5개의 트리노드 객체가 만들어져 연결됩니다.

이렇게 링크드리스트로 트리를 구현하면, 실제 존재하는 노드에 대한 공간만 사용하게 되므로 위와 같은 경우에 배열을 이용한 구현보다 더 효율적으로 공간을 사용합니다.

하지만 더 위에 있던 예시의 complete binary tree와 같이 빽빽히 노드들이 차있는 트리의 경우에는, 배열로 구현할 경우 노드 자체의 데이터만 저장하면 되지만, 링크드리스트로 구현할 경우 노드 하나 당 데이터뿐 아니라 두개의 포인터를 추가적으로 저장해야하므로 더 불리할 수 있습니다. 

트리 순회 (Tree traversal)

트리의 노드들을 순회하는 방식에는 세가지가 있습니다. 

세가지 Tree traversal을 코드로 구현할 때 재귀적으로 구현할 수도 있고, 스택과 반복문을 이용하여 구현할 수도 있습니다. 

우선 재귀적으로 구현하는 방식은 다음과 같습니다.

void InOrder(Tree* t) {
    if (t) {
        InOrder(t->left);
        printf("%d", t->data);
        InOrder(t->right);
    }
}

void PreOrder(Tree* t) {
    if (t) {
        printf("%d", t->data);
        PreOrder(t->left);
        PreOrder(t->right);
    }
}

void PostOrder(Tree* t) {
    if (t) {
        PostOrder(t->left);
        PostOrder(t->right);
        printf("%d", t->data);
    }
}

스택과 반복문을 이용해 트리를 in-order 방식으로 순회하는 코드는 다음과 같습니다.

void InOrder(Tree* node) {
    int top = -1;
    Tree* stack[MAX_SIZE];
    while (true) {
        while (node) {
            stack[++top] = node;
            node = node->left;
        }
        if (top == -1) break;
        node = stack[top--];
        printf("%d", node->data);
        node = node->right;
    }
}

트리를 순회하는 또다른 방식으로 level-order traversal이 있습니다.

level order방식은 다음과 같이 각 level순으로 노드들을 순회하는 방식입니다. 

void LevelOrder(Tree* node) {
    int front = 0;
    int rear = -1;
    Tree* queue[MAX_SIZE];
    if (!node) return;
    queue[++rear] = node; // Enqueue
    while (true) {
        node = queue[front++]; //Dequeue
        if (node) {
            printf("%d", node->data);
            if (node->left) queue[++rear] = node->left; // Enqueue left child
            if (node->right) queue[++rear] = node->right; // Enqueue right child
        } else {
        	break;
        }
    }
}

루트노드부터 시작하여 큐에 계속하여 자식들을 담아놓고 큐에서 하나씩 빼내며 노드들에 접근하는 방식입니다. 

더 낮은 depth에 있는 노드들이 왼쪽부터 순차적으로 먼저 큐에 들어가기 때문에 큐의 특성에 따라 해당 노드들이 더 먼저 출력되게 되어 level order traversal이 가능해집니다.