[자료구조] 트리(Trees)

 

 

트리

: 정보의 항목들이 가지(branch)로 연결되는 데이터 구조

: 하나 이상의 노드로 이루어진 유한 집합.

• 루트(root) 노드 1개
• 나머지는 n개의 분리 집합 T1,T2,...Tn으로 분할.(Ti는 서브트리)

 

- 노드: 데이터(정보) 아이템+ 다른 노드로 뻗은 가지(branch)

- 차수(degree): 노드의 서브트리 수(= link 수 = branch 수)

- 단말(leaf) 노드: 차수 = 0 => 자식(child) 비존재

- 비단말 노드: 차수 !=0  => 자식(child) 존재

- 자식: 노드 X의 서브트리의 루트(<->부모)

- 형제(sibling): 부모가 같은 자식들

- 트리의 차수 = max{노드의 차수}

- 조상: 루트까지의 경로상에 있는 모든 노드

- 노드 레벨: 루트=레벨1, 자식레벨 = 부모레벨+1

- 트리의 높이(깊이): max{노드 레벨}

 

트리의 표현

리스트 표현

(A(B(E(K,L), F),C(G),D(H(M),I,J)))

트리 그림으로 나타낸 것

연결 리스트로 나타낸 것

 

차수가 k인 트리에 대한 노드 구조

공간 낭비가 많다.

k원 트리에서 노드 수가 n이면 nk의 자식 필드 중 n(k-1)+1개 필드가 0

 

왼쪽 자식-오른쪽 형제 표현(left child-right sibling)

node degree의 편차가 클 때, degree가 고정되지 않을 때 child node에 대한 모든 링크를 유지하는 것은 낭비.

 

차수가 2인 트리 표현

- 왼쪽 자식-오른쪽 형제 트리의 오른쪽 형제 포인터를 45도 회전

- 루트의 오른쪽 자식은 공백.

이진트리(binary Tree): 왼쪽 자식-오른쪽 자식 트리

 

참고용

 

 

이진 트리(Binary Trees)

이진 트리의 특성

- 한 노드는 최대 두개의 자식노드를 가짐

- 왼쪽 서브트리와 오른쪽 서브트리 구별

- 0개의 노드를 가질 수 있음(공백 트리)

 

이진트리의 정의

- 공백이거나

- 루트와 왼쪽 서브트리, 오른쪽 서브트리 두 개의 분리된 이진 트리로 구성된 노드의 유한 집합

 

ADT

 

상이한 이진트리(Different Binary Trees)

이진 트리와 일반 트리의 차이점

-공백 이진 트리 존재

-자식의 순서 구별(left child와 right child)

 

편향 이진 트리(skewed tree): 한쪽으로만 몰린(=편향된) 이진 트리

완전 이진 트리(Complete Binary Trees): 순차적으로 노드를 구성한 이진 트리

+Full Binary Tree: leaf 노드를 제외한 모든 노드가 2개의 자식을 가지는 트리.

 

이진트리의 성질

레벨 i에서의 최대 노드 수: 2^(i-1) (i>=1)

- 귀납 기초: 레벨 i=1이면 루트만이 유일한 노드-> 이때 최대 노드수는 2^(1-1)=2^0 =1

- 귀납 가설: i가 1보다 큰 임의의 양수라고 하면 레벨 i-1에서 최대 노드 수는 2^(i-2)라 가정

- 귀납 과정: 가설에 의해 레벨 i-1의 최대 노드 수는 2^(i-2)이고 각 노드의 최대 차수가 2이므로 레벨 i에서의 최대 노드 수는 2^(i-1)

 

깊이가 k인 이진 트리의 최대 노드 수: 2^k -1(k>=1)

Σ(레벨 i의 최대 노드 수) = Σ2^(i-1) = 2^k -1 --등비수열의 합.

 

리프 노드 수와 차수가 2인 노드 수와의 관계

- n0 = n2 +1 (n0: 리프 노드 수, n2: 차수가 2인 노드 수)

-증명

• 총 노드 수 = 리프 노드 수+차수 1인 노드+차수 2인 노드
• 루트를 제외한 모든 노드들은 들어오는 가지가 하나씩 있으므로 총 노드수는 총 가지 수+1 (1은 루트)
• 모든 가지들은 차수가 2인 노드나 1인 노드에서 뻗어 나오므로 총 가지 수 = 2*(차수 2인 노드수)+(차수 1인 노드 수)
• 즉 (총 노드 수) = 2*(차수 2인 노드수)+(차수 1인 노드 수)+1 = 리프 노드 수+차수 1인 노드+차수 2인 노드
• 이 등식을 정리하면 n0 = n2+1이 됨.

포화 이진 트리(full binary tree)

- 깊이가 k이고, 노드 수가 2^k -1인 이진 트리

- 노드 번호 1~2^k-1까지 순차적 부여 가능

 

완전 이진 트리(complete binary tree)

- 깊이가 k이고 노드 수가 n인 이진 트리

- 각 노드들이 깊이가 k인 포화 이진 트리에서 1부터 n까지 번호를 붙인 노드와 1:1 일치

