트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )
Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104
1. 트리 트리 (tree) 원소들간에 1: 多관계를가지는비선형자료구조 원소들간에계층관계를가지는계층형자료구조 상위원소에서하위원소로내려가면서확장되는트리 ( 나무 ) 모양의구조 하나의줄기에서가지로뻗어나가면서 확장되는구조 하나의그루터기에서뿌리로뻗어나가면서 확장되는구조 3/104
1. 트리 트리자료구조의예 가계도 가계도의자료 : 가족구성원 자료를연결하는선 : 부모 - 자식관계표현 4/104
1. 트리 철수의자식 성호, 영주, 진호 성호, 영주, 진호의부모 철수 같은부모의자식들끼리는형제관계 성호, 영주, 진호는형제관계 조상 현재위치에서연결된선을따라올라가면서만나는사람들 수영의조상 : 승완, 성호, 철수 자손 - 현재위치에서연결된선을따라내려가면서만나는사람들 성호의자손 : 승우, 승완, 수영, 수철 선을따라내려가면서다음세대로확장 가족구성원누구든지자기의가족을데리고분가하여독립된가계를이룰수있다. 5/104
1. 트리 트리 A 6/104
1. 트리 트리 A 노드 (node) 트리의원소 트리 A 의노드 - A,B,C,D,E,F,G,H,I,J,K,L 루트노드 (root node) 트리의시작노드 트리 A 의루트노드 - A 간선 (edge) 노드를연결하는선. 부모노드와자식노드를연결 형제노드 (sibling node) 같은부모노드의자식노드들 B,C,D 는형제노드 조상노드 간선을따라루트노드까지이르는경로에있는모든노드들 K 의조상노드 : F, B, A 서브트리 (subtree) 부노노드와연결된간선을끊었을때생성되는트리 각노드는자식노드의개수만큼서브트리를가진다. 자손노드 서브트리에있는하위레벨의노드들 B 의자손노드 E,F,K,L 7/104
1. 트리 트리 A 차수 (degree) 노드의차수 : 노드에연결된자식노드의수. A 의차수 =3, B 의차수 =2, C 의차수 =1 트리의차수 : 트리에있는노드의차수중에서가장큰값 트리 A 의차수 =3 단말노드 ( 리프노드 ) : 차수가 0 인노드. 자식노드가없는노드 높이 노드의높이 : 루트에서노드에이르는간선의수. 노드의레벨 B 의높이 =1, F 의높이 =2 트리의높이 : 트리에있는노드의높이중에서가장큰값. 최대레벨 트리 A 의높이 =3 8/104
1. 트리 포리스트 (forest) : 서브트리의집합 트리 A 에서노드 A 를제거하면, A 의자식노드 B, C, D 에대한서브트리가생기고, 이들의집합은포리스트가된다. A 루트루트루트 B C D E F G H I J K L 트리 1 트리 2 트리 3 9/104
2. 이진트리 이진트리 트리의노드구조를일정하게정의하여트리의구현과연산이쉽도록정의한트리 이진트리의모든노드는왼쪽자식노드와오른쪽자식노드만을가진다. 부모노드와자식노드수와의관계 1:2 공백노드도자식노드로취급한다. 0 노드의차수 2 10/104
2. 이진트리 이진트리는순환적구성 노드의왼쪽자식노드를루트로하는왼쪽서브트리도이진트리 노드의오른쪽자식노드를루트로하는오른쪽서브트리도이진트리 루트 A 의왼쪽서브트리 루트 B A A 의오른쪽서브트리 루트 C B 의왼쪽서브트리 B 의오른쪽서브트리 C 의왼쪽서브트리 C 의오른쪽서브트리 D E F G H I J K L 11/104
2. 이진트리 추상자료형이진트리 ADT BinaryTree 데이터 : 공백이거나루트노드, 왼쪽서브트리, 오른쪽서브트리로구성된노드들의유한집합연산 : bt, bt1, bt2 BinaryTree; item Element; createbt() = create an empty binary tree; // 공백이진트리를생성하는연산 isempty(bt) = if (bt is empty) then return true else return false; // 이진트리가공백인지아닌지를확인하는연산 makebt(bt1, item, bt2) = return {item 을루트로하고 bt1 을왼쪽서브트리, bt2 를오른쪽서브트리로하는이진트리 } // 두개의이진서브트리를연결하여하나의이진트리를만드는연산 leftsubtree(bt) = if (isempty(bt)) then return null else return left subtree of bt; // 이진트리의왼쪽서브트리를구하는연산 rightsubtree(bt) = if (isempty(bt)) then return null else return right subtree of bt; // 이진트리의오른쪽서브트리를구하는연산 data(bt) = if (isempty(bt)) then return null else return the item in the root node of bt; // 이진트리에서루트노드의데이터 (item) 를구하는연산 End BinaryTree 12/104
2. 이진트리 이진트리의특성 정의 1) n 개의노드를가진이진트리는항상 (n-1) 개의간선을가진다. 루트를제외한 (n-1) 개의노드가부모노드와연결되는한개의간선을가짐 정의 2) 높이가 h 인이진트리가가질수있는노드의최소개수는 (h+1) 개가되며, 최대개수는 (2 h+1-1) 개가된다. 이진트리의높이가 h 가되려면한레벨에최소한한개의노드가있어야하므로 높이가 h 인이진트리의최소노드의개수는 (h+1) 개 하나의노드는최대 2 개의자식노드를가질수있으므로레벨 i 에서의노드의 최대개수는 2 i 개이므로높이가 h 인이진트리전체의노드개수는 2 i = 2 h+1-1 개 13/104
2. 이진트리 이진트리의특성 높이가 3 이면서최소의노드를갖는이진트리와최대의노드를갖는이진트리 14/104
2. 이진트리 이진트리의종류 포화이진트리 (Full Binary Tree) 모든레벨에노드가포화상태로차있는이진트리 높이가 h 일때, 최대의노드개수인 (2 h+1-1) 의노드를가진이진트리 루트를 1 번으로하여 2 h+1-1 까지정해진위치에대한노드번호를가짐 15/104
2. 이진트리 완전이진트리 (Complete Binary Tree) 높이가 h 이고노드수가 n 개일때 ( 단, h+1 n < 2 h+1-1 ), 포화이진트리의노드번호 1 번부터 n 번까지빈자리가없는이진트리 예 ) 노드가 12 개인완전이진트리 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 10 J 11 K 12 L 13 14 15 16/104
2. 이진트리 편향이진트리 (Skewed Binary Tree) 높이 h 에대한최소개수의노드를가지면서한쪽방향의자식노드만을가진이진트리 왼쪽편향이진트리 모든노드가왼쪽자식노드만을가진편향이진트리 오른쪽편향이진트리 모든노드가오른쪽자식노드만을가진편향이진트리 17/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 순차자료구조를이용한이진트리의구현 1 차원배열의순차자료구조사용 높이가 h 인포화이진트리의노드번호를배열의인덱스로사용 인덱스 0 번 : 실제로사용하지않고비워둠. 인덱스 1 번 : 루트저장 18/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 완전이진트리의 1 차원배열표현 1 A 2 3 B C 4 5 6 7 D E F G 8 9 10 11 12 H I J K L [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] A B C D E F G H I J K L 19/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 왼쪽편향이진트리의 1 차원배열표현 20/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 이진트리의 1 차원배열에서의인덱스관계 [0] 1 A [1] [2] A B 부모노드의인덱스 = 2 2 B 3 C [3] [4] [5] C D E 4 5 6 7 D E F G 8 9 10 11 12 H I J K L [6] [7] [8] [9] [10] F G H I J 왼쪽자식노드의인덱스 = 10 [11] [12] K L 오른쪽자식노드의인덱스 = 11 21/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 이진트리의순차자료구조표현의단점 편향이진트리의경우에사용하지않는배열원소에대한메모리공간낭비발생 트리의원소삽입 / 삭제에대한배열의크기변경어려움 22/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 연결자료구조를이용한이진트리의구현 단순연결리스트를사용하여구현 이진트리의모든노드는최대 2 개의자식노드를가지므로일정한구조의 단순연결리스트노드를사용하여구현 이진트리의노드구조에대한 C 구조체정의 typedef struct treenode { char data; struct treenode *left; struct treenode *right; } treenode; 23/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 완전이진트리의단순연결리스트표현 24/104
3. 이진트리구현 : 순차자료구조를이용한이진트리구현 왼쪽편향이진트리의단순연결리스트표현 25/104
4. 이진트리의순회 이진트리의순회 (traversal) 계층적구조로저장되어있는트리의모든노드를방문하여데이터를처리하는연산 순회를위해수행할수있는작업정의 ⑴ 현재노드를방문하여데이터를읽는작업 D ⑵ 현재노드의왼쪽서브트리로이동하는작업 L ⑶ 현재노드의오른쪽서브트리로이동하는작업 R 현재노드 노드의데이터읽기 : 작업 D 왼쪽서브트리로이동하기 : 작업 L 오른쪽서브트리로이동하기 : 작업 R 26/104
4. 이진트리의순회 이진트리가순환적으로정의되어구성되어있으므로, 순회작업도서브트리에대해서순환적으로반복하여완성한다. 왼쪽서브트리에대한순회를오른쪽서브트리보다먼저수행한다. 순회의종류 전위순회 중위순회 후위순회 27/104
4. 이진트리의순회 전위순회 (preorder traversal) 수행방법 1 현재노드 n을방문하여처리한다. : D 2 현재노드 n의왼쪽서브트리로이동한다. : L 3 현재노드 n의오른쪽서브트리로이동한다. : R 전위순회알고리즘 28/104
4. 이진트리의순회 전위순회의예 29/104
4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 30/104
4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 31/104
4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K 32/104
4. 이진트리의순회 전위순회과정 >> A-B-D-H-E-I-J-C-F-G-K A B C D E F G H I J K 33/104
4. 이진트리의순회 수식이진트리에대한전위순회 수식을이진트리로구성한수식이진트리를전위순회하면, 수식에대한전위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의전위순회경로 >> -*AB/CD 34/104
4. 이진트리의순회 중위순회 (inorder traversal) 수행방법 1 현재노드 n의왼쪽서브트리로이동한다. : L 2 현재노드 n을방문하여처리한다. : D 3 현재노드 n의오른쪽서브트리로이동한다. : R 중위순회알고리즘 35/104
4. 이진트리의순회 중위순회의예 36/104
4. 이진트리의순회 중위순회과정 >> H-D-B-I-E-J-A-F-C-G-K A B C D E F G H I J K 37/104
4. 이진트리의순회 38/104
4. 이진트리의순회 39/104
4. 이진트리의순회 40/104
4. 이진트리의순회 수식이진트리에대한중위순회 수식이진트리를중위순회하면, 수식에대한중위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의중위순회경로 >> A*B-C/D 41/104
4. 이진트리의순회 후위순회 (postorder traversal) 수행방법 1 현재노드 n의왼쪽서브트리로이동한다. : L 2 현재노드 n의오른쪽서브트리로이동한다. : R 3 현재노드 n을방문하여처리한다. : D 후위순회알고리즘 42/104
4. 이진트리의순회 후위순회의예 43/104
4. 이진트리의순회 후위순회과정 >> H-D-I-J-E-B-F-K-G-C-A A B C D E F G H I J K 44/104
4. 이진트리의순회 45/104
4. 이진트리의순회 46/104
4. 이진트리의순회 47/104
4. 이진트리의순회 수식이진트리에대한후위순회 수식이진트리를후위순회하면, 수식에대한후위표기식을구할수있다. [ 그림 8-15] 의수식이진트리의후위순회경로 >> AB*CD/- 48/104
4. 이진트리의순회 : [ 예제 8-1] 연결자료구조로구현한이진트리에서의순회 C 프로그램 수식 (A*B-C/D) 에대한수식이진트리를단순연결리스트로구현 전위순회, 중위순회, 후위순회를차례로수행하면서순회경로를출력하는프로그램 실행결과 > 49/104
4. 이진트리의순회 : [ 예제 8-1] 01 #include <stdio.h> 02 #include <stdlib.h> 03 #include <memory.h> 04 05 typedef struct treenode{ // 연결자료구조로구성하기위해트리의노드정의 06 char data; 07 struct treenode *left; // 왼쪽서브트리에대한링크필드 08 struct treenode *right; // 오른쪽서브트리에대한링크필드 09 } treenode; 10 11 treenode* makerootnode(char data, treenode* leftnode, treenode* rightnode) 12 { //data 를루트노드로하여왼쪽서브트리와오른쪽서브트리를연결하는연산 13 treenode* root = (treenode *)malloc(sizeof(treenode)); 14 root->data = data; 15 root->left = leftnode; 16 root->right = rightnode; 17 return root; 18 } 19 20 void preorder(treenode* root) // 이진트리에대한전위순회연산 21 { 22 if(root){ 23 printf("%c", root->data); 24 preorder(root->left); 25 preorder(root->right); 26 } 27 } 50/104
4. 이진트리의순회 : [ 예제 8-1] 28 29 void inorder(treenode* root) // 이진트리에대한중위순회연산 30 { 31 if(root){ 32 inorder(root->left); 33 printf("%c", root->data); 34 inorder(root->right); 35 } 36 } 37 38 void postorder(treenode* root) // 이진트리에대한후위순회연산 39 { 40 if(root){ 41 postorder(root->left); 42 postorder(root->right); 43 printf("%c", root->data); 44 } 45 } 46 51/104
4. 이진트리의순회 : [ 예제 8-1] 47 void main() 48 { 49 treenode* n7 = makerootnode('d', NULL, NULL); 50 treenode* n6 = makerootnode('c', NULL, NULL); 51 treenode* n5 = makerootnode('b', NULL, NULL); 52 treenode* n4 = makerootnode('a', NULL, NULL); 53 treenode* n3 = makerootnode('/', n6, n7); 54 treenode* n2 = makerootnode('*', n4, n5); 55 treenode* n1 = makerootnode('-', n2, n3); 56 57 printf("\n preorder : "); 58 preorder(n1); 59 60 printf("\n inorder : "); 61 inorder(n1); 62 63 printf("\n postorder : "); 64 postorder(n1); 65 66 getchar(); 67 } 52/104
4. 이진트리의순회 : [ 예제 8-2] 폴더계산 C 프로그램 컴퓨터의폴더구조가이진트리구조인경우에이진트리순회를응용하여폴더의용량을계산하는프로그램 폴더의이진트리구조 53/104
4. 이진트리의순회 : [ 예제 8-2] 하위폴더의용량을계산하여상위폴더의용량과더해서전체용량을계산해야하므로후위순회를이용 프로그램폴더의전체용량 = 프로그램폴더 (2M) + 하위폴더의용량 {C 프로그램폴더 (200M) + Java 프로그램폴더 (100M)} = 302M C:\ 의전체용량 = C:\ 의용량 (0M) + 하위폴더의용량 { 프로그램폴더의전체용량 (302M) + 자료폴더 (15M)} = 317M 그림폴더의전체용량 = 그림폴더 (68M) + 하위폴더의용량 { 사진폴더 (55M) + 동영상폴더 (120M)} = 243M D:\ 의전체용량 = D:\ 의용량 (10M) + 하위폴더의용량 { 음악폴더의용량 (40M) + 그림폴더의전체용량 (243M)} = 293M 내컴퓨터의전체용량 = 내컴퓨터의용량 (0M) + 하위폴더의용량 {C:\ 폴더의전체용량 (317M) + D:\ 폴더의전체용량 (293M)} = 610M 54/104
4. 이진트리의순회 : [ 예제 8-2] 01 #include <stdio.h> 02 #include <stdlib.h> 03 #include <memory.h> 04 05 typedef struct treenode{ // 트리의노드구조정의 06 int size; // 데이터필드 07 struct treenode *left; // 왼쪽서브트리에대한링크필드 08 struct treenode *right; // 오른쪽서브트리에대한링크필드 09 } treenode; 10 11 int FolderSize=0; 12 // size 를루트노드의데이터필드로하여왼쪽서브트리와오른쪽서브트리를 // 연결하는연산 13 treenode* makerootnode(int size, treenode* leftnode,treenode* rightnode) 14 { 15 treenode* root = (treenode *)malloc(sizeof(treenode)); 16 root->size = size; 17 root->left = leftnode; 18 root->right = rightnode; 19 return root; 20 } 55/104
4. 이진트리의순회 : [ 예제 8-2] 21 // 각폴더의크기계산을위한후위순회연산 22 int postorder_foldersize(treenode* root) 23 { 24 if(root){ 25 postorder_foldersize(root->left); 26 postorder_foldersize(root->right); 27 FolderSize += root ->size; 28 } 29 return FolderSize; 30 } 31 56/104
4. 이진트리의순회 : [ 예제 8-2] 32 void main() 33 { 34 treenode* F11 = makerootnode(120, NULL, NULL); 35 treenode* F10 = makerootnode(55, NULL, NULL); 36 treenode* F9 = makerootnode(100, NULL, NULL); 37 treenode* F8 = makerootnode(200, NULL, NULL); 38 treenode* F7 = makerootnode(68, F10, F11); 39 treenode* F6 = makerootnode(40, NULL, NULL); 40 treenode* F5 = makerootnode(15, NULL, NULL); 41 treenode* F4 = makerootnode(2, F8, F9); 42 treenode* F3 = makerootnode(10, F6, F7); 43 treenode* F2 = makerootnode(0, F4, F5); 44 treenode* F1 = makerootnode(0, F2, F3); 45 46 printf("\n C:\\ 의용량 : %d M \n", postorder_foldersize(f2)); 47 48 FolderSize=0; 49 printf("\n D:\\ 의용량 : %d M \n", postorder_foldersize(f3)); 50 51 FolderSize=0; 52 printf("\n 내컴퓨터의전체용량 : %d M \n", postorder_foldersize(f1)); 53 54 getchar(); 55 } 57/104
4. 이진트리의순회 : [ 예제 8-2] 실행결과 > 58/104
5. 이진탐색트리 이진탐색트리 (binary search tree) 이진트리에탐색을위한조건을추가하여정의한자료구조 이진탐색트리의정의 ⑴ 모든원소는서로다른유일한키를갖는다. ⑵ 왼쪽서브트리에있는원소의키들은그루트의키보다작다. ⑶ 오른쪽서브트리에있는원소의키들은그루트의키보다크다. ⑷ 왼쪽서브트리와오른쪽서브트리도이진탐색트리다. 59/104
5. 이진탐색트리 이진탐색트리의탐색연산 루트에서시작한다. 탐색할킷값 x를루트노드의킷값과비교한다. ( 킷값 x = 루트노드의킷값 ) 인경우 : 원하는원소를찾았으므로탐색연산성공 ( 킷값 x < 루트노드의킷값 ) 인경우 : 루트노드의왼쪽서브트리에대해서탐색연산수행 ( 킷값 x > 루트노드의킷값 ) 인경우 : 루트노드의오른쪽서브트리에대해서탐색연산수행 서브트리에대해서순환적으로탐색연산을반복한다. 60/104
5. 이진탐색트리 탐색연산알고리즘 61/104
5. 이진탐색트리 탐색연산예 ) 원소 11 탐색하기 1 찾는킷값 11 을루트노드의킷값 8 과비교 ( 찾는킷값 11 > 노드의킷값 8) 이므로오른쪽서브트리를탐색 2 ( 찾는킷값 11 > 노드의킷값 10) 이므로, 다시오른쪽서브트리를탐색 3 ( 찾는킷값 11 < 노드의킷값 14) 이므로, 왼쪽서브트리를탐색 4 ( 찾는킷값 11 = 노드의킷값 11) 이므로, 탐색성공! ( 연산종료 ) 62/104
5. 이진탐색트리 이진탐색트리의삽입연산 1) 먼저탐색연산을수행 삽입할원소와같은원소가트리에있으면삽입할수없으므로, 같은원소가트리에있는지탐색하여확인한다. 탐색에서탐색실패가결정되는위치가삽입위치가된다. 2) 탐색실패한위치에원소를삽입한다. 63/104
5. 이진탐색트리 이진탐색트리에서의 삽입할자리탐색 삽입할노드만들기 탐색한자리에노드연결 64/104
5. 이진탐색트리 이진탐색트리에서의삽입연산예 ) 원소 4 삽입하기 1 찾는킷값 4 를루트노드의킷값 8 과비교하여, ( 찾는킷값 4 < 노드의킷값 8) 이므로, 왼쪽서브트리를탐색한다. 2 ( 찾는킷값 4 > 노드의킷값 3) 이므로, 오른쪽서브트리를탐색한다. 3 ( 찾는킷값 4 < 노드의킷값 5) 이므로, 왼쪽서브트리를탐색해야하는데왼쪽자식노드가없으므로탐색실패! 이때, 탐색실패가결정된위치즉, 왼쪽자식노드의위치가삽입위치가된다. 4 탐색작업으로찾은자리즉, 노드 5 의왼쪽자식노드자리에노드 4 를삽입한다. 65/104
5. 이진탐색트리 단순연결리스트로표현한이진트리에서의원소 4 삽입하기 q q 탐색실패! q 66/104
5. 이진탐색트리 이진탐색트리의삭제연산 1) 먼저탐색연산을수행 삭제할노드의위치를알아야하므로트리를탐색한다. 2) 탐색하여찾은노드를삭제한다. 노드의삭제후에도이진탐색트리를유지해야하므로삭제노드의경우에대한후속처리 ( 이진탐색트리의재구성작업 ) 가필요하다. 삭제할노드의경우 삭제할노드가단말노드인경우 : 차수가 0 인경우 삭제할노드가하나의자식노드를가진경우 : 차수가 1 인경우 삭제할노드가두개의자식노드를가진경우 : 차수가 2 인경우 67/104
5. 이진탐색트리 단말노드의삭제연산 노드 4 를삭제하는경우 68/104
5. 이진탐색트리 노드 4 를삭제하는경우에대한단순연결리스트표현 노드를삭제하고, 삭제한노드의부모노드의링크필드에 null 설정 69/104
5. 이진탐색트리 자식노드가하나인노드, 즉차수가 1 인노드의삭제연산 노드를삭제하면, 자식노드는트리에서연결이끊어져서고아가된다. 후속처리 : 이진탐색트리의재구성 삭제한부모노드의자리를자식노드에게물려준다. 예 ) 노드 10 을삭제하는경우 탐색시작 8 1 10 > 8 3 10 2 5 2 10 = 10 자식노드이동 14 1 단계 : 삭제할노드탐색 2 단계 : 탐색한노드삭제 3 단계 : 후속처리 4 11 16 70/104
5. 이진탐색트리 예 ) 노드 10 을삭제하는경우 71/104
5. 이진탐색트리 노드 10 을삭제하는경우에대한단순연결리스트표현 72/104
5. 이진탐색트리 자식노드가둘인노드, 즉차수가 2 인노드의삭제연산 노드를삭제하면, 자식노드들은트리에서연결이끊어져서고아가된다. 후속처리 : 이진탐색트리의재구성 삭제한노드의자리를자손노드들중에서선택한후계자에게물려준다. 후계자선택방법방법 1) 왼쪽서브트리에서가장큰자손노드선택 왼쪽서브트리의오른쪽링크를따라계속이동하여오른쪽링크필드가 NULL 인노 드즉, 가장오른쪽에있는노드가후계자가된다. 방법 2) 오른쪽서브트리에서가장작은자손노드선택 오른쪽서브트리에서왼쪽링크를따라계속이동하여왼쪽링크필드가 NULL 인노 드즉, 가장왼쪽에있는노드가후계자가된다. 73/104
5. 이진탐색트리 삭제한노드의자리를물려받을수있는후계자노드 74/104
5. 이진탐색트리 예 ) 노드 8 을삭제하는경우 75/104
5. 이진탐색트리 노드 5 를후계자로선택한경우 1 후계자노드 5 를원래자리에서삭제하여, 삭제노드 8 의자리를물려준다. 2 후계자노드 5 의원래자리는자식노드 4 에게물려주어이진탐색트리를재구성한다. ( 자식노드가하나인노드삭제연산의후속처리수행!) 노드 10 을후계자로선택한경우 1 후계자노드 10 을원래자리에서삭제하여, 삭제노드 8 의자리를물려준다. 2 후계자노드 10 의원래자리는자식노드 14 에게물려주어이진탐색트리를재구성한다. ( 자식노드가하나인노드삭제연산의후속처리수행!) 76/104
5. 이진탐색트리 노드 5 를후계자로선택한경우 1 단계 : 노드삭제 노드삭제 8 2 단계 : 삭제한노드의자리를후계자에게물려주기 3 단계 : 후계자노드의원래자리를자식노드에게물려주기 3 10 2 5 14 4 11 16 77/104
5. 이진탐색트리 노드 8 을후계자로선택한경우 1 단계 : 노드삭제 노드삭제 8 2 단계 : 삭제한노드의자리를후계자에게물려주기 3 단계 : 후계자노드의원래자리를자식노드에게물려주기 3 10 2 5 14 4 11 16 78/104
5. 이진탐색트리 이진탐색트리에서의삭제연산알고리즘 79/104
5. 이진탐색트리 이진탐색트리에서의삭제연산알고리즘 80/104
5. 이진탐색트리 : [ 예제 8-3] 이진탐색트리프로그램 연결자료구조를이용한이진탐색의 C 프로그램 이진탐색트리를단순연결리스트로구현하고, 탐색연산을수행하는프로그램 실행결과 > 81/104
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 } 82/104
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 83/104
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 84/104
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 : 문자삽입 ); 85/104
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(); 86/104
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(" 삭제할문자를입력하세요 : "); 150 key = getchar(); getchar(); 151 deletenode(root, key); 152 break; 153 154 case 4 : printf(" 찾을문자를입력하세요 : "); 155 key = getchar(); getchar(); 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 } 87/104
6. 히프 히프 (heap) 완전이진트리에있는노드중에서킷값이가장큰노드나킷값이가장작은노드를찾기위해서만든자료구조 최대히프 (max heap) 킷값이가장큰노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 } 루트노드 : 킷값이가장큰노드 최소히프 (min heap) 킷값이가장작은노드를찾기위한완전이진트리 { 부모노드의킷값 자식노드의킷값 } 루트노드 : 킷값이가장작은노드 88/104
6. 히프 히프의예 89/104
6. 히프 히프가아닌이진트리의예 90/104
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() 91/104
6. 히프 히프에서의삽입연산 1 단계 : 완전이진트리를유지하면서확장한노드에삽입할원소를임시저장 노드가 n 개인완전이진트리에서다음노드의확장자리는 n+1 번의노드가된다. n+1 번자리에노드를확장하고, 그자리에삽입할원소를임시저장한다. 2 단계 : 만들어진완전이진트리내에서삽입원소의제자리를찾는다. 현재위치에서부모노드와비교하여크기관계를확인한다. { 현재부모노드의킷값 삽입원소의킷값 } 의관계가성립하지않으면, 현재부모노드의원소와삽입원소의자리를서로바꾼다. 92/104
6. 히프 히프에서의삽입연산예 1) 17 을삽입하는경우 노드를확장하여임시로저장한위치에서의부모노드와크기를비교하여히프의크기관계가성립하므로, 현재위치를삽입원소의자리로확정 93/104
6. 히프 히프에서의삽입연산예 2) 23 을삽입하는경우 94/104
6. 히프 히프에서의삽입연산알고리즘 95/104
6. 히프 1 현재히프의크기를하나증가시켜서노드위치를확장하고, 확장한노드번호가현재의삽입위치 i 가된다. 2 삽입할원소 item 과부모노드 heap[ i/2 ] 를비교하여 item 이부모노드보다작거나같으면현재의삽입위치 i 를삽입원소의위치로확정한다. 3 만약삽입할원소 item 이부모노드보다크면, 부모노드와자식노드의자리를바꾸어최대히프의관계를만들어야하므로부모노드 heap[ i/2 ] 를현재의삽입위치 heap[i] 에저장하고, 4 i/2 를삽입위치 i 로하여, 2~4 를반복하면서 item 을삽입할위치를찾는다. 5 찾은위치에삽입할노드 item 을저장하면, 최대히프의재구성작업이완성되므로삽입연산을종료한다. 96/104
6. 히프 히프에서의삭제연산 히프에서는루트노드의원소만을삭제할수있다. 1단계 : 루트노드의원소를삭제하여반환한다. 2 단계 : 원소의개수가 n-1 개로줄었으므로, 노드의수가 n-1 인완전이진트리로조정한다. 노드가 n 개인완전이진트리에서노드수 n-1 개의완전이진트리가되기위해서마지막노드, 즉 n 번노드를삭제한다. 삭제된 n 번노드에있던원소는비어있는루트노드에임시저장한다. 3 단계 : 완전이진트리내에서루트에임시저장된원소의제자리를 찾는다. 현재위치에서자식노드와비교하여크기관계를확인한다. { 임시저장원소의킷값 현재자식노드의킷값 } 의관계가성립하지않으면, 현재자식노드의원소와임시저장원소의자리를서로바꾼다. 97/104
6. 히프 히프에서의삭제연산예 98/104
6. 히프 히프에서의삭제연산알고리즘 99/104
6. 히프 히프에서의삭제연산알고리즘 1 루트노드 heap[1] 을변수 item 에저장하고, 2 마지막노드의원소 heap[n] 을변수 temp 에임시저장한후에, 3 마지막노드를삭제하고히프배열의원소개수를하나감소한다. 4 마지막노드의원소였던 temp 의임시저장위치 i 는루트노드의자리인 1 번이된다. 5 현재저장위치에서왼쪽자식노드 heap[j] 와오른쪽자식노드 heap[j+1] 이있을때, 둘중에서킷값이큰자식노드의킷값과 temp 를비교하여, temp 가크거나같으면현재위치가 temp 의자리로확정된다. 6 만약 temp 가자식노드보다작으면, 자식노드와자리를바꾸고다시 5~ 6 을반복하면서 temp 의자리를찾는다. 7 찾은위치에 temp 를저장하여최대히프의재구성작업을완성하고 8 루트노드를저장한 item 을반환하는것으로삭제연산을종료한다. 100/104
6. 히프 순차자료구조를이용한히프의구현 부모노드와자식노드를찾기쉬운 1 차원배열의순차자료구조이용 1 차원배열을이용한히프의표현예 101/104
6. 히프 : [ 예제 8-4] 순차자료구조를이용한히프프로그램 순차자료구조를이용한히프 C 프로그램 공백히프에원소 10, 45, 19, 11, 96 을차례로삽입하면서최대히프를구성하고, 삭제연산을수행하여삭제된원소를출력하는프로그램 최대히프의루트노드는히프에서가장큰노드가되므로, 원소개수만큼 삭제연산을수행하면서출력하면큰값부터작은값의내림차순으로출력 되는것을확인할수있다. 실행결과 > 102/104
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 } 103/104
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 : "); 104/104
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); 64 insertheap(heap, 45); 65 insertheap(heap, 19); 66 insertheap(heap, 11); 67 insertheap(heap, 96); 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 } 105/104
IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )