3. 트리

(1)

3. 트리



3.1 트리의 개요



3.2 이진 트리



3.3 트리의 운행

(2)

3.1 트리의 개요

트리 : 그래프의 일종 데이터 : 노드

순환적 정의

T = {R, T ₁ ,T ₂ ,…T _n } R : 루트

T _i : 서브-트리(트리)

(3)

(4)

1. 노드 2. 근 노드 3. 서브트리 4. 차수

5. 단 노드

6. 간 노드(nonterminal node) 7. 부-노드, 자-노드

8. Family tree : 조상, 자손 9. 레벨

10. 높이 11. 숲

3.1 트리의 개요

(5)

3.1트리의 개요

 3.1.4 트리의 종류



Ordered tree



Oriented tree



Binary tree



Skewed tree

(6)

(7)

3.2 이진 트리

여러가지 응용에 가장 넓이 사용 엄밀한 이진 트리

크누스 이진 트리

(8)

(9)

3.2.2 이진 트리와 관련된 정리

정리 1 : 이진 트리의 레렐 i에 있는 노드의 최대 개수는 2 ^i-1 이다.

정리 2 : 깊이가 k인 이진 트리에 있는 노드의 전체 개수는 최대 2 ^k -1 이다.

3.2 이진 트리

(10)

(11)

정리 4 : n개의 노드를 가진 전이진 트리, 즉 깊이가 log n + 1 인 트리가 1차원 배열에 저장되면 다음과 같은 관계가 성립된다.

(1) parent[i]는 i!=1일 때 i/2의 위치에 있게 된다.

(2) Leftchild[i]는 2i<=n일 때 2i의 위치에 있게 된다.

(3) rightchild[i]는 2i+1<=n 일 때 2i+1의 위치에 있게 된다.

3.2 이진 트리

(12)

(13)

3.3 트리의 운행

 트리의 운행(Traversal)



각 노드를 중복되지 않게 한번씩 방문하여 트리를 검색하는 방법

 트리의 운행 방법



Level order Traveral



Preorder Traversal



Inorder Traversal



Postorder Traversal

(14)

(15)

 7.3.2 이진 트리의 운행



L : 왼쪽으로의 이동



R : 오른쪽으로의 이동



D : 자료의 출력



Preorder Traversal----DLR



Inorder Traversal----LDR



Postorder Traversal----LRD

3.3 트리의 운행

(16)

 전위 운행

public static void preOrder(BinaryTreeNode t) {

if(t!=null) {

visit(t);

preOrder(t.leftChild);

preOrder(t.rightChild);

} }

출력: / - * A ** B C Log D E

3.3 트리의 운행

/ -

A **

B C

D

*

E

log

(17)

 중위 운행

public static void inOrder(BinaryTreeNode t) {

if(t!=null) {

inOrder(t.leftChild);

visit(t);

inOrder(t.rightChild);

} }

출력: A * B ** C - log D / E

7.3 트리의 운행

/ -

A **

B C

D

*

E

log

(18)

 후위 운행

public static void postOrder(BinaryTreeNode t) {

if(t!=null) {

postOrder(t.leftChild);

postOrder(t.rightChild);

visit(t);

} }

3.3 트리의 운행

/ -

A **

B C

D

*

E

log

 후위 운행

public static void postOrder(BinaryTreeNode t) {

if(t!=null) {

postOrder(t.leftChild);

postOrder(t.rightChild);

visit(t);

} }

출력: A B ** * D log - E /

(19)



7.3.3 운행의 응용



트리의 복사

public BinaryTreeNode copyTree(BinaryTreeNode bintree) {

if( bintree=!null){

BinaryTreeNode temptree=new BinaryTreeNode();

temptree.leftChild=copyTree(bintree.leftChild);

temptree.rightChild=copyTree(bintree.rightChild);

return temptree;

}

return null;

}

3.3 트리의 운행

(20)

 3.3.3 운행의 응용



