[2기 대구 이현복] Data Structure - Tree

안녕하세요.

대구 멤버십 21기 이현복 입니다.

Data Structure중 네번째 주제인 Tree에 대한 이야기 입니다

Tree란 하나 이상의 node로 이루어진 유한 집합으로서

노드 중에는 루트(Root)라는 노드가 하나 있고

나머지 노드들은 n ( >= 0 )개의 분리 집합 T1, ..., Tn 으로 분할 될 수 있습니다.

T1, ..., Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 합니다.

계층(Hierarchy)를 갖는 비선형 자료 구조(nonlinear data structure)입니다.

여기에서 가장 중요하게 생각해 볼 점은 집합 이라는 것과

비선형 즉 1차원 적인 선이 아니라 공간을 표현한다는 점입니다.

트리(Tree)로 만들어지는 형태는 다양하지만 특히 Binary Tree(이진 트리)를 많이 사용하게 되는데

컴퓨터 적인 입장에서 이진트리는 선을 2개로 제한할 수 있기 때문에 자료구조화 하기 쉽고

좌측과 우측에 다른 의미를 부여함으로써 일반적인 트리 표현을 가능하게 합니다.

좌측과 우측의 의미가 다르기 때문에 A좌측에 B가 있는 트리와 A우측에 B가 있는 트리는 다른 트리가 되며

한쪽으로 쏠리게되는 편향 이진 트리가 만들어 질 수 도 있습니다.

가능한한 가득찬 포화 이진트리가 되면 좋겠지만 아닐경우 완전 이진트리가 되도록 만드는게 최선입니다.

이런 이진 트리를 표현하는 방법으로는 Array와 List를 이용한 2가지 방법을 생각해 볼 수 있습니다.

Array를 사용할 경우 다음과 같은 정리를 이용하여 표현 할 수 있다.

n개의 노드를 가진 완전 이진 트리를 순차적으로 표현하면 depth = ,

인덱스 i(1 <= i <= n) 을 갖는 임의의 노드에 대해 다음이 성립한다.

이를 이용하여 다음과 같은 형태로 표현 할 수 있다.

List를 사용할 경우 다음과 같이 2개의 링크(포인터)를 가진 구조체를 이용하여 구현 할 수 있으며

typedef struct _node

{

int data;

struct _node *left_child;

struct _node *right_child;

} node;

이를 이용하여 다음과 같은 형태로 표현 할 수 있습니다.

트리는 선형 구조가 아니기 때문에 모든 노드를 방문하는 것이 쉽지 않습니다.

이진 트리 순회 방법을 이용하면 모든 노드를 특정한 순서대로 방문할 수 있기 때문에 중요한 기법입니다.

순회의 방법으로는 전위(preorder), 중위(inorder), 후위(postorder), 레벨(levelorder)의 방법이 있습니다.

전위 순회(PreOrder)는 

노드 방문

왼쪽 서브 트리 방문

오른쪽 서브 트리 방문

void preorder(node ptr) {

if ( ptr ) {

printf( "%d", ptr->data );

preorder( ptr->left_child );

preorder( ptr->right_child );

}

}

중위 순회(InOrder)는

왼쪽 서브 트리 방문

노드 방문

오른쪽 서브 트리 방문

void inorder(node ptr) {

if ( ptr ) {

inorder( ptr->left_child );

printf( "%d", ptr->data );

inorder( ptr->right_child );

}

}

or

void iter_inorder(node ptr) {

int top = -1;

node stack[MAX_STACK_SIZE];

while(true) {

for( ; node; node = node->left_child )

push( &top, node );

node = pop( &top );

if( !node ) break;

printf( "%d", node->data );

node = node->right_child;

}

}

후위 순회(PostOrder)는

왼쪽 서브 트리 방문

오른쪽 서브 트리 방문

노드 방문

void postorder(node ptr) {

if ( ptr ) {

postorder( ptr->left_child );

postorder( ptr->right_child );

printf( "%d", ptr->data );

}

}