- n 노드 완전 이진 트리의 높이는 ⌈log_2(n+1)⌉ (이하의 정수 중 가장 큰 수)

 

이진 트리 표현

배열 표현(Array Representation)

- 1차원 배열에 노드 저장

- 노드 번호 i는 배열의 i번째 위치(사상, mapping)

- 보조 정리

• parent(i) : ⌊i/2⌋  (if i!=1. 1이면 루트)
• leftChild(i): 2i (if 2i<=n, 만족하지 않으면 왼쪽 자식 없음)
• rightChild(i): 2i+1 (if 2i+1<=n, 만족하지 않으면 오른쪽 자식 없음)

- 완전 이진 트리: 낭비 공간 없음.

편향 트리: 공간 낭비. 최악의 경우 k 깊이에서 2^k-1 중 k개만 사용됨.

 

typedef struct node *treePointer;
typedef struct node{
	int data;
    treePointer leftChild, rightChild;
    // 부모를 알기 어렵단 문제로, parent 필드가 추가될 수 있음.
};

 

 

이진트리 순회(Binary Tree Traversals)

트리 순회(Tree traversal): 트리에 있는 모든 노드를 한번씩만 방문

순회 방법: LVR, LRV, VLR, VRL, RVL, RLV

-L: 왼쪽 이동, V: 노드 방문, R: 오른쪽 이동

일반적으로 왼쪽을 오른쪽보다 먼저 방문(LR)

-LVR: 중위 순회(inorder)

-VLR: 전위 순회(preorder)

-LRV: 후위 순회(postorder)

 

+Graph에는 Depth First와 Breath First가 존재.

 

중위 순회-recursive한 구현

void inorder(treePointer ptr)
{
	if(ptr) {
    	inorder(ptr->leftChild); // L
        printf("%d", ptr->data); // V
        inorder(ptr->rightChild); //R
    }
}

 

 

전위 순회-recursive한 구현

void preorder(treePointer ptr)
{
	if(ptr) {
    	printf("%d", ptr->data); // V
        inorder(ptr->leftChild); // L
        inorder(ptr->rightChild); //R
    }
}

 

 

후위 순회-recursive한 구현

void postorder(treePointer ptr)
{
	if(ptr) {
        inorder(ptr->leftChild); // L
        inorder(ptr->rightChild); //R
        printf("%d", ptr->data); // V
    }
}

 

 

반복적 중위 순회(Iterative Inorder Traversal)

- recursive가 아닌 iterative한 방식으로 동등한 함수 구현

//Time Complexity : O(n)
//Space Complexity : O(n)

void iterInorder(treePointer node)
{
	int top = -1; //스택 초기화
    treePointer stack[MAX_STACK_SIZE];
    for(;;){
    	for(; node; node=node->leftChild) push(node); //STACK PUSH
        node = pop(); //STACK POP
        
        if(!node) break;
        
        printf("%d", node->data);
        node = node->rightChild;
    }
}

Note: 절대 recursive한 구현을 피해야하는 경우

1) depth가 미정일 경우.(얼마나 반복될지 알 수가 없음)

2) 자원의 제약 ex. 임베디드 시스템

3) 병렬처리(절대 안됨)

 

레벨 순서 순회(Level-order Traversal)

- 큐 사용

- 루트 방문->왼쪽 자식->오른쪽 자식

void levelOrder(treePointer ptr)
{
    int front = rear = 0;
    treePointer queue[MAX_QUEUE_SIZE];
    
    if (!ptr) return;
    addq(front, &rear, ptr);
    for ( ; ; ) {
        ptr = deleteq(&front, rear);
        if (ptr) {
        	printf(“%d”, ptr->data);
            
            if (ptr->leftChild) addq(front, &rear, ptr->leftChild);
            if (ptr->rightChild) addq(front, &rear, ptr->rightChild);
        }
        else break;
    }
}

 

 

스택 없는 순회.

: 스택을 위한 추가적 공간 없이 이진트리 순회가 가능한가?

방법 1) 각 노드에 parent 필드를 추가하여 스택 없이도 루트 노드로 올라갈 수 있게

방법 2) thread 이진트리로 표현.

- 각 노드마다 두 비트가 필요하고,(정보)

- 두 Child 필드를 루트로 돌아갈 경로를 유지하게 함.

- 경로상의 주소 스택은 리프 노드에 저장

 

 

 

이진트리의 추가연산(Additional Binary Operations)

이진트리의 복사(Copying Binary Trees)

treePointer copy(treePointer original)
/* 주어진 트리를 복사하고 복사된 트리의 treePointer를 반환한다. */
{
    treePointer temp;
    if (orginal) {
        temp = (treePointer) malloc(sizeof(node));
        
        if ( IS_FULL(temp)) {
            fprintf(stderr, “The memory is full\n”);
            exit(1);
        }
        
        temp->leftChild = copy(original->leftChild);
        temp->rightChild = copy(original->rightChild);
        temp->data = original->data;
        
        return temp;
    }
    return NULL;
}

 

동일성 검사(Testing Equality)