두 트리의 비교

public int equal(BinaryTreeNode first, BinaryTreeNode second) {

return((fist==null && second==null)||

(first!=null&&second!=null&&

first.element==second.element)&&

equal(firt.leftChild, second.leftChild)&&

equal(first.rightChild, second.rightChild));

}

3.3 트리의 운행

(21)

트리의 응용



7.3.5 이진 트리의 이질 성격 public class BinaryTreeNode1

{

BinaryTreeNode1 leftChild;

BinaryTreeNode1 rightChild;

char operator;

float value;

}

(22)



이진드리를 이용한 수식의 계산

public float evalTree(BinaryTreeNode1 tree) {

if(tree!=null) {

evalTree(tree.leftChild);

evaltree(tree.rightChild);

switch(tree.operator){

case ‘+’:

tree.value=tree.leftChild.value+tree.rightChild.value break;

case ‘-’:

tree.value=tree.leftChild.value-tree.rightChild.value break;

case ‘*’:

tree.value=tree.leftChild.value*tree.rightChild.value break;

case ‘/’:

tree.value=tree.leftChild.value/tree.rightChild.value }

} }

7.3 트리의 운행

(23)

(24)

(25)

(26)

 이진 탐색 트리(binary search tree)

 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구 조

 이진 탐색 트리의 정의

• ⑴ 모든 원소는 서로 다른 유일한 키를 갖는다.

• ⑵ 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다 .

• ⑶ 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.

• ⑷ 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.

5. 이진 탐색 트리

(27)

 이진 탐색 트리의 탐색 연산

 루트에서 시작한다.

 탐색할 킷값 x를 루트 노드의 킷값과 비교한다.

• (킷값 x = 루트노드의 킷값)인 경우 :

☞ 원하는 원소를 찾았으므로 탐색연산 성공

• (킷값 x < 루트노드의 킷값)인 경우 :

☞ 루트노드의 왼쪽 서브트리에 대해서 탐색연산 수행

• (킷값 x > 루트노드의 킷값)인 경우 :

☞ 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행

 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

5. 이진 탐색 트리

(28)

 탐색 연산 알고리즘

5. 이진 탐색 트리

(29)

 탐색 연산 예) 원소 11 탐색하기

① 찾는 킷값 11을 루트노드의 킷값 8과 비교

(찾는 킷값 11 > 노드의 킷값 8) 이므로 오른쪽 서브트리를 탐색

② (찾는 킷값 11 > 노드의 킷값 10) 이므로, 다시 오른쪽 서브트리를 탐색

③ (찾는 킷값 11 < 노드의 킷값 14) 이므로, 왼쪽 서브트리를 탐색

④ (찾는 킷값 11 = 노드의 킷값 11) 이므로, 탐색 성공! (연산 종료)

5. 이진 탐색 트리

(30)

 이진 탐색 트리의 삽입 연산

1) 먼저 탐색 연산을 수행

• 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.

• 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.

2) 탐색 실패한 위치에 원소를 삽입한다.

5. 이진 탐색 트리

(31)

 이진 탐색 트리에서의

5. 이진 탐색 트리

삽입할 자리 탐색

삽입할 노드 만들기

탐색한 자리에 노드연결

(32)

 이진 탐색 트리에서의 삽입 연산 예) 원소 4 삽입하기

① 찾는 킷값 4를 루트노드의 킷값 8과 비교하여,

(찾는 킷값 4 < 노드의 킷값 8) 이므로, 왼쪽 서브트리를 탐색한다.

② (찾는 킷값 4 > 노드의 킷값 3) 이므로, 오른쪽 서브트리를 탐색한다.

③ (찾는 킷값 4 < 노드의 킷값 5) 이므로, 왼쪽 서브트리를 탐색해야하는데 왼쪽 자식 노드가 없으므로 탐색 실패!

이때, 탐색 실패가 결정된 위치 즉, 왼쪽 자식노드의 위치가 삽입 위치가 된다.

④ 탐색작업으로 찾은 자리 즉, 노드 5의 왼쪽 자식노드 자리에 노드 4를 삽입한다.

5. 이진 탐색 트리

(33)

• 단순 연결 리스트로 표현한 이진트리에서의 원소 4 삽입하기

5. 이진 탐색 트리

q q

q

탐색실패!

(34)

 이진 탐색 트리의 삭제 연산

1) 먼저 탐색 연산을 수행

• 삭제할 노드의 위치를 알아야 하므로 트리를 탐색한다.

2) 탐색하여 찾은 노드를 삭제한다.

• 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요하다.

−

삭제할 노드의 경우

• 삭제할 노드가 단말노드인 경우 : 차수가 0인 경우

• 삭제할 노드가 하나의 자식노드를 가진 경우 : 차수가 1인 경우

• 삭제할 노드가 두개의 자식노드를 가진 경우 : 차수가 2인 경우

5. 이진 탐색 트리

(35)

 단말 노드의 삭제 연산

• 노드 4를 삭제하는 경우

5. 이진 탐색 트리

(36)

• 노드 4를 삭제하는 경우에 대한 단순 연결 리스트 표현

−

노드를 삭제하고, 삭제한 노드의 부모 노드의 링크 필드에 null 설정

5. 이진 탐색 트리

(37)

 자식 노드가 하나인 노드, 즉 차수가 1인 노드의 삭제 연산

• 노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다.

• 후속 처리 : 이진 탐색 트리의 재구성

−

삭제한 부모노드의 자리를 자식노드에게 물려준다.

• 예) 노드 10을 삭제하는 경우

5. 이진 탐색 트리

8

3 10

2 5

11 16 14 탐색시작

① 10 > 8

② 10 = 10

4

1단계: 삭제할 노드 탐색

자식노드 이동

2단계: 탐색한 노드 삭제

3단계: 후속처리

(38)

• 예) 노드 10을 삭제하는 경우

5. 이진 탐색 트리

(39)

• 노드 10을 삭제하는 경우에 대한 단순 연결 리스트 표현

5. 이진 탐색 트리

(40)

 자식 노드가 둘인 노드, 즉 차수가 2인 노드의 삭제 연산

• 노드를 삭제하면, 자식 노드들은 트리에서 연결이 끊어져서 고아가 된다.

• 후속 처리 : 이진 탐색 트리의 재구성

−

삭제한 노드의 자리를 자손 노드들 중에서 선택한 후계자에게 물려준다.

• 후계자 선택 방법

방법1) 왼쪽 서브트리에서 가장 큰 자손노드 선택

• 왼쪽 서브트리의 오른쪽 링크를 따라 계속 이동하여 오른쪽 링크 필드가 NULL인 노

드 즉, 가장 오른쪽에 있는 노드가 후계자가 된다.

방법2) 오른쪽 서브트리에서 가장 작은 자손노드 선택

• 오른쪽 서브트리에서 왼쪽 링크를 따라 계속 이동하여 왼쪽 링크 필드가 NULL인 노

드 즉, 가장 왼쪽에 있는 노드가 후계자가 된다.

5. 이진 탐색 트리

(41)

• 삭제한 노드의 자리를 물려받을 수 있는 후계자 노드

5. 이진 탐색 트리

(42)

• 예) 노드 8을 삭제하는 경우

5. 이진 탐색 트리

(43)

• 노드 5를 후계자로 선택한 경우

① 후계자 노드 5를 원래자리에서 삭제하여, 삭제노드 8의 자리를 물려준다.

② 후계자 노드 5의 원래자리는 자식노드 4에게 물려주어 이진 탐색 트리를 재구성 한다. (☞ 자식노드가 하나인 노드 삭제 연산의 후속처리 수행!)

• 노드 10을 후계자로 선택한 경우

