트리(Tree)의 운행과 알고리즘 - 정보올림피아드 문제풀이

이전 포스팅 트리(Tree)의 개념에서 트리의 기본적인 개념과 실제로 많이 사용하는 이진트리에 대해서도 자세하게 살펴 보았습니다. 이번 포스팅에서는 트리의 운행 방법(traversal)과 관련된 알고리즘을 다루겠습니다.

위의 그림과 같은 이진 트리의 모든 노드를 방문하는 방법에는 3가지가 있는데 트리의 각 노드를 방문하는 방법을 트리의 운행(traversal) 또는 순회라 하고 크게 3가지 방법으로 나뉩니다. 각각의 방법은 다양한 형태로 응용하기 때문에 그 기법을을 꼭 알아두셔야 합니다.  트리(Tree)의 개념에서 이진트리의 각 노드는 Left 링크는 자식 노드를 가리키고 Right 링크는 형제 노드를 가리키도록하여 어떤 차수의 트리도 이진 트리로 표현할수 있다고 했는데 각 노드를 언제 방문하는가에 따라 트리 운행 방법을 구분합니다. 각 노드를 n, Left 링크를 L, Right 링크를 R이라할 때 nLR의 순서로 방문하는 것을 전위(preorder) 운행, LnR의 순서로 방문하는 것을 중위(inorder) 운행, LRn의 순서로 방문하는 것을 후위(postorder) 운행이라 합니다.

위의 트리를 전위 운행하면 nLR이므로 일단 [a]를 방문하고 Left가 있으므로 Left로 이동하여 노드 [d]를 방문합니다. Left가 있으므로 이동하여 [h], [i]를 차례로 방문하고 [d]로 거슬러 올라와서 Right링크로 이동하여 [e]를 방문한 다음 자식 노드가 없으므로 [a]로 거슬러 올라와 Right링크 쪽도 마찬가지 방식으로 각 노드를 방문하면 결과는 a-d-h-i-e-f-g-m-l 이 됩니다. 

동일한 트리를 중위 운행하면 LnR이므로 Left 링크를 계속 따라가서 [i]를 방문하고 노드 [h]를 방문한 다음 Right가 없으므로 노드 [d]를 방문하고 Right로 이동합니다. [e]의 left/right가 없으므로 노드 [e]를 방문하고 거슬러 올라가 노드[a]를 방문한 다음 Right쪽으로 이동하는 방식으로 운행합니다. 결과는 i-h-d-e-a-f-m-g-l입니다. 같은 트리를 후위 운행한 결과는 i-h-e-d-m-l-g-f-a 입니다.

■ 트리 운행 개념을 다룬 문제풀이

1. 다음과 같은 트리를 중위 순회(inorder traversal) 할 때 세 번째로 방문하게 되는 노드는?

① A ② B ③ C ④ D ⑤ E

※ LnR의 순서로 방문하는 중위 순회 설명을 참조합니다. Left링크가 없을 때까지 일단 Left를 계속적으로 따라가야 합니다. 그러면 D가 첫방문이 되고 중위 순회이므로 B를 방문하고 B의 Right를 찾아가는 방식입니다.

2. A부터 H가 적혀있는 8개의 노드로 이루어진 이진트리가 있다. 이 이진트리에서 전위순회로 방문한 노드의 순서가 ABDECFGH, 중위 순회로 방문한 노드의 순서가 DBEAGFHC 일 때 후위 순회로 방문한 노드의 순서는? 

① ACFGHBDE   ② ACFHGBED   ③ DBEGHFCA   

④ DEBGHFCA   ⑤ HGFCEDBA 

※ 이 문제는 순회 결과를 통해서 트리의 구조를 분석해 내고 그 결과로 문제를 풀어야 합니다. 전위 순회는 모드 부터 방문하므로 A가 루트이고, 중위 순회는 노드보다 Left가 먼저이므로 BDE가 A의 Left트리 임을 알수 있습니다. BDE만 보면 전위 순회에서 B를 먼저 방문했으므로 B가 노드이고 D가 Left, E가 right임을 알 수 있습니다. 마찬가지로 우측으로 이동하여 C부터 방문했으므로 C가 노드이고 C다음의 전위 순회가 F이지만 중위에서는 G이므로 G가 F의 Left, H가 G의 Right임을 알수 있습니다. 결과적인 트리 모양은 다음과 같습니다.

위의 트리를 후위 순회하면 LRn의 순서이므로 b노드의 Left인 d를 먼저방문하고 b노드의 Right e를 방문한 다음 노드 b를 방문하는 방식입니다.

3. 다음 트리를 전위 순회(preorder traversal)했을 때 방문하는 노드를 순서대로 나열한 것은?

① A B C D E F ② A B D E C F ③ D B E A F C ④ D E B F C A ⑤ D E F B C A

4. 다음 트리를 후위 순회(postorder traversal)했을 때 방문하는 노드를 순서대로 나열한 것은?

①1 2 3 4 5 6   ②1 2 4 5 3 6   ③4 2 5 1 6 3   ④4 5 2 6 3 1   ⑤4 5 6 2 3 1

위의 설명과 문제 풀이로 만나본 트리 운행법을 활용한 것이 이진 탐색 트리(BST, Binary Search Tree)로 중복된 노드값 없이 노드값 보다 작으면 좌측 크면 우측 트리로 배치하는 방식입니다. 트리의 높이가 일정 수준으로 유지되는 균형트리인 경우 평균 의 탐색 속도를 보입니다. 이진 탐색 트리를 중위 순회로 모든 노드를 방문하면 오름차순으로 정렬된 결과를 얻을 수 있습니다. 아래는 이진 탐색 트리의 데이터 추가 및 순회를 구현한 예제 코드입니다(출처:http://programminggeeks.com/)

struct node {
    int data;
    struct node *left;
    struct node *right;
};
 
struct node *root = NULL;
 
void insertNode(struct node *q, int data) {
    if(q == NULL) {
        // create the root node (root)
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->left = NULL;
        p->right = NULL;
        p->data = data;
        root = p;
        return;
    }
    else if(data < q->data && q->left != NULL) {
        q = q->left;
        insertNode(q,data);
    }
    else if(data > q->data && q->right != NULL) {
        q = q->right;
        insertNode(q,data);
    }
    else if(q->left == NULL && data < q->data) {
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->data = data;
        p->right = NULL;
        p->left = NULL;
        q->left = p;
        return;
    }
    else if(q->right == NULL  && data > q->data) {
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->data = data;
        p->right = NULL;
        p->left = NULL;
        q->right = p;
        return;
    }
}
 
void inOrder(struct node *q) {
    if(q != NULL) {
        inOrder(q->left);
        printf("%d\n",q->data);
        inOrder(q->right);
    }
}
 
void preOrder(struct node *q) {
    if(q != NULL) {
        printf("%d\n",q->data);
        preOrder(q->left);
        preOrder(q->right);
    }
}
 
void postOrder(struct node *q) {
    if(q != NULL) {
        postOrder(q->left);
        postOrder(q->right);
        printf("%d\n",q->data);
    }
}

트리 구조체는 노드 데이터와 좌우 부트리로의 링크를 가지고 있으며 새로운 노드가 추가될 때 마다 동적으로 메모리를 할당하고(malloc) 있음을 확인할 수 있습니다. 노드 삽입은 노드값 비교로 위치를 찾아 새로운 단노드를 추가하는 방식이고 트리를 순회하거나 삽입 위치 찾기는 재귀함수를 사용하고 있음을 확인할 수 있습니다. 단, 위의 알고리즘은 트리의 높이를 관리하는 트리의 균형 알고리즘은 감안하지 않은 것으로 입력 자료에 따라 비효율을 초래할 수 있습니다. 균형 이진 트리를 만들기 위한 알고리즘은 insertNode함수에서 노드를 추가한 다음 좌/우 부트리의 깊이를 계산하여 깊이차가 1보다 큰 경우 조정 작업을 수행합니다.

■ 트리 탐색, 관리를 다룬 문제풀이

5. 다음과 같은 이진 탐색 트리(binary search tree)에 30을 추가하려고 한다. 30이 들어갈 위치로 알맞은 것은?

① 33의 왼쪽 자식 ② 36의 왼쪽 자식 ③ 20의 오른쪽 자식 ④ 49의 오른쪽 자식 ⑤ 17의 오른쪽 자식

※ 삽입하려는 값과 노드 값을 비교하여 작으면 좌측, 크면 우측으로 이동하여 삽입 위치를 찾습니다.

       

6-7. 높이가 h이고 개의 노드를 가진 이진트리가 있다. 이 트리의 각 노드에 중위 우선 순서로 1번부터 n번까지의 번호를 붙였다. h=3 (n=24-1=15)일 때의 예는 다음과 같다.

a[1], a[2], …, a[n]에 정수 값이 하나씩 들어 있는 배열 a가 있을 때, 다음과 같은 규칙으로 배열 b를 만든다.

“i번 노드의 왼쪽 서브트리에 속한 노드 번호들이 j1, j2, …, jm일 때, b[i]에는 a[j1], a[j2], …, a[jm]의 합이 저장된다.” 

가령 위의 예에서, 4번 노드의 왼쪽 서브트리는 1, 2, 3번 노드로 구성되어 있으므로, b[4]의 값은 a[1]+a[2]+a[3]이다. 또한 12번 노드의 왼쪽 서브트리는 9, 10, 11번 노드로 구성되어 있으므로, b[12]의 값은 a[9]+a[10]+a[11]이다.

배열 b의 모든 값이 미리 계산되어 있을 때, 배열 b를 이용하여 1 이상 n 이하의 자연수 k가 주어졌을 때, a(1)+a(2)+…+a(k) 값을 빠르게 구하는 프로그램을 다음과 같이 작성하였다.

// a[1] + a[2] + ... + a[k]의 합을 구함

p = _____㉠_____;

d = p;

sum = 0;

while (d > 0) {

    d = d / 2;

    if ( _____㉡_____ ) {

        sum = sum + a[p] + b[p];

        p = p + d;

    }

    else {

        p = p - d;

    }

}

printf("%d\n", sum);

6. ㉠에 들어갈 내용으로 알맞은 것은?

① k   ② k / 2   ③ n / 2   ④ n   ⑤ n + 1

7. ㉡에 들어갈 내용으로 알맞은 것은?

① p < n   ② k < p   ③ k <= p   ④ p < k   ⑤ p <= k

※ 포화 이진 트리의 예제로 루트 노드부터 시작해야 하므로 6번의 답은 n/2입니다. 한가지 유념해야 점은 내부 노드의 값은 짝수이므로 실제로는 (n/2)의 값은 올림값이 되어야 합니다 결국 위의 문제에서 p값은 8로 시작하고  d값은 4부터 시작합니다. k가 6인 경우 p는 8, 4, 6, 7 로 움직이고 d는 4, 2, 1, 0으로 움직이며 결국 트리의 해당 위치를 정확하게 찾아갑니다. 7번의 경우 p <= k 일때로 k가 6인 경우 p가 4, 6일때 합산된 결과를 가져옵니다.