/* 두 이진 트리가 동일하면 TRUE, 그렇지 않으면 FALSE를 반환한다. */
int equal(treePointer first, treePointer second)
{
    return ((!first && !second) ||
            (first && second && (first->data == second->data) &&
            equal(first->leftChild, second->leftChild) &&
            equal(first->rightChild, second->rightChild));
}

 

만족성 문제(The Satisfiability Problem)

: 변수 x1, x2...xn과 연산자 ^, v, ┓(~)으로 이루어진 식

-변수는 Boolean 값

 

규칙

1) 변수도 하나의 식

2) x, y가 식이면 ┓x, x^y, x ∨ y도 식

3) 연산 순서는 ┓,^, ∨ 순, 괄호 사용 

 

명제 해석식(formula of propositional calculus)

-위 규칙을 이용하여 구성한 식

 

명제식의 만족성 문제: 식의 값이 true가 되도록 변수에 값을 지정할 수 있는 방법이 있는가?

만족성 문제를 위한 노드 구조

enum {not, and, or, true, false} logical;
typedef struct node *treePointer;
typedef struct node {
    treePointer leftChild;
    logical data;
    short int value;
    treePointer rightChild;
};

 

 

만족성 알고리즘의 첫번째 버전

- 리프의 data는 노드가 나타내는 변수의 현재 값

- root가 n개의 변수를 갖는 명제식의 트리를 가리킴

//Time complexity: O(2^n). it is not Reasonable.

for(all 2^n possible combinations)
{
	Generate the next combination;
    Replace the variables by their values;
    Evaluate root by traversing it in postorder;
    if(root->value){
    	printf(<<coombination>);
        return;
    }
}
printf("No satisfiable combination\n");

 

후위 순회 연산 함수

void postOrderEval(treePointer node)
{/* 명제 해석 트리를 계산하기 위해 수정된 후위 순회 */
    if (node) {
    postOrderEval (node->leftChild);
    postOrderEval (node->rightChild);
    switch(node->data) {
        case not:
        	node->value = !node->rightChild->value; break;
        case and:
        	node->value = node->rightChild->value &&
        				  node->leftChild->value; break;
        case or:
        	node->value = node->rightChild->value ||
        				  node->leftChild->value; break;
        case true:
        	node->value = TRUE; break;
        case false:
        	node->value = FALSE;
    }
}

 

 

스레드 이진 트리(Threaded Binary Trees)

스레드(Threads)

n-노드 이진 트리의 연결 표현

• 총 링크 수: 2n
• NULL 링크 수: n+1
  • # of nodes = n = 2^k -1
  • # of null link = 2*(# of leaf nodes) = 2*2^(k-1) = 2^k = n+1

스레드 구성 방법

- 널 링크 필드를 다른 노드를 가리키는 포인터로 대치

- if ptr->rightChild == NULL, ptr->rightChild = ptr의 중위 후속자(다음에 갈 곳)에 대한 포인터

- if ptr->leftChild == NULL, ptr->leftChild = ptr의 중위 선행자(이전에 간 곳)에 대한 포인터

 

노드 구조

- leftThread == false if leftChild가 포인터

                   == true if leftChild가 스레드

- rightThread == false if rightChild가 포인터

                   == true if rightChild가 스레드

 

헤드 노드

-분실 스레드(loose thread) 문제 해결 -> 헤드 노드를 가리키도록

- root가 헤드노드를 가리키도록: root->leftChild가 첫번째 노드

 

tree를 접근할 수 있는 방법 3가지

1) root로

2) root->leftChild

3) tree

 

스레드 이진 트리의 중위 순회

x->rightThread

== true : x->rightChild

==false : 오른쪽 자식의 왼쪽 자식 링크를 따라가서 leftThread==true인 노드까지 이동

threadedPointer insucc(threadedPointer tree)
{
    threadedPointer temp;
    temp = tree->rightChild;
    
    if (!tree->rightThread)
        while (!temp->leftThread) temp = temp->leftChild;
        
    return temp;
}

/* 스레드 이진 트리의 중위 순회 */
void tinorder(threadedPointer tree)
{
    threadedPointer temp = tree;
    
    for ( ; ; ) {
        temp = insucc(temp);
        if (temp == tree) break;
        
        printf(“%3c”, temp->data);
    }
}

 

스레드 이진 트리에서의 노드 삽입

- s의 오른쪽 자식으로 r을 삽입

- s의 오른쪽 자식이 null이면 그대로 삽입

- s의 오른쪽 자식이 null이 아니면 s의 오른쪽 자식을 r에 연결하고 삽입(thread 수정 필요)

/* 스레드 이진 트리에서 r을 s의 오른쪽 자식으로 삽입 */
void insertRight(threadedPointer s, threadedPointer r)
{
    threadedPointer temp;
    r->rightChild = parent->rightChild;
    r->rightThread = parent->rightThread;
    r->leftChild = parent;
    r->leftThread = TRUE;
    s->rightChild = r;
    s->rightThread = FALSE;
    
    if (!r->rightThread) {
        temp = insucc(r);
        temp->leftChild = r;
    }
}