① 후계자 노드 10을 원래자리에서 삭제하여, 삭제노드 8의 자리를 물려준다.

② 후계자 노드 10의 원래자리는 자식노드 14에게 물려주어 이진 탐색 트리를 재구 성한다. (☞ 자식노드가 하나인 노드 삭제 연산의 후속처리 수행!)

5. 이진 탐색 트리

(44)

• 노드 5를 후계자로 선택한 경우

5. 이진 탐색 트리

3 10

2

11 16 14 노드 삭제

4

8

5

1단계: 노드 삭제

2단계: 삭제한 노드의 자리를 후계자에게 물려주기 3단계: 후계자노드의 원래자리를 자식노드에게 물려주기

(45)

• 노드 8을 후계자로 선택한 경우

5. 이진 탐색 트리

3

2 5

11 16 14 4

노드 삭제 8

10

1단계: 노드 삭제

2단계: 삭제한 노드의 자리를 후계자에게 물려주기 3단계: 후계자노드의 원래자리를 자식노드에게 물려주기

(46)

 이진 탐색 트리에서의 삭제 연산 알고리즘

5. 이진 탐색 트리

(47)

 이진 탐색 트리에서의 삭제 연산 알고리즘

5. 이진 탐색 트리

(48)

 연결 자료구조를 이용한 이진 탐색의 C 프로그램

 이진 탐색 트리를 단순 연결 리스트로 구현하고, 탐색 연산 을 수행하는 프로그램

 실행 결과 >

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프

로그램

(49)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프 로그램

001 #include<stdio.h>

002 #include<stdlib.h>

003 004 typedef struct treeNode {

005 char key; // 데이터 필드

006 struct treeNode* left; // 왼쪽 서브 트리 링크 필드 007 struct treeNode* right; // 오른쪽 서브 트리 링크 필드 008 } treeNode;

009 010 typedef char element; // char을 이진 탐색 트리 element의 자료형으로 정의 011 012 treeNode* insertNode(treeNode *p, char x)

013 { // 포인터 p가 가리키는 노드와 비교하여 노드 x를 삽입하는 연산 014 treeNode *newNode;

015 if (p == NULL){

016 newNode = (treeNode*)malloc(sizeof(treeNode));

017 newNode->key = x;

018 newNode->left = NULL;

019 newNode->right = NULL;

020 return newNode;

021 }

022 else if (x < p->key) p->left = insertNode(p->left, x);

023 else if (x > p->key) p->right = insertNode(p->right, x);

024 else printf("\n 이미 같은 키가 있습니다! \n");

025 026 return p;

027 }

(50)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프 로그램

029 void deleteNode(treeNode *root, element key)

030 { // root 노드부터 탐색하여 key 값과 같은 노드를 찾아 삭제하는 연산 031 treeNode *parent, *p, *succ, *succ_parent;

032 treeNode *child;

033 034 parent=NULL;

035 p=root;

036 while((p != NULL) && (p->key != key)){ // 삭제할 노드의 위치 탐색 037 parent=p;

038 if(key < p->key) p=p->left;

039 else p=p->right;

040 }

041 if(p == NULL){ // 삭제할 노드가 없는 경우

042 printf("\n 찾는 키가 이진 트리에 없습니다!!");

043 return;

044 }

045 046 // 삭제할 노드가 단말 노드인 경우

047 if((p->left == NULL) && (p->right == NULL)){

048 if(parent != NULL){

049 if(parent->left == p) parent->left=NULL;

050 else parent->right=NULL;

051 }

052 else root=NULL;

053 } 054

(51)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프

055

로그램

// 삭제할 노드가 한 개의 자식 노드를 가진 경우 056 else if((p->left == NULL) || (p->right == NULL)){

057 if(p->left != NULL) child=p->left;

058 else child=p->right;

059 060 if(parent != NULL){

061 if(parent->left == p) parent->left=child;

062 else parent->right=child;

063 }

064 else root=child;

065 }

066 067 // 삭제할 노드가 두 개의 자식 노드를 가진 경우 068 else{

069 succ_parent=p;

070 succ=p->left;

071 while(succ->right != NULL){

072 succ_parent=succ;

073 succ=succ->right;

074 }

075 if(succ_parent->left == succ) succ_parent->left=succ->left;

076 else succ_parent->right=succ->left;

077 p->key=succ->key;

078 p=succ;

079 }

080 free(p);

081 } 082

(52)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프 로그램

083 treeNode* searchBST(treeNode* root, char x)

084 { // 이진 탐색 트리에서 키값이 x인 노드의 위치를 탐색하는 연산 085 treeNode* p;

086 p = root;

087 while (p != NULL){

088 if (x < p->key) p = p->left;

089 else if (x == p->key) return p;

090 else p = p->right;

091 }

092 printf("\n 찾는 키가 없습니다!");

093 return p;

094 }

095 096 void displayInorder(treeNode* root)

097 { // 이진 탐색 트리를 중위 순회하면서 출력하는 연산 098 if(root){

099 displayInorder(root->left);

100 printf("%c_", root->key);

101 displayInorder(root->right);

102 } 103 }

104 105 void menu() 106 {

107 printf("\n*---*");

108 printf("\n\t1 : 트리 출력");

109 printf("\n\t2 : 문자 삽입“);

(53)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프

110

로그램

printf("\n\t3 : 문자 삭제");

111 printf("\n\t4 : 문자 검색");

112 printf("\n\t5 : 종료");

113 printf("\n*---*");

114 printf("\n메뉴입력 >> ");

115 }

116 117 int main() 118 {

119 treeNode* root = NULL;

120 treeNode* foundedNode = NULL;

121 char choice, key;

122 123 root=insertNode(root, 'G'); // 트리 만들기 124 insertNode(root, 'I');

125 insertNode(root, 'H');

126 insertNode(root, 'D');

127 insertNode(root, 'B');

128 insertNode(root, 'M');

129 insertNode(root, 'N');

130 insertNode(root, 'A');

131 insertNode(root, 'J');

132 insertNode(root, 'E');

133 insertNode(root, 'Q');

134 135 while(1){

136 menu();

137 choice = getchar(); getchar();

(54)

5. 이진 탐색 트리 : [예제 8-3] 이진 탐색 트리 프

139

로그램

switch(choice){

140 case 1 : printf("\t[이진트리 출력] ");

141 displayInorder(root); printf("\n");

142 break;

143 144 case 2 : printf("삽입할 문자를 입력하세요 : ");

145 key = getchar(); getchar();

146 insertNode(root, key);

147 break;

148 149 case 3 : printf("삭제할 문자를 입력하세요 : ");

151 deleteNode(root, key);

152 break;

153 154 case 4 : printf("찾을 문자를 입력하세요 : ");

156 foundedNode = searchBST(root, key);

157 if (foundedNode != NULL)

158 printf("\n %c 를 찾았습니다! \n", foundedNode->key);

159 else printf("\n 문자를 찾지 못했습니다. \n");

160 break;

161 162 case 5 : return 0;

163 default : printf("없는 메뉴입니다. 메뉴를 다시 선택하세요! \n");

164 break;

165 } 166 } 167 }

(55)

 히프(heap)

 완전 이진 트리에 있는 노드 중에서 킷값이 가장 큰 노드나 킷값이

가장 작은 노드를 찾기 위해서 만든 자료구조

 최대 히프(max heap)

• 킷값이 가장 큰 노드를 찾기 위한 완전 이진 트리

• {부모노드의 킷값 ≥ 자식노드의 킷값}

• 루트 노드 : 킷값이 가장 큰 노드

 최소 히프(min heap)

• 킷값이 가장 작은 노드를 찾기 위한 완전 이진 트리

• {부모노드의 킷값 ≤ 자식노드의 킷값}

• 루트 노드 : 킷값이 가장 작은 노드

6. 히프

(56)

 히프의 예

6. 히프

(57)

 히프가 아닌 이진 트리의 예

6. 히프

(58)

 히프의 추상 자료형

6. 히프

ADT Heap

데이터 : n개의 원소로 구성된 완전 이진 트리로서 각 노드의 킷값은 그의 자식 노드의 킷값보다 크거나 같다.

(부모 노드의 킷값 ≥ 자식 노드의 킷값) 연산 :

heap∈Heap; item∈Element;

createHeap() ∷= create an empty heap;

// 공백 히프의 생성 연산

isEmpty(heap) ∷= if (heap is empty) then return true;

else return false;

// 히프가 공백인지를 검사하는 연산

insertHeap(heap, item) ∷= insert item into heap;

// 히프의 적당한 위치에 원소(item)를 삽입하는 연산 deleteHeap(heap) ∷= if (isEmpty(heap)) then return error;

else {

item ← 히프에서 가장 큰 원소;

remove {히프에서 가장 큰 원소};

return item;

}

// 히프에서 킷값이 가장 큰 원소를 삭제하고 반환하는 연산 End Heap()

(59)

 히프에서의 삽입 연산

1단계 : 완전 이진 트리를 유지하면서 확장한 노드에 삽입할 원소를 임시 저장

• 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드 가 된다.

• n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장한다.

2단계 : 만들어진 완전 이진 트리 내에서 삽입 원소의 제자 리를 찾는다.

• 현재 위치에서 부모노드와 비교하여 크기 관계를 확인한다.

• {현재 부모노드의 킷값 ≥ 삽입 원소의 킷값}의 관계가 성립하지 않으면, 현재 부모노드의 원소와 삽입 원소의 자리를 서로 바꾼다.

6. 히프

(60)

 히프에서의 삽입 연산 예1) 17을 삽입하는 경우

