4.1 관계

Transcription

1 5 장트리 트리 (tree) 정보의항목들이가지 (branch) 로연결될수있게데이터가조직되는것, 예 ) 그림 5.1 정의 : 트리는 1 개이상의노드로이루어진유한집합으로서 1 root node 2 나머지노드들은 n( 0) 개의분리집합 (disjoint set) T 1, T 2,, T n 으로분리, T i 는각각트리로서 subtree 노드 : 정보항목 + 다른노드로뻗어진가지

2 A B C D E F G H I J K L M Level 1 Level 2 Level 3 Level 4 트리관련용어 노드의차수 (A: 3), 트리의차수 (3) Leaf 또는단말노드 (K, L, F, G, M, I, J) Parent (E: B), Children (B: E & F), Siblings (E & F) Ancestor (M: H, D, A), Descendants (B: E, F, K, L) Level (Root: 1), Height or Depth (4)

3 5.2 이진트리 정의 : 이진트리는공집합이거나루트와왼쪽서브트리, 오른쪽서브트리라고부르는분리된이진트리로구성된노드의유한집합이다. 이진트리에대한 ADT

4 structure Binary_Tree ( 줄여서 BinTree) objects: 공백이거나루트노드, 왼쪽 Binary_Tree, 오른쪽 Binary_Tree로구성되는노드들의유한집합 functions: 모든 bt, bt1, bt2 BinTree, item element BinTree Create() ::= 공백이진트리를생성 Boolean IsEmpty(bt) ::= if (bt == 공백이진트리 ) return TRUE else return FALSE BinTree MakeBT(bt1, item, bt2) ::= 왼쪽서브트리가 bt1, 오른쪽서브트리가 bt2, 루트는데이타를갖는이진트리를반환 BinTree Lchild(bt) ::= if (IsEmpty(bt)) return 에러 else bt의왼쪽서브트리를반환 element Data(bt) ::= if (IsEmpty(bt)) return 에러 else bt의루트에있는데이타를반환 BinTree Rchild(bt) ::= if (IsEmpty(bt)) return 에러 else bt의오른쪽서브트리를반환

5 이진트리와트리의차이점 공백이진트리존재 서브트리의순서중요 서로다른두이진트리 empty right subtree A A empty left subtree B B

6 A A Level 1 B B C 2 C D E F G 3 D H I 4 E (a) (b) 5 Figure 5.9: 경사트리와완전이진트리

7 이진트리의특성 보조정리 5.1 [ 최대노드수 ] (1) 레벨 i 에서의최대노드수 : 2 i-1 (i 1) (2) 깊이가 k 인이진트리가가질수있는최대노드수 = 레벨 1,2,..k 의노드의합 = 2 k - 1(k 1) 보조정리 5.2[ 단말노드수와차수가 2 인노드수와의상관관계 ] n0 : 단말노드수, n2 : 차수가 2 인노드수일때 n0 =n2 +1 pf) n : 전체노드수, B : 전체간선수 (n 1 +2n 2 ) n 1 : 차수가 1 인노드수 n=n 0 + n 1 + n 2 n=b+1=n 1 + 2n 2 +1 n 0 =n 2 +1

8 포화이진트리 (full binary tree) 깊이가 K 이고, 노드수가 2 K -1 인이진트리 1,,2 K -1 까지순차적노드번호를붙인깊이 4 의포화이진트리 level 1 1 depth 4 level level level 정의 : 깊이가 K 이고노드수가 n 인이진트리가만일이트리의각노드들이깊이 k 인포화이진트리에서 1 부터 n 까지번호를붙인노드들과일대일로일치할때완전이진트리라함, 예 ) 그림 5.9 의 (b)

9 이진트리의표현 배열표현, 링크표현 이진트리의배열표현 그림 5.10 처럼, 노드에 1 부터 n 까지번호가할당되므로, 일차원배열에각노드를저장 보조정리 5.3 을사용하여자식과부모의위치결정 보조정리 5.3: n 개의노드를가진완전이진트리 1 PARENT(i) : _ I / 2 _ if i 1 2 LCHILD(i) : 2i if 2i n otherwise no left child 3 RCHILD(i) : 2i+1 if 2i+1 n otherwise no right child

10 이진트리의배열표현 1 완전이진트리는배열표현이공간낭비없으므로좋은표현 2 편향이진트리 ( 깊이 k) : 2 k -1 중 k 만사용 ( 최악의경우 ) A A B B C C D E F G D H I E (a) (b)

11 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]... [16] - A B - C D -... E [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] - A B C D E F G H I

12 링크표현 배열표현은 complete binary tree 가아닐때는메모리낭비가있고, 삽입 / 삭제시많은노드이동필요 linked 표현사용 data Left_child data Right_child Left_Child Right_Child typedef struct node *tree_pointer; typedef struct node { int data; tree_pointer left_child, right_child; ;

13 A A B B C C D E F G D H I E (a) (b) root root A 0 A B 0 B C C 0 D 0 E 0 0 F 0 0 G 0 D 0 0 H 0 0 I 0 0 E 0

14 5.3 이진트리순회 트리의노드들을방문하는연산 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L: 왼쪽이동, V: 노드방문 ( 데이타출력 ), R: 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR (inorder) : infix VLR (preorder) : prefix LRV (postorder) : postfix * * + D E 산술식의이진트리표현 operators, variables / C A B

15 중위순회 (inorder traversal) 1. 널노드에도달할때까지왼쪽방향으로이동 2. 널노드에도착하면널노드의부모방문 3. 순회는오른쪽방향으로계속 4. 오른쪽으로이동할수없을때에는하나더뒤의노드로이동 void inorder(tree_pointer ptr) /* 중위트리순회 */ + { * if (ptr) { inorder(ptr->left_child); * printf("%d", ptr->data); D inorder(ptr->right_child); / C A output A / B * C * D + E B E

16 전위순회 (preorder traversal) 1. 노드를먼저방문 2. 왼쪽가지의모든노드방문 3. 널노드에도달하면오른쪽자식을가진가장가까운조상으로돌아가서오른쪽자식에서순회를계속 void preorder(tree_pointer ptr) /* 전위트리순회 */ { if (ptr) { printf("%d", ptr->data); preorder(ptr->left_child); preorder(ptr->right_child); output + * * / A B C D E A / * B * C + D E

17 후위순회 (postorder traversal) 1. 노드를방문하기전에두자식을먼저방문노드보다그노드의자식이먼저출력 void postorder(tree_pointer ptr) /* 후위트리순회 */ { if (ptr) { + postorder(ptr->left_child); * E postorder(ptr->right_child); printf("%d", ptr->data); * D / C output A B / C * D * E + A B

18 반복적중위순회순환을시뮬레이트 : 스택필요 void iter_inorder(tree_pointer node) { int top = -1; /* 스택초기화 */ tree_pointer stack[max_stack_size]; for (;;) { for (; node; node = node->left_child) add(&top, node); /* 스택에삽입 */ node = delete(&top); /* 스택에서삭제 */ if (!node) break; /* 공백스택 */ printf("%d", node->data); node = node->right_child;

19 레벨순서순회 (level order traversal): 큐를사용하는순회 1. 루트먼저방문, 2. 루트의왼쪽자식, 3. 루트의오른쪽자식 void level_order(tree_pointer ptr) /* 레벨순서트리순회 */ { int front = rear = 0; tree_pointer queue[max_queue_size]; if (!ptr) return; /* 공백트리 */ addq(front, &rear, ptr); for (;;) { 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; // 그림 5.15, output + * E * D / C A B

20 이진트리의추가연산 이진트리의복사 : 트리순회를이용하여하나의노드씩복사 tree_pointer copy(tree_pointer original) // 후위순회변형 { /* 주어진트리를복사하고복사된트리의 tree_pointer 를반환한다. */ tree_pointer temp; if (original) { temp = (tree_pointer) malloc(sizeof(node)); if (IS_FULL(temp)) { fprintf(stderr, "The memory is full"); exit(1); temp->left_child = copy(original->left_child); temp->right_child = copy(original->right_child); temp->data = original->data; return temp; return NULL;

21 이진트리의동일성검사 동일한구조와정보? int equal(tree_pointer first, tree_pointer secon) { /* 두이진트리가동일하면 TRUE, 그렇지않으면 FALSE 를반환한다. */ return ((!first &&!second) (first && second && (first->data == second->data) && equal(first->left_child, second->left_child) && equal(first->right_child, second->right_child));

22 명제식의만족성 (satisfiability) 문제 식의값이참이되도록, 변수에값을지정할수있는방법이있는가? ( x x x ) ( x x ) 가능한모든참과거짓의조합에대해서그결과를조사 위의경우에는 8 가지의조합이가능함 식을계산하기위해서는두 subtree 를먼저계산 : 후위순회

23 ( x x x ) ( x x ) x 3 x 1 x 3 x 2 x 1

24 typedef enum {not, and, or, true, false logical; typedef struct node *tree_pointer; typedef struct node { tree_pointer left_child; logical short int data; value; tree_pointer right_child; ; left_child data value right_child 리프노드의 node->data 는이노드가나타내는변수의현재값을갖는다고가정 : x_1, x_2, x_3 는 true 또는 false 가짐 N 개의변수를갖는명제식의트리를 root 가가리킨다고가정

25 만족성알고리즘 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(<combination>); return; printf("no satisfiable combination");

26 트리를계산하는함수는후위순회를수정하여작성 void post_order_eval (tree_pointer node) { if (node) { post_order_eval(node->left_child); post_order_eval(node->right_child); switch(node->data) { case not: node->value =!node->right_child->value; break; case and: node->value = node->right_child->value && node->left_child->value; break; case or: node->value = node->right_child->value node->left_child->value; break; case true: node->value = TRUE; break; case false: node->value = FALSE;

27 5.5 스레드이진트리 이진트리에는 2n 개의링크중 n+1 개의널링크 pf) 2 n_0 + n_1 = n + 1 p200 스레드 (Thread : 실 ) 널링크를다른노드를가리키는포인터로사용 1 ptr->left_child 가 NULL 이면중위순회시 ptr 앞에방문하는노드에대한포인터 2 ptr->right_child 가 NULL 이면중위순회시 ptr 다음에방문하는노드에대한포인터

28 스레드트리예 중위순회 : H D I B E A F C G 그림 5.14 (a) 스레드이진트리는? root A B C D E F G H I

29 스레드이진트리의표현 left_thread 와 right_thread 라는필드첨가 left_thread 가 true 이면 left_child thread false 이면 left_child pointer right_thread 가 true 이면 right_child thread false 이면 right_child pointer typedef struct threaded_tree *threaded_pointer ; typedef struct threaded_tree { short int left_thread ; threaded_pointer left_child ; char data ; threaded_pointer right_child ; short int right_thread ; ;

30 분실스레드 첫번째방문하는 H 의왼쪽자식, 마지막방문하는 G 오른쪽자식 분실스레드해결방법 헤드노드사용 : root left_child 가실제트리의첫번째노드를가리킴 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

31 스레드이진트리의중위순회 중위후속자찾기 : 다음방문할노드찾기, 스택의사용없음 threaded_pointer insucc (threaded_pointer tree) { threaded_pointer temp ; temp = tree right_child ; if (!tree right_thread) //right_thread 가 false 이면 while (!temp left_thread) temp = temp left_child ; return temp ; // 헤드노드의왼쪽자식은트리를가리키고, 오른쪽스레드는 FALSE 라가정 void tinorder (threaded_pointer tree) { // 스레드이진트리의중위순회 threaded_pointer temp = tree ; for ( ; ; ) { temp = insucc (temp) ; if (temp == tree) break ; print ( %3c, temp->data) ;

32 스레드이진트리에서의노드삽입 s 의오른쪽자식으로 r 을삽입 root root s r s r root (a) root s r s r before (b) after

33 void insert_right (threaded_pointer parent, threaded_pointer child) { // 스레드이진트리에서 child 를 parent 의오른쪽자식으로삽입 threaded_pointer 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) { //parent 의오른쪽자식이있었으면, //child 는 parent 의전중위후속자였던노드의중위선행자가됨 temp = insucc (child) ; temp left_child = child ;

34 5.6 히프 (heap) 정의 : 최대트리는각노드의키값이그자식의키값보다작지않은트리이다. 최대히프는최대트리이면서완전이진트리이다. 정의 : 최소트리는각노드의키값이그자식의키값보다크지않은트리이다. 최소히프는최소트리이면서완전이진트리이다.

35 최대히프 최소히프

36 추상데이타타입 MaxHeap structure MaxHeap objects : 각노드의값이그자식들의것보다작지않도록조직된 n>0 원소의완전이진트리 functions : 모든 heap MaxHeap, item Element, n, max_size integer MaxHeap Create(max_size) ::= 최대 max_size개의원소를가질수있는공백히프를생성 Boolean HeapFull(heap, n) ::= if (n == max_size) return TRUE else return FALSE MaxHeap Insert(heap, item, n)::= if (!HeapFull(heap, n)) item을히프에삽입하고그히프를반환 else return 에러 Boolean HeapEmpty(heap, n) ::= if (n>0) return TRUE else return FALSE Element Delete(heap, n) ::= if (!HeapEmpty(heap, n)) 히프에서가장큰원소를제거하고그원소를반환

37 우선순위큐 (priority queue) max(min) priority queue: 삭제시 highest(or lowest) priority 를가지는것부터삭제 Heap 을사용하여구현가능 예 ) 운영체제작업스케쥴러 우선순위큐의표현방법 표현방법 삽입 삭제 순서없는배열 Θ(1) Θ(n) 순서없는연결리스트 Θ(1) Θ(n) 정렬된배열 O(n) Θ(1) 정렬된연결리스트 O(n) Θ(1) 최대히프 O(log_2 n) O(log_2 n)

38 최대히프에서의삽입 1, 5, 21 을삽입할때의예 p (a) (a) 삽입전히프 (b) 새노드의초기위치 히프 (a) 에 5 를삽입 (d) 히프 (a) 에 21 을삽입

39 히프의구현 부모를찾아갈수있어야함 완전이진트리이므로배열을사용하면 parent(i) 는 i 2 #define MAX_ELEMENTS 200 /* 최대히프크기 + 1 */ #define HEAP_FULL(n) (n == MAX_ELEMENTS-1) #define HEAP_EMPTY(n) (!n) typedef struct { int key; /* 다른필드들 */ element; element heap[max_elements]; int n = 0;

40 최대히프에삽입 void insert_max_heap(element item, int *n) { /* n개의원소를갖는최대히프에 item을삽입한다. */ int i; if (HEAP_FULL(*n)) { fprintf(stderr, "The heap is full. "); exit(1); i = ++(*n); while ((i!= 1)&&(item.key>heap[i/2].key)){ // 부모보다크면 heap[i] = heap[i/2]; // 부모를 i위치에저장 i /= 2; // item의위치를부모위치 i/2로 heap[i] = item;

41 Insert_max_heap 알고리즘의분석 While 루프, 새로운리프에서루트까지의경로를따라루트까지도달하던가, 부모위치 I/2의값이삽입되어질값보다큰위치 I를선택 n개의원소를가진완전이진트리의높이 log 2 ( n 1) 연산시간은 O(log_2 n)

42 최대히프에서의삭제 최대값얻기위해루트에서삭제 나머지트리를완전이진트리로재구성해야함 히프를재구성하기위해부모노드와자식노드를비교하여순서가틀린원소들을교환 제거됨 (a) 히프구조 (b) 10 이루트에삽입 (c) 최종히프

43 element delete_max_heap(int *n) { /* 가장큰값의원소를히프에서삭제 */ int parent, child; element item, temp; if (HEAP_EMPTY(*n)) { fprintf(stderr, "The heap is empty"); exit(1); /* 가장큰키값을저장 */ item = heap[1]; /* 히프를재구성하기위해마지막원소를이용 */ temp = heap[(*n)--]; parent = 1; child = 2; while (child <= *n) { /* 현 parent 의가장큰자식을탐색 */ if ((child < *n) && (heap[child].key < heap[child+1].key)) child++; if (temp.key >= heap[child].key) break; /* 아래단계로이동 */ heap[parent] = heap[child]; parent = child; child *= 2; heap [parent] = temp; return item;

44 delete_max_heap 알고리즘의분석 부모와자식노드의비교 While 루프 n 개의원소를가진완전이진트리의높이 log 2 ( n 1) 연산시간은 O(log_2 n)

45 5.7 이진탐색트리 삽입, 삭제, 탐색연산에지금까지자료구조중좋은성능 히프는임의의원소의삭제에 O(n) 이진탐색트리는이진트리로서공백가능하고, 만약공백이아니라면 1. 모든원소는서로상이한키를갖는다. 2. 왼쪽서브트리의키들은그루트의키보다작다. 3. 오른쪽서브트리의키들은그루트의키보다크다 4. 왼쪽과오른쪽서브트리도이진탐색트리이다. 이진트리의일종, 이전의전위, 중위, 후위순회를수정없이사용할수있고, 이절에서는삽입, 삭제, 탐색연산을추가한다.

46 이진탐색트리예 ( 그림 5.30) 질문 : 이진탐색트리인가? (a) (b) (c)

47 이진탐색트리의탐색 : key 값을찾는다. tree_pointer search(tree_pointer root, int key) /* 순환탐색 */ { /* 키값이 key 인노드에대한포인터반환. 그런노드가없는경우에는 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);

48 tree_pointer search2 (tree_pointer tree, int key) /* 반복탐색 */ { /* 키값이 key 인노드에대한포인터반환. 그런노드가없는경우는 NULL 을반환 */ while (tree) { if (key == tree->data) return tree; if (key < tree->data) else tree = tree->left_child; tree = tree->right_child; return NULL; search, serach2 의분석 : 높이가 h 인이진탐색트리에대해 O(h)

49 이진탐색트리에대한삽입 동일한 key 값을가진노드가없어야삽입가능 탐색이실패하면탐색이끝난지점에노드를삽입 그림 5.30(b) 에 80 삽입 탐색이끝난 40 의오른쪽자식에 80 을삽입 5.31 (a) (a) 에 35 삽입 (b) 그림 (a) 80 을삽입 (b) 35 를삽입

50 void insert_node(tree_pointer *node, int num) /* 트리내의노드가 num 을가리키고있으면아무일도하지않음 ; 그렇지않은경우는 data=num 인새노드를첨가 */ { tree_pointer ptr, temp = modified_search(*node, num); if (temp!(*node)) { // temp 가널이아니거나, 널이라도 *node 가널 /* num 이트리내에없음 */ ptr = (tree_pointer)malloc(sizeof(node)) ; if (IS_FULL(ptr)) { fprintf(stderr, "The memory is full"); exit(1); ptr->data = num; ptr->left_child = ptr->right_child = NULL; if (*node) /* temp 의자식으로삽입 */ if (num < temp->data) temp->left_child = ptr; else temp->right_child = ptr; else *node = ptr:

51 modified_search search2 를수정 이진탐색트리 *node 에서키값 num 을탐색하는데만약트리가공백이거나 num 이존재하면 NULL 을반환하고, 그렇지않으면탐색도중에마지막으로검사한노드에대한포인터를반환한다. insert_node 의분석 높인 h인트리에서 num을탐색하는데 O(h) 나머지는 Θ(1) 전체시간은 O(h)

52 이진탐색트리에서의삭제 : 세가지경우가존재 1. 단말노드의삭제 : 부모의자식필드에 NULL 을삽입 그림 31(b) 에서 35 를삭제하려면그부모노드의왼쪽자식필드를 NULL 로만들고노드를반환, 결과는그림 31(a) 2. 하나의자식을가진비단말노드의삭제 삭제된노드의자식을삭제된노드의자리에대체 그림 5.31(a) 에서 40 을삭제하면그림 5.32 의트리 3. 두개의자식을가진비단말노드의삭제 : i. 왼쪽서브트리에서가장큰원소로치환, 또는 ii. 오른쪽서브트리에서가장작은원소로치환대체하려고선택된노드를 A 라하면 A 의자식을 A 의부모노드의자식으로연결하고, A 를반환 ( 참고 ) A 의자식은 0 이거나 1 (A 는가장크거나작으므로 )

53 그림 그림 5.33 두자식을가진노드의삭제 (b) 60 을삭제하기전의트리 (b) 60 을삭제한후의트리

54 이진탐색트리 (n) 의높이 worst case : height = n [1,2,3,,n] 으로삽입할때 average : height = O(log n ) 최악의경우에도 height = O(log n ) 이되는트리 균형탐색트리 (balanced search tree) 탐색, 삽입, 삭제를 O(h) 시간에할수있다. 10 장 : AVL, 2-3, 2-3-4, red-black, B 트리

55 5.8 선택트리 K 개의런 (run) 에서가장작은키의레코드를출력 런 : key에따라비감소순서로정렬된레코드로구성 직접적인방법은 k-1번비교 선택트리사용하여 k-1 보다적은비교로가능 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8

56 선택트리의구성 단말노드 : 해당런의첫번째레코드 각비단말노드 : 토너먼트의승자 루트노드 : 전체승자또는가장작은값 선택트리구현 노드는레코드에대한포인터만을포함 배열표현방식사용 (why?) : 노드번호는노드의주소 시간복잡도 비교는단말노드에서루트로가는경로에서발생 k 1 트리의레벨수는 ceil (log ) 2 따라서, 트리의재구성시간은 O(log k), n개의모든레코드를모두합병하는데 O(n log k) 처음선택트리설정 O(k) 이므로전체시간은 O(n log k)

57 승자트리에서한레코드가출력되고나서재구성된모습 ( 변경된노드는표시되어있음 ) 연습 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8

58 패자트리 노드가패자를표현, 좀더빠른알고리즘 형제노드들은전에시행되었던토너먼트의패자 비단말노드는패자, 승자는상위노드로진출 각노드는레코드에대한포인터저장, 그림에서는편의상레코드의키값사용, 노드 0 은전체토너먼트의승자 0 6 전체승자 Run

59 5.9 포리스트 포리스트 : n >= 0 개의분리트리의집합 포리스트의이진트리변환 변환된이진트리들을루트의오른쪽서브트리로연결 정의 : T1,T2,,Tn 이트리들로이루어진포리스트라하면이포리스트에대응하는이진트리, B(T1,T2,,Tn) 는 (1) n=0 이면공백 (2) B 는 T1 과같은루트를가지며, 왼쪽서브트리로 B(T11,T12,,T1m), 여기서, T11,T12,, T1m 는 T1 의서브트리 오른쪽서브트리 = B(T2,,Tn)

60 세개의트리로구성된포리스트 A E G B C D F H I 변환된이진트리표현 A B E C F G D H I

61 포리스트 F 에대응하는이진트리 T 의전위, 중위순회는 F 의순회와대응관계 포리스트전위 (forest preorder) (1) F 가공백이면귀환 (2) F 의첫트리의루트를방문 (3) 첫트리의서브트리들을포리스트전위순회 (4) F 의나머지트리들을포리스트전위로순회 포리스트중위 (forest inorder) (1) F 가공백이면귀환 (2) F 의첫트리의서브트리를포리스트중위로순회 (3) 첫트리의루트를방문 (4) 나머지트리들을포리스트중위로순회 포리스트후위 (forest postorder) (1) F 가공백이면귀환 (2) F 의첫트리의서브트리를포리스트후위로순회 (3) 나머지트리들을포리스트후위로순회 (4) F 의첫트리의루트를방문

62 5.10 집합표현 트리를사용한집합표현 그림 5.39: 자식에서부모로가는링크로연결 S 1 S 2 S 3 i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] parent

63 집합의연산 Union : S_1 U S_2 = {0, 6, 7, 8 U {1, 4, 9 = {0, 6, 7, 8, 1, 4, 9 Find (I): 원소 I 를포함하는집합을찾음, 3 은 S_3 에 8 은 S_1 에있음 Union( 합집합 ) 연산 두트리중의하나를다른트리의서브트리로만듦 한루트의부모필드가다른트리의루트를가리키도록함 S 1 S 2 or S 1 S 2

64 find(i) I 에서시작하여음수값의부모인덱스를따라감 find(5) 는 int find1 (int I) { for (; parent[i] >= 0; I = parent[i]) ; return I ; void union1 (int I, int j) { parent[i] = j ;

65 union1 과 find1 의분석 S_I = {I 인집합, 다음의연산을수행 union(0, 1), union(1, 2),, union(n-2, n-1), find(0), find(1),, find(n-1) N-1 N-2 0 union 연산은상수이므로 n-1 개수행 O(n) find 는레벨 I 에대해서는 O(I) 이므로 find(0), find(1),...,find(n-1) = n: O(n^2)

66 union 연산의효율적구현 union(i,j) 를위한가중법칙 트리 I 의노드수 < 트리 j 의노드수 j 가 I 의부모 트리 I 의노드수 > 트리 j 의노드수 i 가 j 의부모 가중법칙을적용하면그림 5.44 가중법칙을적용하기위해, 트리의노드수를루트노드의 parent 필드에음수로저장하면됨

67 void union2 (int I, int j) {/* 가중법칙을이용하여루트가 I 와 j 인집합을합집합함. Parent[I] = -conunt[i], parent[j] = -count[j] int temp = parent[i] + parent[j] ; if (parent[i] > parent[j]) { // 음수이므로 i쪽이노드수가작다 parent[i] = j; /*j를새루트로만듦 */ parent[j] = temp ; else { parent[j] = i; /*i를새루트로만듦 */ parent[i] = temp ;

68 보조정리 5.4: n 개의노드를가진트리 T 가 union2 함수로만들어진트리라면, T 에있는어떤노드도 _ log_2 n _ + 1 보다큰레벨을가질수없다. 보조정리 5.4에따라 union2로만들어진트리에서 find 연산시간 O(log_2 n) 이므로 n-1개의 union과 m개의 find를실행하는시간은 O(n + mlog_2 n)

69 예제 5.1 결과는그림 5.45 예제 5.2 그림 5.45 에서 8 개의 find(7) 를수행하면각각 3 개의 parent 링크필드를거쳐야하므로, 24 개의링크를이동 붕괴법칙을사용하여 find 를수정한 find2 는처음 find2 는세개의링크를거치고세개의링크를변경, 나머지는 7 개는하나의링크만거치면되므로총 13 번이동

70 붕괴법칙 : 만일 j 가 I 에서루트로가는경로위에있다면 j 를루트의자식으로만든다. int find2(int I) { /* 원소 I 를포함하는루트를찾음. 붕괴법칙을사용하여 I 로부터루트로가는모든노드를붕괴시킴 */ int root, trail, lead ; for (root = I; parent[root] >= 0; root = parent[root]) ; for (trail = I; trail!= root; trail = lead) { lead = parent[trail] ; parent[trail] = root ; return root ;