Data-Structure - Tree

Terminology

---

Definition

tree는 위와 같이 정의됩니다. 

root라는 특수한 노드가 있고 이 root라는 노드를 기준으로 disjoint한 Tree의 set으로 나누어 집니다. 이를 subtree라고 합니다.

 

Representation of Trees

---

대게 list로 위와 같이 Child Node를나열해서 Tree를 표현할 수도 있습니다. 하지만 이는 일반적이지 않은 방법이고 아래와 같이 Left Child-Right Sibling Representation을 사용하기도 합니다. (underground yea~)

 

Left Child-Right Sibling Representation

---

이와 같이 left-child는 leftmost child를 가리키고 right sibling필드는 이와 가장 가까운 right sibling을 가리키게 합니다.

이제 이를 45도 기울여서 이진트리로 표현하게 되면 아래와 같게 됩니다.

 

Binary Trees

---

위와같이 표현된 이진트리는 Data-Structure에서 많이 보게 될 매우 중요한 구조입니다. 이러한 Binary Tree의 주요 특징은 트리의 degree가 2를 넘어가면 안된다는 것이고, left subtree와 right subtree로 나뉘어질 수 있다는 것이고, 이는 zero nodes를 가질 수도 있습니다. 

Binary Tree의 정의는 유한된 노드들의 집합으로서, 빌 수도 있고 루트라는 특수 노드를 바탕으로 disjoint한 이진트리로 나뉘어지는 것이라고 할 수 있습니다.

 

또한 Binary Tree의 특수 형태는 위와 같이 2가지 정도로 나타낼 수 있는데, Skewed Binary Tree는 사향 이진트리로써 한쪽으로 몰린 이진트리를 말하며, Complete Binary Tree는 왼쪽부터 차례대로 쌓아 나가는 이진 트리를 말합니다.

 

Properties of Binary Trees

---

Binary Tree의 특징은

1. level i에서 노드의 최대 갯수는 2^i-1, i >= 1이 됩니다.
2. depth가 k에서 노드의 최대 갯수는 2^k, k >= 1이 됩니다.
3. n0을 leaf_node의 갯수라고 하고, n2를 degree가 2인 노드의 갯수라고 하면 n0 = n2 + 1이 됩니다.

이는 간단히 예시를 들어가면서 혼자 생각해보면 당연하다고 생각이 들겁니다. 그리고 3)은 수학적 귀납법으로 쉽게 증명가능합니다.

 

또한 Complete Binary Tree에서 특수한 형태인 Full Binary Tree가 있습니다. 이는 depth가 k일 떄 노드의 갯수가 2^k, k >= 0인 트리를 말합니다.

 

또한 Complete Binary Tree에서 height는 노드가 n개 있다면 [log2(n + 1)]이 됩니다.

 

 

Array Representation

---

tree를 array로 표현할 때는 증명된 Lemma를 사용해야 합니다. 해당 노드의 인덱스를 i라고 하고 tree의 노드 갯수가 n - 1개 있다고 합시다. 그러면 array로 represent할 떄 0번 index는 버린다고 하면 1~n까지의 index를 사용하게 됩니다. 이러한 상황에서 parent Node는 [i / 2] 가 되고, leftChild는 2i ( 2i <= n ), rightChild는 2i + 1 ( 2i + 1 <= n )이게 됩니다.

 

< Examples >

이제 이러한 Array representation을 Skewed tree와 Complete tree에 적용해 봅시다.

이렇게 각각 표현할 수 있습니다. 이 때 딱 느꼈을 수도 있지만 Skewed tree를 Array로 표현하게 되면 많은 메모리 용량이 낭비되게 됩니다. 이에 반해 Complete Tree는 어떠한 공간도 낭비되지 않음을 볼 수 있습니다. 이로 인해 Tree는 Tree의 특성 때문에 Array로 표현하기에는 제약이 있음을 느꼈을 겁니다

 

Linked Representation

---

Array Representation의 제약때문에 나타난 것이 Linked Representation입니다. 이는 Array Representation에서 node의 insertion과 deletion을 중간에서 하게 되면 많은 데이터의 movement가 일어나게 됨과, 많은 공간낭비가 있을 수 있음에서 착안한 형태입니다. Linked Representation으로 Tree를 구현하게 되면 아주 쉽게 insertion과 deletion을 구현할 수 있게 됩니다.

기본적인 형태는 위와 같습니다. 

< Examples >

이제 이러한 Linked representation을 Skewed tree와 Complete tree에 적용해 봅시다.

딱봐도 Array Representation보다 공간 낭비도 적고 Tree를 다루기 쉽게 생겼을 겁니다. ㅎㅎ

 

Binary Tree Traversals

---

Traversing이란 Tree의 노드를 정확히 딱 한번만 방문하는 것을 말합니다. 만약 한 노드가 방문되었다면, 어떠한 동작이 수행되게 함이 Traversing의 목적입니다. 이는 Tree에서 Linear order를 생성해 냅니다.

 

이러한 Traversing에는 6가지 종류가 존재합니다. 일단 L, V, R을 정의하겠습니다. L은 moving left, V는 visiting the node, R은 moving right로 하겠습니다. 이를 적절히 배합하면 3! = 6가지가 나오며 종류는 다음과 같습니다. LVR, LRV, VLR, VRL, RVL, RLV

 

우리는 여기서 제약조건을 하나 더 걸어줘서 단순하게 생각하겠습니다. 우리는 Traversing을 할 때 left->right순으로 순회한다는 규칙을 걸어주겠습니다. 그러면 3가지의 Traversing 종류가 남게 됩니다.

 

• LVR : inorder ( 중순위 )
• LRV : postorder ( 전순위 )
• VLR : preorder ( 후순위 )

또한 이는 자연스럽게 infix, postfix, prefix로도 매칭이 되며 트리의 노드에 적절하게 operator를 넣어주면 됩니다.

 

< Inorder Traversal >

Inorder Traversal은 위에서도 말했지만 LVR으로 표현됩니다. 이를 코딩으로 구현하려면 간단히 재귀호출을 써주면 됩니다. 재귀호출 순서로는 leftChild로 쭉 가준 다음에 해당 node의 data를 print하고 rightChild로 쭉 가주면 됩니다.

위의 그림에 있는 Tree를 Inorder Traversal을 통해서 나타내면 위의 순서가 됩니다.

<Preorder Traversal >

Preorder Traversal은 VLR으로서, 먼저 해당 node의 data를 print하고 leftChld, rightChild순으로 순회해 주면 됩니다.

 

<Postorder Traversal >

Postorder Traversal은 LRV로서, leftChild, rightChild순으로 순회하고 맨 마지막으로 node를 방문해 data를 출력하면 됩니다.

 

< Iterative Inorder Traversal >

이는 recursion없이 스택을 사용해서 inorder traversal을 하는 방법입니다.

void iter_inorder(treePointer root)
{
    treePointer ptr;
    node temp;

    top = -1;
    ptr = root;

    while (1)
    {
        while (ptr != NULL)
        {
            push(*ptr);
            ptr = ptr->leftChild;
        }

        temp = pop();
        if (temp.data == ERROR_KEY)
            break;

        printf("%c ", temp.data);
        ptr = temp.rightChild;
    }
}

계속 leftChild로 가면서 하나 팝하고 rightChild를 Ptr로 지정해 가면서 하면 됩니다.

 

<Level-Order Traversal >

이는 queue를 이용해서 traversal을 하는 것인데 노드를 방문하고 큐에 노드를 집어넣고 하나씩 빼고 또 넣고 하면서 진행해 갑니다.

void levelOrder(treePointer ptr) {
	if (!ptr)
		return;
	
	Enqueue(ptr);  

	while (1) {
		ptr = Dequeue();
		if (ptr)
		{
			printf("%d ", ptr->data);

			if (ptr->leftChild)
				Enqueue(ptr->leftChild);
			if (ptr->rightChild)
				Enqueue(ptr->rightChild);
		}
		else
			break; 
	}
}

이가 iterative inorder traversal과의 차이는 큐를 이용한다는 점입니다.

 

Copying Binary Trees

기본적인 이진트리를 복사하는 방법은 재귀적으로 leftChild와 rightChild를 복사해 가면 됩니다.