• 노드를 확장하여 임시로 저장한 위치에서의 부모노드와 크기를 비교하여 히프의 크기관계가 성립하므로, 현재 위치를 삽입 원소의 자리로 확정

6. 히프

(61)

 히프에서의 삽입 연산 예2) 23을 삽입하는 경우

6. 히프

(62)

 히프에서의 삽입 연산 알고리즘

6. 히프

(63)

① 현재 히프의 크기를 하나 증가시켜서 노드 위치를 확장하고, 확장한 노드 번호가 현재의 삽입 위치 i가 된다.

② 삽입할 원소 item과 부모 노드 heap[└i/2┘]를 비교하여 item이 부모 노드 보다 작거나 같으면 현재의 삽입 위치 i를 삽입 원소의 위치로 확정한다.

③ 만약 삽입할 원소 item이 부모 노드보다 크면, 부모 노드와 자식 노드의 자 리를 바꾸어 최대 히프의 관계를 만들어야 하므로 부모 노드 heap[└i/2┘]

를 현재의 삽입 위치 heap[i]에 저장하고,

④ i/2를 삽입 위치 i로 하여, ②~④를 반복하면서 item을 삽입할 위치를 찾는다.

⑤ 찾은 위치에 삽입할 노드 item을 저장하면, 최대 히프의 재구성 작업이 완성되므로 삽입 연산을 종료한다.

6. 히프

(64)

 히프에서의 삭제 연산

 히프에서는 루트 노드의 원소만을 삭제 할 수 있다.

1단계 : 루트 노드의 원소를 삭제하여 반환한다.

2단계 : 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전

이진 트리로 조정한다.

• 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 위해서 마지막 노드, 즉 n번 노드를 삭제한다.

• 삭제된 n번 노드에 있던 원소는 비어있는 루트노드에 임시 저장한다.

3단계 : 완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리를

찾는다.

6. 히프

(65)

 히프에서의 삭제 연산 예

6. 히프

(66)

 히프에서의 삭제 연산 알고리즘