레벨 순회(LevelOrder)는

노드 방문

왼쪽 노드 방문

오른쪽 노드 방문

왼쪽 - 왼쪽 노드

왼쪽 - 오른쪽 노드

...

void levelorder(node ptr) {

int front = 0, rear = 0;

node queue[MAX_QUEUE_SIZE];

addq( front, &rear, ptr );

while(true) {

ptr = deleteq( &front, rear );

if( ptr == NULL ) break;

if( ptr->left_child )

addq( front, &rear, ptr->left_child );

if( ptr->right_child )

addq( front, &rear, ptr->right_child );

}

}

재귀적 방법에 의해 전위, 중위, 후위 순회는 쉽게 구현할 수 있으며

스택을 이용하여 중위 순회를 구현하거나

큐를 이용하여 레벨 순회를 구현할 수 있습니다.

트리의 또 다른 특성으로 집합이라는 의미가 있습니다.

다음과 같이 S1, S2, S3라는 집합을 나타내는 기호를 아래와 같은 형태로 표현 할 수 있습니다.

일반적인 트리와는 다르게 차일드가 루트를 가리키는 형태로 구현 되며

같은 루트를 가지고 있는 차일드는 같은 집합 이라는 의미로써 사용 됩니다.

집합의 특성상 원소의 수가 유한하면서도 각 요소를 가르킬수 있어야 하며 고유한 집합에 속한다는 점에서

리스트보다는 배열로 구현하는 것이 이점이 많습니다.

이를 위해 구현해야하는 함수는 2가지로

같은 집합인지 확인하는 find와 두 요소를 하나의 집합으로 만드는 union이 있습니다.

int find(int i) {

for( ; parent[i] >= 0; i = parent[i] );

return i;

}

void union(int i, int j) {

parent[i] = j;

}

위와 같이 union을 단순하게 구성할 경우

다음과 같이 연속적인 값을 입력하게 되면 변질 트리(degenerate tree)의 발생 가능성이 있습니다.

union( 0, 1 ), union( 1, 2 ), ... , union( n-2, n-1 )

따라서 가중 규칙을 적용하여 루트를 제한하는 방법을 고려 해 볼 수 있습니다.

이때 가중치를 표현하기 위해 배열에서 루트를 가르키는 -1을 -2, -3 등 자신에게 달린 child의 수로 고려하여

가중치를 부여할 수 있습니다.

voi union(int i, int j) {

int temp = parent[i] + parent[j];

if ( parent[i] > parent[j] ) {

parent[i] = j;

parent[j] = temp;

}

else {

parent[j] = i;

parent[i] = temp;

}

}

이렇다 할지라도 union함수에는 한계가 있어서 최악의 경우 다음과 같은 결과를 낼 수 있습니다.

이를 해결하기 위해 collapsing rule을 고려해 볼 수 있습니다.

find 가 실행되는 과정에서 만나는 root가 아닌 노드들을 root의 child로 변경하는 방법입니다.

void find(int i) {

int root, node, next;

for( root = i; parent[root] >= 0; root = parent[root] );

for( node = i; node != root && parent[node] != root; node = next ) {

next = parent[node];

parent[node] = root;

}

return root;

}

이 외에도 힙을 구성하는 것이나 이진 탐색 트리를 구성하는 것 등 다양한 기법이 있지만

공간적 표현을 이용하기 위한 순회와 집합을 표현하는 방법이 트리의 특성을 그대로 사용하기 때문에

트리를 이해함에 있어 중요하다고 생각합니다.

자료구조는 결국 데이터가 저장된 공간과 데이터를 가르키는 포인터의 세트라고 할 수 있는데

자료구조를 공부할 때 공간적인 측면과 포인터 즉 알고리즘적인 측면을 분리하여 공부한다면

특정한 상황에 자신에게 맞는 자료구조를 설계하는데 도움이 되지 않을까 싶습니다.