5.3 Binary Tree Traversal Tree 의각 node 를한번씩방문하는알고리즘 각 node 와그 node 의 subtree 들을동등하게취급하면 6 개의 traversal 조합이있다. (L: Left 로움직임, V: 노드를 visiting, R: Right 로움직임 ) (1) LVR, (2) LRV, (3) VLR, (4) VRL, (5) RVL, (6) RLV Traverse left before right 를도입하면, 3 개의조합이남는다. (1) LVR (in-order traversal) (2) LRV (post-order traversal) (3) VLR (pre-order traversal) 3 개의 tree traversal 과 expression 의 (1) infix, (2) postfix, (3) prefix form 간에상호관련이있음. 23
In-order Traversals: 왼쪽 branch 를모두방문한후, node 를방문하고, 오른쪽 branch 를방문함 주어진식 : 16 + A / B * C * D + E (infix form) 12 * 18 E 번호는아래알고리즘의수행순서이므로방문순서임 8 * 14 17 19 D void inorder(tree_ptr ptr) { 4 / 10 13 15 if(ptr) { C inorder(ptr->left_child); printf( %d,ptr->data); 2 A 6 B 9 11 inorder(ptr->right_child); 1 3 5 7 inorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : A/B*C*D+E - 주어진 infix form 과동일 24
Pre-order Traversals: node 를방문하고, 왼쪽 branch 를모두방문한후, 오른쪽 branch 를방문함 주어진식 : 1 + A / B * C * D + E (infix form) 2 * 17 E 번호는아래알고리즘의수행순서이므로방문순서임 3 * 14 18 19 D void preorder(tree_ptr ptr) { 4 / 11 15 16 if(ptr) { C printf( %d,ptr->data); preorder(ptr->left_child); 5 A 8 12 13 preorder(ptr->right_child); B 6 7 9 10 preorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : +**/ABCDE 25
Post-order Traversals: 왼쪽 branch 를모두방문한후, 오른쪽 branch 를방문한후, node 를방문함 주어진식 : 19 + A / B * C * D + E (infix form) 15 * 18 E 번호는아래알고리즘의수행순서이므로방문순서임 11 * 14 16 17 D void postorder(tree_ptr ptr) { 7 if(ptr) { 12 13 / 10 C preorder(ptr->left_child); 3 A 6 B preorder(ptr->right_child); 8 9 printf( %d,ptr->data); 1 2 4 5 postorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : AB/C*D*E+ 26
Iterative In-order Traversal Recursive version의 system stack을모방하기위해 stack에대한삽입, 삭제연산을수행 void iter_inorder(tree-pointer node) { int top = -1; // 스택초기화 tree_ptr stack[max_stack_size]; while (1) { while (node) { push(&top, node); // 스택에넣음 node = node->left_child; node = pop(&top); if (!node) break; printf( %d, node->data); node = node->right_child; // 스택에서꺼냄 // 빈스택임 < 분석 > Tree 에있는모든 node 가 stack 에 add 되었다가 delete 된다. delete 될때만처리되므로, tree 의 node 수가 n 이라면 time complexity 는 O(n) 이다. space requirement 는 tree 의 depth 와같으므로평균, O(log n), 최악의경우 O(n) 이다. < 유사응용 > Factorial, Fibonacci 숫자, 트리순회, 이진탐색, 하노이타워, quick sort, 등등 27
Level Order Traversal 아래그림의 sequential node number 에근거한항해방법으로서 queue 를이용한다. 4 2 1 5 6 8 9 10 11 12 13 14 15 순회결과 : 123456789 15 Figure 5.8 의경우 : +*E*D/CAB 3 7 void level_order(tree_ptr ptr) { int front = rear = 0; tree_ptr queue[max_queue_size]; if (!ptr) return; addq(front,&rear,ptr); while (1) { ptr = deleteq(&front, rear); if (ptr) { printf( %d, ptr->data); if (ptr->left_child) addq(front,&rear,ptr- >left_child); if (ptr->right_child) addq(front,&rear,ptr- >right_child); else break; 28
( 참고 ) 5.4 이진트리의추가연산 (1) Copying Binary Trees (Program 5.6: post-order 항해법을약간변형함 ) tree_ptr copy(tree_ptr original) { tree_ptr temp; if (original) { temp = (tree_ptr)malloc(sizeof(node)); if (IS_FULL(temp)) exit(1); temp->left_child = copy(original->left_child); temp->right_child = copy(original->right_child); temp->data = original->data; return temp; return NULL; 29
( 참고 ) 5.4 이진트리의추가연산 (2) Testing for Equality of Binary Trees 2 개의 binary tree 가 같은구조 와 같은정보 를담고있는지를확인한다. 다음 program 5.7 은 pre-order traversal 에대한약간의변형이다. int equal(tree_ptr first,tree_ptr second) { return ( (!first &&!second) (first && second && (first->data == second->data) && equal (first->left_child, second->left_child) && equal (first->right_child, second->right_child ) ); 30
5.5 Threaded Binary Trees Thread : Needless Null link 대신, tree 의다른노드를가리키는용도로사용 A.J. Perlis 와 C. Thorntorn 에의해제안된방법이다. 왜 Thread 를사용하는가? Binary tree 에서 2n 개의 link 들중, leaf 의 n+1 개의 link 가 null link 를이용함 node 당 2 개의 link 가있고, 사용되는 link 의수가, n-1 이므로, null link 는 n+1 개 (1) null link 가너무많다 null link 를다른좋은일에사용할수없을까? 공간이아까우니, 이공간을활용하자. (2) 임의단말노드의바로앞노드 (previous node) 와뒷노드 (successor node) 순서를알기힘들기때문에 thread 를이용하자. Thread 구성규칙 1. 한 node 의 left-child 가 null 이면, 그값이 in-order traversal 에의해현 node 바로전에방문되는 node 를가리킨다. ( 현 node 의 in-order predecessor 를가리킴 ) 2. 한 node 의 right-child 가 null 이면그값이 in-order traversal 에의해현 node 바로뒤에방문되는 node 를가리킨다. ( 현 node 의 in-order successor 를가리킴 ) 31
A B C D E F G H I Figure 5.9 Threaded tree corresponding to Figure 5.6 (b) - In-order traversal: H, D, I, B, E, A, F, C, G - E 의 left child 가 null 이므로 E 의 left child 가 predecessor B 를가리킴 - E 의 right child 가 null 이므로 E 의 right child 가 successor A 를가리킴 32
실제포인터와스레드를어떻게구분하나? thread 와 normal pointer 를구분하기위해다음두개의 field 를추가함 : (1) left_thread, (2) right_thread (ß 실제로는, 각기한 bit 면된다 ) 예제 : if ( ptr->left_thread = TRUE ) ptr->left_child 는 thread 이다. if ( ptr->left_thread = FALSE ) ptr->left_child 는 left child node 에대한 ptr. right_thread 도동일 dangling reference 방지를위해모든 threaded binary tree 는 head node (dummy root) 를유지한다. 따라서 empty threaded binary tree 도하나의 node 를가진다. Figure 5.10 과같이 root->left_child 는실제 tree 의첫 node 를가리킨다. 33
Figure 5.10 (a) empty threaded tree typedef struct threaded_tree * threaded_ptr; typedef struct threaded_tree { short int left_thread; threaded_ptr left_child; char data; threaded_ptr right_child; short int right_thread; ; left_thread left_child data right_child right_thread 34
Figure 5.10 (b) Memory representation of the threaded tree root f -- f f A 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 f: FALSE t: TRUE 35
In-order Traversal of a Threaded Binary Tree 일반적으로이미방문했던노드 (already visited node) 이지만, 다음에사용해야하는 node 를 keeping 하는방법으로 stack 을이용한다. 그러나, stack 을사용하지않고도 threaded tree 의 thread 를이용하여 inorder traversal 수행하여다음노드를알수있다. ptr 노드의 in-order 순뒷노드를찾아보자. 만약 ptr->right_thread=true 면, ptr->right_child ( 다음을위해서, 따라간다 ) 그렇지않으면 (ptr->right_thread=false 면 ), 우측노드 (right node) 의좌측노드 (left_thread 에 TRUE 가나타날때까지 ) 를계속따라간다. void tinorder (threaded_ptr tree) { threaded_ptr temp = tree; for (;;) { temp = insucc (temp); if (temp = tree) break; printf( %3c, temp->data); threaded_ptr insucc (threaded_ptr tree) { threaded_ptr temp; temp = tree à right_child; if (!tree à right_thread) /* 오른쪽 FALSE */ while (!temp à left_thread) /* 왼쪽 FALSE */ temp = temp->left_child; return temp; - Insucc () 를계속호출하면됨 임의노드의 inorder - 시간복잡도 : O(n), n은노드수 successor를찾는루틴 36
Threaded binary tree 에노드삽입 오른쪽 subtree 가없는 parent 에서오른쪽에 child 를만들어보자. 1) parent->right_thread를 FALSE로만듦 2) child->left_thread, child->right_thread를 TRUE로만듦 3) child->left_child가 parent를가리키게한다. 4) child->right_child가 parent->right_child 값을가짐 5) parent->right_child가 child를가리킴 parent 가 right child 를가지고있으면, 그 child 는 parent 의 inorder successor 노드가된다. 당연히, 역으로 parent 는그 child 의 in-order predecessor 가된다. 37
Figure 5.10 부모노드에새로운노드를오른쪽자식으로삽입하는알고리즘 void insert_right(threaded_ptr parent, threaded_ptr child) { threaded_ptr temp; child->right_child=parent->right_child; child->right_thread=parent->right_thread; child->left_child=parent; child->left_thread=true; parent->right_child=child; parent->right_thread=false; if(!child->right_thread) { temp=insucc(child); temp->left_child=child; 38
삽입예 : Threaded Binary Trees root root A A parent B parent B C D child C D child 삽입전 삽입후 : 붉은선 Young-Ho Park
삽입예 : Threaded Binary Trees root root A parent A parent B B child C D C X E F D child X E F before After: 붉은선 Young-Ho Park
The Heap Abstract Data Type 5.6 Heaps Definition: max tree 는 node 에있는 key value 가그 children 의 key value 들보다크거나같다. max heap 은 complete binary tree 이면서동시에 max tree 이다. Max Heap 예제들 :: [1] 14 [1] 9 [1] 30 [2] [3] 12 7 [2] [3] 6 3 [2] 25 [4] [5] [6] 10 8 6 [4] 5 41
The Heap Abstract Data Type ( 계속 ) Definition: min tree 는 node 에있는 key value 가그 children 의 key value 들보다작거나같다. main heap 은 complete binary tree 이면서동시에 main tree 이다. Min Heap 예제들 :: [1] 2 [1] 10 [1] 11 [2] [3] 7 4 [2] [3] 20 83 [2] 21 [4] [5] [6] 10 8 6 [4] 50 heap 은 array 로표현할수있고, 이경우 Lemma 5.3 에근거한 addressing scheme 을사용할수있다. 42
Abstract data type MaxHeap structure MaxHeap is object: 각노드에있는값이그자식들의값보다큰노드들로구성된 0 이상의 element 들을가진 complete binary tree functions: for all heap MaxHeap, item Element, n, max_size integer MaxHeap Create (max_size) ::= 최대크기의 element들의최대값을가지고있는 빈 heap을만든다. Boolean HeapFull (heap,n) ::= if (n==max_size) return TRUE else return FALSE Maxheap Insert (heap, item, n) ::= if (!HeapFull (heap,n)) insert item into heap and return the resulting heap else return error Boolean HeapEmpty (heap,n) ::= if (n>0) return FALSE else return TRUE Maxheap Delete (heap, n) ::= if (!HeapEmpty(heap,n)) 힙에서가장큰것을반환한다. 그리고, 그것을힙에서제거한다. else return error 43
5.6.2 Priority Queues heap 은 priority queue 의구현에적합하다. priority queue 에대한연산은? 가장높은 priority 를가진 element 를삭제하고, 임의의 priority 를가진 element 를삽입하는연산이대부분이다. OS 의 job scheduling 시 priority queue 를이용한다. priority queue 를구현하는여러가지방법들 :: 표현방법삽입삭제 순서없는배열 Q (1) Q (n) 순서없는연결리스트 Q (1) Q (n) 정렬된배열 O(n) Q (1) 정렬된연결리스트 O(n) Q (1) 최대힙 O(log 2 n) O(log 2 n) 44
priority queue 를구현하는여러가지방법들 ( 보완 ) 1. array 간단함 insertion : array 끝에추가 O(1) deletion : 가장큰값을검색후 element를삭제하고 O(n) array elements를 shift함 O(n) 2. un-ordered linked list insertion : chain 끝에추가 O(1) deletion : 가장큰값을검색후한 element를삭제 O(n) 3. ordered array insertion : 해당위치검색후 O(n) array element shift O(n) deletion : 정해진위치의 element을삭제 O(1) 4. linked list (non-increasing order) insertion : 해당위치검색후삽입 O(n) deletion : link의 header element을삭제 O(1) 5. heap insertion : O(log₂n) deletion : O(log₂n) 45
5.6.3 Insertion into a Max Heap 넣는노드위치 (complete tree 구성순서 ) 로부터 parent 로계속올라간다. 링크표현 : 각노드구조에는 parent 를가리키는 field 가있어야한다. 배열표현 : 힙은 complete binary tree 이므로, Lemma 5.3 에서소개한바와같이, 간단한주소방법인 배열 을사용하는것이적합하다. [1] 20 [1] 20 [1] 20 [1] 21 [2] [3] 15 [4] [5] 14 10 2 [2] [3] 15 [4] [5] [6] 14 10 2 [2] [3] 15 [4] [5] [6] 14 10 2 5 [2] 15 [3] 20 [4] [5] [6] 14 10 2 (a) 삽입전힙 (b) 새노드의초기위치 (c) 힙 (a) 에 5 삽입 (d) 힙 (a) 에 21 을삽입 46
5.6.3 Insertion into a Max Heap ( 계속, Program 5.11) heap 이 complete binary tree 이므로 array representation 이용 Lemma 5.3 을이용하면노드별배열매핑주소 (location) 를파악할수있다. Lemma 5.3 을이용하기위해 array 의 index 를 0 이아닌 1 부터사용 알고리즘 :: 삽입될노드의위치를지정함 : 가장밑에가장오른쪽단말노드 새로운키값을넣는다. parent 를통해계속루트방향으로올라가면서키값들을조정한다. : i/2 시간복잡도 : O( 트리의깊이 ) O(log 2 n) void insert_max_heap(element item, int *n) { int i; if (HEAP_FULL(*n)) { fprintf(stderr, The heap is full. \n ); exit(1); i = ++(*n); while ((i!=1 )&& (item.key > heap[i/2].key)) { heap[i] = heap[i/2]; i /= 2; heap[i] = item; 47
5.6.4 Deletion from a Max Heap 항상, 힙의루트에서자료를제거하면된다. 자료제거후, 완전이진트리가되도록트리를재조정한다. 가장마지막에있는노드를루트에놓고, 루트로부터그자식노드들을비교하면서힙의정의에맞도록노드들을조정하면서트리를아래방향으로 scanning 한다. 시간복잡도 : O( 트리깊이 ) à O(log2n) 48
Heaps [1] 20 [1] 20 removed [2] [3] 15 2 [2] [3] 15 2 [4] [5] 14 10 [4] [5] 14 10 (a) 힙구조 [1] 10 [1] 15 [2] [3] 15 2 [2] [3] 14 2 [4] 14 [4] 10 (b) 루트에 10 을넣기 (c) 최종힙구조 Young-Ho Park
element delete_max_heap (int *n) { element item, temp; if (HEAP_EMPTY(*n)) { fprintf(stderr, 힙 is empty\n ); exit(1); item = heap[1]; temp = heap[(*n)--]; parent = 1; child = 2; while (child <= *n) { /* 왼쪽과오른쪽자식의키값을비교 */ if ((child < *n) && (heap[child].key < heap[child+1].key)) child++; if (temp.key >= heap[child].key) break; /* move to the next lower level */ heap[parent] = heap[child]; parent = child; child *= 2; heap[parent] = temp; return item; Analysis heap 을따라내려가면서 parent 와 child node 를비교하면서 heap 을재정립 heap 의높이가 log 2 (n+1) 이므로 complexity 는 O(log 2 n) 이다. 50
5.7 Binary Search Trees Definition: Binary Search Tree 는탐색에목적을둔 binary tree 이다. 본 tree 는 empty 일수있고, empty 가아닌경우다음의성질을만족한다. 1. 모든 element 는서로다른 key 를갖는다. 2. Non-empty left subtree 에있는 key 들은 root 의 key 보다작은값을갖는다. 3. Non-empty right subtree 에있는 key 들은 root 의 key 보다큰값을갖는다. 4. left subtree 와 right subtree 도역시 binary search tree 이다. 20 30 60 15 25 5 40 70 12 10 22 2 65 80 (a) 이진탐색트리가아님 (b) 이진탐색트리 Figure 5.12: Binary Trees (c) 이진탐색트리 51
5.7.2 Binary Search Tree(BST) 의탐색법 BST 의순환적탐색법 ( 재귀호출방법 ) tree_ptr search (tree_ptr root, int key) { /* return a pointer to the node that contains key. If there is no such node, return NULL */ if (!root) return NULL; if (key == root àdata) return root; if (key < root àdata) return search (root àleft_child, key); return search (root àright_child, key); BST의반복적탐색법 tree_ptr iter_search (tree_ptr tree, int key) { while (tree) { if (key == tree à data) return tree; if (key < tree àdata) tree = treeàleft_child; else tree = treeàright_child; return NULL; Analysis ( 이때, h 는 BST 의높이 ) search iter_search 탐색시간측면의비용분석 O(h) O(h) 사용된스택공간측면의비용분석 O(h) None 52
5.7.3 Binary Search Tree 에노드삽입하는방법 unique key 를지원하므로 insert 연산시, search 연산이선행되어야함 해당 key 를찾지못한경우, 검색이끝난지점에서새로운 element 를삽입함 30 80 35 30 30 5 40 5 40 5 40 2 2 80 2 35 80 (a) 초기상태 (b) 80 삽입 (c) 35 삽입 80 의 insert 과정 : tree 에서 80 을검색하고, 검색이성공적이지못하고검색이끝난곳은 key 40 인 node 이다. 이 node 의오른쪽 child 로서새로운 key 를 insert 한다. 53
삽입프로그램 : 5.15: modified_search modified_search 함수 : tree 가비어있거나 (empty) 이거나검색 search key 가이미 tree node 에존재하는경우에는, NULL 을 return 한다. 그렇지않으면 search 중만나는마지막 node 에대한 pointer 를 return 한다 ( 그곳에넣으면된다 ). void insert_node (tree_ptr *node, int num) { tree_ptr ptr, temp = modified_search (*node, num); <BST 에한노드를삽입하기 > if (temp!(*node)) { ptr = (tree_ptr) malloc (sizeof(node)); if (IS_FULL (ptr)) { fprintf (stderr, The momory is full\n ); exit (1); ptràdata = num; ptràleft_child = ptràright_child = NULL; if (*node) { if (num < tempàdata) tempàleft_child = ptr; else tempàright_child = ptr; else *node = ptr; 삽입 key 에대한 search time 이 O(h) 이고, 이외의알고리즘은 O(1) 이다. 따라서, 총시간은 O(h) 이다. 54
5.7.4 Binary Search Tree 에서노드를삭제하는방법 leaf node 인경우, 해당 node 를지우고그 parent 의 link 를 NULL 로만든다. 하나의 child 를가진 non-leaf node 를 delete 하는경우, 해당 node 를지우고, child node 가지워진 node 를대체한다. 두개의 children 을가진 non-leaf node 를 delete 하는경우, leaf sub-tree 의가장큰 element 나 right sub-tree 의가장작은 element 를삭제하고자하는 node 와대체한다. 30 35 삭제 30 40 삭제 30 5 40 5 40 5 80 2 35 80 2 80 2 (a) 노드가삭제될 BST (b) delete 35 ( 단말노드삭제경우 ) (c) delete 40 ( 하나의자식노드를가지는노드제거 ) 55
2 개의자식노드 (50, 70) 를가지는노드 (60) 를제거하는방법 40 40 20 60 20 55 10 30 50 70 10 30 50 70 45 55 45 52 52 (a) 60 을제거하기전트리 (b) 60 을제거한후의트리 (a) 의 tree 에대하여 60 을 55 과 70, 둘중하나와대체할수있다. (b) 는 55 로대체한경우이다. (skewed tree 를피하기위함 ) 56
5.7.5 Height of a binary search tree Worst case key 를 1,2,3,., n 의순으로삽입하면, binary search tree 의 height 가 n 이된다. 일반적인경우 binary search tree 의 height 는평균 O(log 2 n) 이다. Balanced search tree worst case height로써 O(log 2 n) 를가지는 search tree 이다. search, insertion, deletion이 O(h) 에수행된다. 종류 : AVL tree, 2-3 tree, red-black tree 등 57
5.8 Selection Trees k 개의 ordered sequence 를하나의 ordered sequence 로 merge 하는문제 k 개의 run 으로부터첫번째 record 들을비교하여최소의 key 를찾는다. 용어 run : 각 ordered sequence 를부르는이름이며, 몇개의 record 로구성되고, key field 에따라 non-decreasing order 로정렬되어있다. n : k 개의 run 에속해있는총 record 의수 직접비교방식을사용하면최소값을하나찾기위해 k-1 번의비교를수행한다. Selection tree 를이용하면보다효율적으로최소값을찾을수있다. Definition : selection tree selection tree 는 binary tree 이고각 node 는자신의 children 중작은쪽의값을갖는다. 따라서 root 는최소값을갖는다. 58
Run, k = 8 인 selection tree 가있을때, 8 개의 run 들각각에첫번 3 개의 key 를보여주는그림 1 6 가장작은값 6, 출력예정! 2 3 6 8 4 5 6 7 9 6 8 17 8 9 10 11 12 13 14 15 10 9 20 6 8 9 90 17 15 16 20 38 20 30 15 25 15 50 11 16 100 110 18 20 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 59
하나의레코드가출력되고, 트리가재구축된후의 selection tree 그림 (nodes that were changed are ticked) : node that is changed 1 8 6 이출력된이후, 트리변경! 2 3 9 8 4 5 6 7 9 15 8 17 8 9 10 11 12 13 14 15 10 9 20 15 8 9 90 17 15 16 20 38 20 30 25 15 50 11 16 100 110 18 20 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 60
Analysis 트리를재구축하는시간은 O(log 2 k) 이다. K: Run 의개수 n 개의 record 들을모두 merge 하는시간은 O(n log 2 k) 이다. 그 selection tree 를초기구성 (set up) 하기위한시간은 the first time is O(k) 총시간 : O(n log 2 k) 61
A tree 62
( 참고 ) 5.9 Forests ( 숲, 나무들의집합 ) 63
정의 Definition: forest 는 n 개 (n 0) 의 disjoint tree 의집합이다. Binary tree 의 root 를제거하면, 두개의 tree 로이루어진 forest 가생성된다. Transforming a Forest Into Binary Tree Forest 를하나의 binary tree 로변환하기위해서는다음을수행하여야한다. forest 에있는 tree 를위한 binary tree representation 을획득한다. binary tree 들은 root node 의 sibling field 를이용하여연결한다. Definition: T₁,,Tn 의 tree 로구성된 forest 에대한 binary tree 는 B(T₁,,Tn) 이고다음을만족한다. n=0 인경우 B(T₁,,Tn) 는 empty 이다. B(T₁,,Tn) 의 root 는 root(t1) 의 root 와같고 left subtree 는 B(T11,T12,T1m) 로구성되며 right subtree 는 B(T2,,Tn) 로구성된다. 단, B(T11,T12,T1m) 는 root(t1) 의 sub tree 이다. 64
? A E G B C D F H I A E G B C D F H I 3 개의 tree 를가지는 forest 가되었다. 65
forest 를이진트리로변환하기 1. forest 내각트리를이진트리 ( 왼쪽자식 - 오른쪽형제형식 ) 로변환한다. 2. 루트노드의 sibling 으로모든이진트리를묶는다. A E G B C D F H I 66
정의 ) 만약 T 1,,T n 이트리들의 forest 라면, 이 forest 에해당하는이진트리는 B(T 1,,T n ) 으로표현된다. n = 0 이면, empty root (T 1 ) 을 root 로가진다 왼쪽 B(T 11,T 12,,T 1m ) sub-tree 를가짐 : T 11,T 12,,T 1m 는 root(t 1 ) 의 sub-tree 오른쪽 sub-tree 는 B(T 2,, T n ) 이다. A B E C F G D H I 67
Forest 순회 Forest 역시, 전위순회 (pre-order traversal), 중위순회 (in-order traversal), 후위순회 (post-order traversal) 가있다. 전위순회 (pre-order traversal) 와중위순회 (in-order traversal) 는이전에배운트리항해법과동일하다. 다음은전위순회방법만을보인다. 만약 F 가 empty 면, return F 의첫번째 tree 의 root 를방문 첫트리의 sub-tree 들을 tree 전위 (pre-order) 로순회 F 의남은 tree 들을전위 (pre-order) 순서로방문 후위순회 (post-order traversal) 는이전에배운것과다르다. ( 다른점파악할것!) 만약 F 가 empty 면, return F 의첫번째 tree 의 sub-tree 를 tree 후위로순회 나머지 tree 를 tree 후위로순회 F 의첫번째 tree 의 root 를방문 68
( 참고 ) 5.10 Set 표현 트리로집합을표현하자. 가정 - 집합의요소들은 0, 1, 2,, n-1 숫자. - 모든집합들은서로분리 (disjoint) 관계 예 ) 10 개의 0 부터 9 까지의숫자들을세개의집합으로나눠보자. S 1 ={0,6,7,8, S 2 ={1,4,9, S 3 ={2,3,5 - 자식에서부모로링크를두자. Young-Ho Park
Set 표현 0 6 7 8 S1 4 2 1 9 3 5 S2 S3 집합의포리스트표현 Young-Ho Park
Set 표현 분리합집합 (disjoint set union) 만약 S i 와 S j 가두개의분리집합일때, 이들의합집합 S i È S j = { 모든요소 x such that x is in S i or S j find(i): 원소 i 를포함하는집합을찾는다. Young-Ho Park
Set 표현 union and find 연산 union 연산 루트들중하나의루트가나머지루트를가리키게만든다. 각집합의이름을다루기위해, 그집합을나타내는루트를가리키는포인터가필요하다. find 연산 각루트는집합이름을가리키는포인터를가진다. 임의의요소가어느집합에있는지알고싶다면, 1) parent 링크를따라가서그트리의루트까지간다. 2) 그곳에있는집합이름포인터를리턴한다. Young-Ho Park
Set 표현 0 4 6 7 8 4 0 1 9 1 9 6 7 8 S1 È S2 S2 È S1 S 1 È S 2 의가능한표현들 Young-Ho Park
Set 표현 0 set name pointer 6 7 8 S1 S2 4 S3 1 9 2 3 5 S 1,S 2, S 3 의자료표현 Young-Ho Park
Set 표현 i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] parent -1 4-1 2-1 2 0 0 0 4 S1,S2, S3 의배열표현 int find1(int i) { for(; parent[i] >= 0; i = parent[i]) ; return i; void union1(int i, int j) { parent[i] = j; /* or parent[j] = i; */ union-find 함수의초기구현 Young-Ho Park
Set 표현 이전집합표현방식은, 구현이쉽지만, 성능면에서좋지않다. 예 ) S i = {i, 0 i< p - 처음에, p 개의 node 로이루어진 forest 라면, parent[i] = -1, 0 i< p - 다음과같이 operation 이수행되면, union(0,1),find(0) union(1,2),find(0) union(n-2,n-1),find(0) 변질 ( 퇴행 ) (degenerate) 트리생성 : 위연산들의시간복잡도 : O(n) + O(n 2 ) à O(n 2 ) Young-Ho Park
Set 표현 n-1 n-2 0 degenerate tree ( 변질트리 ) Young-Ho Park
Set 표현 변질트리생성을방지하기위해서는, - union(i,j) 에대한 weighting rule 정의 ) union(i,j) 를위한 weighting rule : 트리 i 에있는노드개수가트리 j 의노드개수보다작으면, j 를 i 의 parent 로만든다. 그렇지않으면, i 를 j 의 parent 로만든다. 각트리에노드개수가몇개인지알아야한다. 루트노드에 count field 가필요하다 : count[i] for root i parent[i] = -count[i] Young-Ho Park
Set 표현 0 1 n-1 0 2 n-1 0 3 n-1 1 1 2 initial 0 4 n-1 union(0,1), 0=find(0) union(0,2), 0 0=find(0) 1 2 3 1 2 3 n-1 union(0,3),, union(0,n-1) 0=find(0) weighting rule 을적용하여구한트리 79