6. 히프

(67)

 히프에서의 삭제 연산 알고리즘

① 루트노드 heap[1]을 변수 item에 저장하고,

② 마지막 노드의 원소 heap[n]을 변수temp에 임시 저장한 후에,

③ 마지막 노드를 삭제하고 히프배열의 원소 개수를 하나 감소한다.

④ 마지막 노드의 원소였던 temp의 임시 저장위치 i는 루트노드의 자리인 1번이 된다.

⑤ 현재 저장위치에서 왼쪽 자식 노드 heap[j]와 오른쪽 자식 노드 heap[j+1]이 있을 때, 둘 중에서 킷값이 큰 자식 노드의 킷값과 temp를 비교하여, temp 가 크거나 같으면 현재 위치가 temp의 자리로 확정된다.

⑥ 만약 temp가 자식노드보다 작으면, 자식노드와 자리를 바꾸고 다시 ⑤~

⑥을 반복하면서 temp의 자리를 찾는다.

⑦ 찾은 위치에 temp를 저장하여 최대 히프의 재구성 작업을 완성하고

⑧ 루트노드를 저장한 item을 반환하는 것으로 삭제 연산을 종료한다.

6. 히프

(68)

 순차 자료구조를 이용한 히프의 구현

 부모노드와 자식노드를 찾기 쉬운 1차원 배열의 순차 자료 구조 이용

 1차원 배열을 이용한 히프의 표현 예

6. 히프

(69)

 순차 자료구조를 이용한 히프 C 프로그램

 공백 히프에 원소 10, 45, 19, 11, 96을 차례로 삽입하면서 최대 히프를 구성하고, 삭제연산을 수행하여 삭제된 원소 를 출력하는 프로그램

• 최대 히프의 루트 노드는 히프에서 가장 큰 노드가 되므로, 원소 개수 만큼 삭제 연산을 수행하면서 출력하면 큰 값부터 작은 값의 내림차순으로 출력 되는 것을 확인할 수 있다.

 실행 결과 >

6. 히프 : [예제 8-4] 순차자료구조를 이용한 히프 프로그

램

(70)

6. 히프 : [예제 8-4] 순차자료구조를 이용한 히프 프로그 램

01 #include <stdio.h>

02 #include <stdlib.h>

03 #define MAX_ELEMENT 100

04 typedef struct { // 히프에 대한 1차원 배열과 히프 원소의 갯수를 구조체로 묶어서 선언 05 int heap[MAX_ELEMENT];

06 int heap_size;

07 } heapType;

08 09 heapType* createHeap() // 공백 히프를 생성하는 연산 10 {

11 heapType *h = (heapType *)malloc(sizeof(heapType));

12 h->heap_size=0;

13 return h;

14 }

15 16 void insertHeap(heapType *h, int item) // 히프에item을 삽입하는 연산 17 {

18 int i;

19 h->heap_size = h->heap_size +1;

20 i = h->heap_size;

21 while((i!=1) && (item > h->heap[i/2])){

22 h->heap[i] = h->heap[i/2];

23 i/=2;

24 }

25 h->heap[i] = item;

26 }

(71)

6. 히프 : [예제 8-4] 순차자료구조를 이용한 히프 프로그 램

28 int deleteHeap(heapType *h) // 히프의 루트를 삭제하여 반환하는 연산 29 {

30 int parent, child;

31 int item, temp;

32 item = h->heap[1];

33 temp = h->heap[h->heap_size];

34 h->heap_size = h->heap_size -1;

35 parent = 1;

36 child = 2;

37 while(child <= h->heap_size) {

38 if((child < h->heap_size) && (h->heap[child]) < h->heap[child+1]) 39 child++;

40 if (temp >= h->heap[child]) break;

41 else {

42 h->heap[parent] = h->heap[child];

43 parent = child;

44 child = child*2;

45 }

46 }

47 h->heap[parent] = temp;

48 return item;

