자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1
8 장트리 소프트웨어학과원성현교수 93
1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy) 을갖는비선형자료구조 (nonlinear data structure) 임 트리란한개이상의노드로이루어진유한집합 트리구조의예 회사의조직구조 컴퓨터내폴더혹은디렉토리구조 의사결정트리구조 B C D 소프트웨어학과원성현교수 94
트리의주요용어 노드 (node) : 트리를구성하는요소하나하나 ( 예 :, B ) 루트 (root) : 트리의시작이되는노드 ( 예 : ) 간선 (edge) : 노드와노드의연결 부모 (parent) : 자신과직접연결된상위노드 자식 (children) : 자신과직접연결된하위노드 형제 (sibling) : 동일한부모를갖는노드들 B C D E F G H I J 소프트웨어학과원성현교수 95
조상 (ancestor) : 임의의노드에서루트까지이르는경로상의모든노드 후손 (descendent) : 임의의노드하위의모든노드 단말 (terminal, leaf) : 자식을갖지않는노드 비단말 (non terminal) : 자식을갖는노드 서브트리 (sub tree) : 특정노드아래구성된트리 차수 (degree) : 임의의노드가갖는자식노드의수 레벨 (level) : 루트를레벨 1 로하고그자식노드는 +1 높이 (height) : 트리가갖는최대레벨 숲 (forest) : 루트를제거했을때생기는서브트리 트리의표현 배열을이용한표현 표현하기용이하나크기가고정되어있어서변화하는트리를적절하게표현하기어려움 연결리스트를이용한표현 표현하기어려우나크기가가변적이어서변화하는트리를적절하게표현하기용이함 소프트웨어학과원성현교수 96
2. 이진트리 이진트리의개요 일반트리 (general tree) 각노드가가질수있는자식의개수가제한되지않은트리 모든노드의차수가다르기때문에배열로든링키드리스트든구현하기어려움 이진트리 (binary tree : BT) 각노드가가질수있는자식의개수가 2 개이하로제한된트리 모든노드의최대차수가 2 로동일하기때문에구현하기매우용이함 모든노드는링크필드를 2 개갖는링키드리스트로구현할수있음 LC data RC 소프트웨어학과원성현교수 97
추상자료형이진트리 이진트리의정의 공집합이거나모든노드의차수가 2 이하이며자식노드는왼쪽자식과오른쪽자식으로명확히구분될수있어야함 이진트리의서브트리도모두이진트리여야함 left subtree right subtree 소프트웨어학과원성현교수 98
이진트리의성질 n 개의노드를가진이진트리는 n-1 개의간선을가짐 모든노드는오직 1 개의부모만갖고부모와자식간에는정확히 1 개의간선만존재하기때문 높이가 h 인이진트리는최소 h 개의노드를갖고최대 2 h -1 개의노드를가짐 n 개의노드를갖는이진트리의높이는최대 n 이거나최소 log 2 (n+1) 이됨 B B C C 최소 D E F G 최대 소프트웨어학과원성현교수 99
이진트리의분류 포화이진트리 (full binary tree) 각레벨에모든노드가꽉차있는트리 완전이진트리 (complete binary tree) 마지막레벨에서왼쪽부터노드가꽉차있는트리 편향이진트리 (skewed binary tree) 이진트리를구성하는모든노드가한쪽자식만갖는트리 B C B C B D E F G D E F C 포화이진트리 완전이진트리 편향이진트리 소프트웨어학과원성현교수 100
3. 이진트리의구현 순차자료구조를이용한이진트리구현 배열표현법 1 2 3 B C 4 5 6 D E F [0] [1] [2] [3] [4] [5] [6] [7] [8] B C D E F B 1 2 3 [0] [1] [2] [3] [4] [5] [6] [7] [8] B C D 8 4 5 6 C 7 D 소프트웨어학과원성현교수 101
연결자료구조를이용한이진트리구현 링크표현법 B C B C D E F NULL D NULL NULL E NULL NULL E NULL typedef struct treenode { char data; struct treenode *left struct treenode *right; } treenode; 소프트웨어학과원성현교수 102
4. 이진트리의순회 이진트리의순회 이진트리의순회 (traversal) 란? 이진트리를구성하는모든노드를오직한번만방문하는연산 이진트리의순회법 V L R 전위순회 (preorder traversal) : VLR 중위순회 (inorder traversal) : LVR 후위순회 (postorder traversal) : LRV 소프트웨어학과원성현교수 103
전위순회 루트를먼저방문하고, 루트의왼쪽서브트리, 오른쪽서브트리의순서로방문 V 1 L 2 3 R left subtree preorder(t) if (T NULL) then { visit T.data; preorder(t.left); preorder(t.right); } end preorder() right subtree 소프트웨어학과원성현교수 104
중위순회 루트의왼쪽서브트리를먼저방문하고, 루트, 오른쪽서브트리의순서로방문 V 2 L 1 3 R left subtree inorder(t) if (T NULL) then { inorder(t.left); visit T.data; inorder(t.right); } end inorder() right subtree 소프트웨어학과원성현교수 105
후위순회 루트의왼쪽서브트리, 오른쪽서브트리를방문한후마지막으로루트의순서로방문 V 3 L 1 2 R left subtree postorder(t) if (T NULL) then { postorder(t.left); postorder(t.right); visit T.data; } end postorder() right subtree 소프트웨어학과원성현교수 106
이진트리에서의순회방법을응용한프로그램 연산식에대한순회 + * E * D / B C <Inorder> /B*C*D+E <Preorder> +**/BCDE <Postorder> B/C*D*E+ 소프트웨어학과원성현교수 107
전위순회와중위순회결과를아는상태에서의이진트리구성 전위순회의결과가 B C D E F G H I 이고, 중위순회의결과가 B C E D G H F I 인이진트리를가정 이두순회결과를통해유일한본래의이진트리를구성할수있을까? B,C D,E,F,G,H,I B D,E,F,G,H,I C 소프트웨어학과원성현교수 108
B D B D C E F,G,H,I C E F G,H I B D C E F G I H 소프트웨어학과원성현교수 109
스레드이진트리 (threaded binary tree) 이진트리의링크의문제점 n 개의노드로구성된이진트리는총 2n 개의링크를갖고있는데그중 n-1 개만실제노드를가리키고나머지 n+1 개의링크는 NULL 임 B C D 0 E 0 0 F 0 0 G 0 0 H 0 0 I 0 소프트웨어학과원성현교수 110
스레드이진트리란모든링크에게임무를부여 원래가리킬노드가있는링크와원래는가리킬노드가없었는데새로이임무를부여받은링크로구분 새로운임무란자신의이전노드와이후노드를가리키는것 B C D E F G H I 소프트웨어학과원성현교수 111
스레드이진트리의노드구조 f : FLSE, t : TRUE root f - f f f f B f f C f f D f t E t t F t t G t t H t t I t 소프트웨어학과원성현교수 112
5. 이진탐색트리 이진트리의순회 이진탐색트리 (Binary Search Tree : BST) 란? 다음과같은조건을만족하는이진트리 모든원소의키 (key) 는유일하다. 왼쪽서브트리의키들은루트의키보다작다. 오른쪽서브트리의키들은루트의키보다크다. 왼쪽과오른쪽서브트리도이진탐색트리이다. < < left subtree( 루트보다작은값 ) right subtree( 루트보다큰값 ) 소프트웨어학과원성현교수 113
이진탐색트리의예 18 7 26 3 12 31 27 이진탐색트리의중위순회예 3 7 12 18 26 27 31 소프트웨어학과원성현교수 114
이진탐색트리의탐색연산 이진탐색트리에서의탐색 루트와제일먼저비교 탐색값과루트가일치하면탐색종료 탐색값이루트보다작으면왼쪽서브트리로이동하여왼쪽서브트리의루트와다시비교 탐색값이루트보다크면오른쪽서브트리로이동하여오른쪽서브트리의루트와다시비교 교재 386 쪽알고리즘 8-4 참조 소프트웨어학과원성현교수 115
이진탐색트리의삽입연산 30 5 40 2 80 삽입 교재 387 쪽알고리즘 8-5 참조 30 5 40 2 80 소프트웨어학과원성현교수 116
이진탐색트리의삭제연산 단말노드를삭제하는경우 30 30 5 40 5 40 2 80 2 한쪽자식만갖고있는노드를삭제하는경우 30 30 5 40 2 40 2 80 80 소프트웨어학과원성현교수 117
양쪽자식모두를갖고있는노드를삭제하는경우 30 35 5 40 5 40 2 35 80 2 80 or 2 5 40 35 80 소프트웨어학과원성현교수 118
6. 힙 힙의개요 힙의개념 최대힙 (Max Heap) 루트의하위노드들은루트보다값이작거나같은이진트리 최소힙 (Min Heap) 루트의하위노드들은루트보다값이크거나같은이진트리 9 1 7 6 4 2 5 4 3 2 7 5 3 3 2 1 3 7 8 9 소프트웨어학과원성현교수 119
힙의구현 배열을이용하는경우, 루트부터왼쪽자식, 오른쪽자식의순서로배열에저장 1 왼쪽자식 : 부모의인덱스 *2 오른쪽자식 : 부모의인덱스 * 2 + 1 9 부모의인덱스 = 자식의인덱스 /2 2 3 5 7 4 5 6 7 8 9 1 0 2 1 3 6 4 3 2 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 9 7 6 5 4 3 2 2 1 3 소프트웨어학과원성현교수 120
힙에서의삽입연산 힙에서의삽입절차 가장마지막에새로운노드 (8) 를삽입 부모노드 (4) 와비교하여삽입노드 (8) 의값이더크므로교환 9 1 9 1 2 3 7 6 4 5 6 7 5 4 3 2 2 3 7 6 4 5 6 7 5 8 3 2 8 9 10 11 8 9 10 11 2 1 3 8 2 1 3 4 소프트웨어학과원성현교수 121
부모노드 (7) 와비교하여삽입노드 (8) 가더크므로교환 부모노드 (9) 와비교하여삽입노드 (8) 가더이상크지않으므로교환종료 5 7 3 2 9 2 3 8 6 4 5 6 7 8 9 10 11 2 1 3 4 1 insertheap(heap,item) if(n=heapsize) then heapfull(); n=n+1; for(i=n; ;) do { if(i=1) then exit; if(item <= heap[ i/2 ]) then exit; heap[i]=heap[ i/2 ]; i= i/2 } heap[i]=item; end insertheap() 힙에서의삽입알고리즘 소프트웨어학과원성현교수 122
힙에서의삭제연산 힙에서의삭제절차 힙에서삭제는최대값을가진노드즉루트 (9) 부터삭제 루트를삭제하면트리가깨지므로히프의마지막노드 (3) 를루트의위치로이동하여트리를유지 9 1 3 1 7 6 5 4 3 2 2 1 3 2 3 4 5 6 7 8 9 10 7 6 5 4 3 2 2 1 2 3 4 5 6 7 8 9 소프트웨어학과원성현교수 123
그러나, 임시로루트가된노드 (3) 는자식노드보다값이작으므로자식노드중값이더큰노드 (7) 와교환 그래도자식노드보다값이작으므로자식노드중값이더큰노드 (5) 와교환 더이상은자식노드보다값이작지않으므로교환종료 7 1 7 1 3 6 5 4 3 2 2 1 2 3 4 5 6 7 8 9 5 6 3 4 3 2 2 1 2 3 4 5 6 7 8 9 소프트웨어학과원성현교수 124
힙에서의삭제알고리즘 deleteheap(heap) if(n=0) then return error; item=heap[1]; temp=heap[n]; n=n-1; i=1; j=2; while(j<=n) do { if(j<n) then if(heap[j]<heap[j+1]) then j=j+1; if(temp>=heap[j]) then exit; heap[i]=heap[j]; i=j; j=j*2; } heap[i]=temp; return item; end deleteheap() 소프트웨어학과원성현교수 125
힙의응용 힙정렬 Input List : 26 5 77 1 61 11 59 15 48 19 [1] 26 [1] 77 5 77 [2] [3] 61 59 [2] [3] [4] [5] [6] [7] 1 61 [8] [9] [10] 15 48 19 Input rray 11 59 [4] [5] [6] [7] 48 19 [9] [10] 15 1 5 Initial Heap 11 26 소프트웨어학과원성현교수 126
[1] 61 [1] 59 48 59 [2] [3] [4] [5] [8] [9] 15 19 [6] 11 26 5 1 Heap Size = 9 Sorted = [77] [7] 48 26 [2] [3] [4] [5] [8] 15 19 [6] 11 1 5 Heap Size = 8 Sorted = [61,77] [7] [1] 48 [1] 26 19 26 [2] [3] [4] [5] [6] [7] 15 5 11 1 Heap Size = 7 Sorted = [59,61,77] 19 11 [2] [3] [4] [5] [6] 15 5 1 Heap Size = 6 Sorted = [48,59,61,77] 소프트웨어학과원성현교수 127
[1] 19 [1] 15 15 11 [2] [3] 5 11 [2] [3] [4] [5] 1 5 Heap Size = 5 [4] 1 Heap Size = 4 Sorted = [26,48,59,61,77] Sorted = [19,26,48,59,61,77] [1] 11 [1] 5 [1] 1 5 1 Heap Size = 3 [2] [3] Sorted = [15,19,26,48,59,61,77] [2] 1 Heap Size = 2 Sorted = [5,11,15,19,26,48,59,61,77] Heap Size = 1 Sorted = [1,5,11,15,19,26,48,59,61,77] 소프트웨어학과원성현교수 128
허프만코딩 (Huffman Coding) 허프만코딩이란? 데이터를표현할때 SCII 와같이고정된길이의비트수를문자에할당하지않고가변길이로할당, 즉자주등장하는문자에게는짧은비트수만을할당하고, 자주등장하지않는문자에게는긴비트수를할당하여식별 허프만코딩의예 e : 15, t : 12, n : 8, i : 6, s : 4 라는빈도를갖는다면총 45 글자이므로이들문자에게각각 8 비트를할당한다면 360 비트가필요하지만 e : 2 비트, t : 2 비트, n : 2 비트, i : 3 비트, s : 3 비트를할당하면 88 비트만으로도충분히표한가능 각문자에게허프만코드를할당하는방법 각문자의빈도수를데이터르갖는이진트리를구성하고이를통해힙을구성. 구성된히프를통해코드를할당 소프트웨어학과원성현교수 129
힙을이용한허프만코딩과정 가장작은값을갖는두노드를합한값으로부모를생성 4 6 8 12 15 10 4 6 8 12 15 45 18 10 27 4 6 8 12 15 소프트웨어학과원성현교수 130
왼쪽간선은 1 로, 오른쪽간선은 0 으로할당 1 45 0 1 18 10 1 0 27 0 1 0 4 6 8 12 15 빈도 4(s) : 111 3 비트할당빈도 6(i) : 110 3 비트할당빈도 8(n) : 10 2 비트할당빈도 12(t) : 01 2 비트할당빈도 15(e) : 00 2 비트할당 소프트웨어학과원성현교수 131