treePointer copy(treePointer original)
{
    /**
     * this function returns a treePointer to an exact copy of the original tree
     */
    treePointer temp;
    if (original)
    {
        MALLOC(temp, sizeof(*temp));
        temp->leftChild = copy(original->leftChild);
        temp->rightChild = copy(original->rightChild);
        temp->data = original->data;
        return temp;
    }
    return NULL;
}

 

Testing Equality

다음으로는 이제 복사를 했으니까 둘의 동등성을 평가할 수 있어야 합니다. 만약 비교하고자 하는 둘의 트리가 같은 구조를 갖고 같은 값을 갖고 있다면 true를 반환합니다

int equalTree(treePointer first, treePointer second)
{
    printf("\n%c %c %d\n", first->data, second->data, !second && !first);

    // first와 second이 다르면 false를 리턴하고 같으면 true를 리턴합니다.
    return ((!first && !second) ||
            (first && second && (first->data == second->data) &&
             equalTree(first->leftChild, second->leftChild) &&
             equalTree(first->rightChild, second->rightChild)));
}

 

The Satisfiability Problem

이는 위와같은 트리가 있을 때, true가 나올 수 있는 조합을 찾는 문제입니다. 이러한 문제를 Satisfiability Problem이라고 합니다. 만약에 변수가 3개라고 하면 2^3에 해당하는 조합을 다 대입해서 postorder traversal을 통해서 찾아가야 합니다.

 

간단하게 2가지 변수만 있을 때를 고려하여 간단히 확인 용도로만 코딩하였습니다.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

typedef enum
{
    not,
    and,
    or
    ,
    true,
    false
} logical;

typedef struct node_
{
    struct node_ *left_child;
    logical data;
    short int value;
    struct node_ *right_child;
} node, *tree_pointer;

void initNode(tree_pointer *ptr, logical data)
{
    MALLOC(*ptr, sizeof(node));
    (*ptr)->data = data;
    (*ptr)->left_child = NULL;
    (*ptr)->right_child = NULL;
}

void post_order_eval(tree_pointer node)
{
    if (node)
    {
        post_order_eval(node->left_child);
        post_order_eval(node->right_child);
        switch (node->data)
        {
        case not:
            node->value = !node->right_child->value;
            break;
        case and:
            node->value = node->right_child->value && node->left_child->value;
            break;
        case or:
            node->value = node->right_child->value || node->left_child->value;
            break;
        case true:
            node->value = TRUE;
            break;
        case false:
            node->value = FALSE;
            break;
        }
    }
}

logical intArr[100] = {0};
logical intArr_final[100][100] = {0};

int count = 0;
void combination(int startIdx, int final)
{
    if (startIdx == final)
    {
        for (int i = 0; i < final; i++)
        {
            intArr_final[count][i] = intArr[i];
        }
        count++;
        return;
    }

    intArr[startIdx] = false;
    combination(startIdx + 1, final);
    intArr[startIdx] = true;
    combination(startIdx + 1, final);
}

int main(void)
{
    tree_pointer root;
    tree_pointer newNode, newNode2, newNode3;

    tree_pointer treeArr[2] = {newNode2, newNode3};

    initNode(&newNode, or);
    root = newNode;

    // initNode(&newNode2, false);
    // newNode->left_child = newNode2;

    // initNode(&newNode3, true);
    // newNode->right_child = newNode3;

    combination(0, 2);
    printf("참이되는 조합은?\n");
    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            initNode(&treeArr[j], intArr_final[i][j]);
        }
        newNode->left_child = treeArr[0];
        newNode->right_child = treeArr[1];

        post_order_eval(root);
        if (root->value)
        {
            printf("%s %s\n", intArr_final[i][0] == false ? "FALSE" : "TRUE", intArr_final[i][1] == false ? "FALSE" : "TRUE");
        }
    }

    return 0;
}

다음과 같이 or연산자를 했을 때 조합이 적절히 출력됨을 보실 수 있습니다.

 

Threaded Binary Trees

 

이와같이 9개의 노드가 있다고 했을 때 10개의 null link가 존재하고 총 18개의 link가 존재합니다. 하지만 우리는 여기서 많은 메모리 효율성의 문제를 느끼게 되었고, 이러한 null link들을 inorder traversal에 도움이 되는 threads로 치환하자는 것입니다.

 

만약에 ptr->leftChild가 null이라면 ptr->leftChild을 inorder predecessor를 가리키게 해야 합니다. 또한 ptr->rightChild가 null이라면 ptr->rightChild는 inorder successor로 치환해야 합니다.

이러한 경우의 Inorder traversal은: H, D, I, B, E, A, F, C, G입니다. 이때 inorder predecessor와 inorder successor를 null노드를 찾아서 적절히 치환해주면 위와같이 threaded Binary tree형태가 됩니다.

 

이를 하기 위해서는 아래와 같은 구조체를 사용하게 됩니다.

이와같이 2개의 필드를 추가합니다. 만약 ptr->leftThreaded(or rightThread) = TRUE라면 ptr->leftChild ( or rightChild )가 thread를 포함하게 됩니다.

또한 root의 left subtree가 actual tree의 header를 가리키게 해야 합니다.( root->leftChild ) 이러한 threads는 tree의 inorder traversal을 stack없이 가능하게 합니다. 이제 이를 c언어로 구현하는 법에대해서 알아보겠습니다.

typedef struct threaded_tree_
{
    short int left_thread;
    struct threaded_tree_ *left_child;
    char data;
    struct threaded_tree_ *right_child;
    short int right_thread;
} threaded_tree, *threaded_pointer;

threaded_pointer insucc(threaded_pointer tree)
{
    /* find the inorder sucessor of tree in a threaded binary tree */
    threaded_pointer temp;
    temp = tree->right_child;

    // tree->right_thread가 false가 아니라면 즉 이뜻은 inorder preccesdor가 없다면.
    if (!tree->right_thread)
    {
        // left_thread가 true인 동안 left_child로 이동
        while (!temp->left_thread)
        {
            temp = temp->left_child;
        }
    }
    return temp;
}

다음과 같이  후속자를 찾는 코드를 짜야 합니다. 우선 tree->right_child를 temp변수에 담아줍니다. 그 후, right_thread가 true라면 여기서 끝내고, right_thread가 false라면 left_thread가 false인 동안 left_child로 이동하게 하면 됩니다. 이러한 콛를 했을 때 노드의 방문 순서를 표현하게 되면 root - A - B - D - H - D - I - B - E - A - C - F - C - G - root가 되어 끝나게 됩니다. 이 때의 출력되는 노드는 당연히 inorder순서인 H - D - I - B - E - A - F - C - G가 됩니다. 아래의 코드는 insucc함수를 무한정 반복하는데 시작 threaded_pointer로 다시 돌아오게 되면 끝나게 해주는 코드를 구현한 것입니다.

void tinorder(threaded_pointer tree)
{
    threaded_pointer temp = tree;
    for (;;)
    {
        temp = insucc(temp);
        if (temp == tree)
            break;
        printf("%3c", temp->data);
    }
}

또한 이러한 threaded binary tree에서의 삽입에 대해서 알아보겠습니다. 우선 상황을 가정하면 s의 오른쪽 자식에 r를 삽입해야 한다고 가정해 봅시다.

< s ihas an empty right subtree >

< right subtree of s is not empty >

만약 이렇게 삭제하는 상황에서 변화되는 것을 살펴봅시다. 먼저 r의 rightChild를 s의 rightChild로 지정하고, r의 rightThread도 만들어 주어야 하는데, 첫번째 상황같은 경우에서를 처리해주기 위해서 r->right_thread를 s->right_thread로 해주어야 합니다. 다음으로는 r의 leftChild는 s가 되고 left_thread는 무조건 TRUE로 지정해 주어야 합니다. 그 이유는 r이 추가되면 leftChild부분은 null이 되기 때문입니다. 그 다음으로 s의 rightChild를 r로 해주고 right_thread를 FALSE로 해주어야 합니다.

마지막으로 r의 right_thread가 false라면 insucc함수를 이용해서 찾아낸 노드의 left_child를 r로 해주어야 하는 과정을 거쳐야 끝나게 됩니다.