49 }

50 51 printHeap(heapType *h) // 1차원 배열 히프의 내용을 출력하는 연산 52 {

53 int i;

54 printf("Heap : ");

(72)

6. 히프 : [예제 8-4] 순차자료구조를 이용한 히프 프로그 램

55 for(i=1; i<= h->heap_size; i++) 56 printf("[%d] ", h->heap[i]);

57 }

58 59 void main() 60 {

61 int i, n, item;

62 heapType *heap = createHeap();

63 insertHeap(heap, 10);

68 69 printHeap(heap);

70 71 n= heap->heap_size;

72 for(i=1; i<=n; i++){

73 item = deleteHeap(heap);

74 printf("\n delete : [%d] ", item);

75 }

76 77 getchar();

78 }

(73)

3. 트리

3. 트리

3.1 트리의 개요

3.2 이진 트리

3.3 트리의 운행

3.1 트리의 개요

트리 : 그래프의 일종 데이터 : 노드

순환적 정의

T = {R, T 1 ,T 2 ,…T n } R : 루트

T i : 서브-트리(트리)

1. 노드 2. 근 노드 3. 서브트리 4. 차수

5. 단 노드

6. 간 노드(nonterminal node) 7. 부-노드, 자-노드

8. Family tree : 조상, 자손 9. 레벨

10. 높이 11. 숲

3.1 트리의 개요

3.1트리의 개요

 3.1.4 트리의 종류

Ordered tree

Oriented tree

Binary tree

Skewed tree

3.2 이진 트리

여러가지 응용에 가장 넓이 사용 엄밀한 이진 트리

크누스 이진 트리

3.2.2 이진 트리와 관련된 정리

정리 1 : 이진 트리의 레렐 i에 있는 노드의 최대 개수는 2 i-1 이다.

정리 2 : 깊이가 k인 이진 트리에 있는 노드의 전체 개수는 최대 2 k -1 이다.

3.2 이진 트리

정리 4 : n개의 노드를 가진 전이진 트리, 즉 깊이가 log n + 1 인 트리가 1차원 배열에 저장되면 다음과 같은 관계가 성립된다.

(1) parent[i]는 i!=1일 때 i/2의 위치에 있게 된다.

(2) Leftchild[i]는 2i<=n일 때 2i의 위치에 있게 된다.

(3) rightchild[i]는 2i+1<=n 일 때 2i+1의 위치에 있게 된다.

3.2 이진 트리

3.3 트리의 운행

 트리의 운행(Traversal)

각 노드를 중복되지 않게 한번씩 방문하여 트리를 검색하는 방법

 트리의 운행 방법

Level order Traveral

Preorder Traversal

Inorder Traversal

Postorder Traversal

 7.3.2 이진 트리의 운행

L : 왼쪽으로의 이동

R : 오른쪽으로의 이동

D : 자료의 출력

Preorder Traversal----DLR

Inorder Traversal----LDR

Postorder Traversal----LRD

3.3 트리의 운행

 전위 운행

public static void preOrder(BinaryTreeNode t) {

if(t!=null) {

visit(t);

preOrder(t.leftChild);

preOrder(t.rightChild);

} }

출력: / - * A ** B C Log D E

3.3 트리의 운행

/ -

A **

B C

D

*

E

log

 중위 운행

public static void inOrder(BinaryTreeNode t) {

if(t!=null) {

inOrder(t.leftChild);

visit(t);

inOrder(t.rightChild);

} }

출력: A * B ** C - log D / E

7.3 트리의 운행

/ -

A **

B C

D

*

T = {R, T ₁ ,T ₂ ,…T _n } R : 루트

T _i : 서브-트리(트리)

정리 1 : 이진 트리의 레렐 i에 있는 노드의 최대 개수는 2 ^i-1 이다.

정리 2 : 깊이가 k인 이진 트리에 있는 노드의 전체 개수는 최대 2 ^k -1 이다.