제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1
1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다. 방법 2) 왼쪽트리 L -> A -> 오른쪽트리 R 방법 3) 왼쪽트리 L -> 오른쪽트리 R -> A 방법 4) A -> 왼쪽트리 L -> 오른쪽트리 R H 왼쪽트리 L A B C D E F G I 오른쪽트리 R 2
트리를탐색하는방법연습 : 아래트리의예에서 4 가지탐색방법에따라방문되는노드를살펴보면다음과같다. [ 참고 ] http://www.student.seas.gwu.edu/~idsv/idsv.html 1) 중위탐색 (inorder traversal) : LVR (Left Visit Right) 2) 전위탐색 (preorder traversal) : VLR (Visit Left Right) 3) 후위탐색 (postorder traversal) : LRV (Left Right Visit) 다음과같은 4 가지방법들을생각해볼수있다. 방법 1) 레벨순 A B C D E F G H I 방법 2) 중위탐색 B A C H D I B E A F C G D E F G 방법 3) 전위탐색 A B D H I E C F G H I 방법 4) 후위탐색 H I D E B F G C A 왼쪽트리 L 오른쪽트리 R 3
(1) 중위탐색 (inorder traversal) 중위탐색은 왼쪽트리 -> 루트노드 -> 오른쪽트리순으로방문을하게된다. 주의할점은왼쪽트리를방문할때왼쪽트리자체가트리이기때문에왼쪽트리안에서도다시중위탐색을한다 그러므로왼쪽트리로간다음왼쪽트리의왼쪽트리, 왼쪽트리의루트노드, 왼쪽트리의오른쪽트리순이된다. 트리탐색알고리즘은순환알고리즘 (recursive algorithm) 이간단하다. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 중위탐색 (inorder traversal) 알고리즘 4
참고 : 순환알고리즘 (recursive algorithm) 순환알고리즘이란프로그램이자기자신을호출하는프로그램을말한다. 순환알고리즘에대응되는말은반복알고리즘이다. ( 예 ) n! (n factorial 이라고부름 ) 함수는다음과같이정의된다. 6! = 6 * 5 * 4 * 3 * 2 * 1 이다. ( 반복알고리즘 ) 1 부터 n 까지곱한값을누적하면된다. int factorial(int n) { int f =1, i=1; for(i =1; i <= n; i++) { f = f * i; return f; ( 순환알고리즘 ) 프로그램을순환알고리즘으로작성하면다음과같다. 6! = 6 * 5! ( 단 1! = 1) int factorial(int n) { if (n ==1) return 1 else return ( n * factorial(n-1) ); 5
순환알고리즘 (recursive algorithm) 예 ( 예 ) Greatest common divisor ( 예 ) void recursivefunction(int num) { printf("%d n", num); if (num < 4) recursivefunction(num + 1); ( 예 ) void recursivefunction(int num) { if (num < 4) recursivefunction(num + 1); printf("%d n", num); 6
중위탐색예 1) 중위탐색을하면 1. 왼쪽트리 (B D E H I), 루트 (A), 오른쪽트리 (C F G) 이기 때문에왼쪽트리를방문해야한다. 2. 왼쪽트리 (B D E H I) 가트리를구성하기때문에왼쪽트리를다시중위방문을하면다음과같은방법들을생각해볼수있습니다. 왼쪽트리 (H D I), 루트 (B), 오른쪽트리 (E) 3. 다시왼쪽트리를 (H D I) 를중위탐색을하면왼쪽트리 (H), 루트 (D), 오른쪽트리 (I) 가된다. 4. 왼쪽트리 (H) 를중위탐색을하면왼쪽 ( 없음 ), 루트노드 (H), 오른쪽트리 ( 없음 ) 이되기때문에 H 가결과가되고출력된다 ( 출력 => H) 5. 3 번으로돌아가서루트방문 ( 출력 => HD) 하고, 오른쪽트리 (I) 를다시중위탐색을한다. 6. 오른쪽트리 (I) 를중위탐색을하면왼쪽 ( 없음 ), 루트노드 (I), 오른쪽트리 ( 없음 ) 이되기때문에 I 가결과가되고출력된다 ( 출력 => HDI) 7. 3 번이끝났으므로 2 번에서루트방문 ( 출력 => HDIB) 오른쪽트리 (E) 를방문한다 ( 출력 => HDIBE) 8. 2 번이끝나면 1 번의루트방문 ( 출력 => HDIBEA) 하고 1 번의오른쪽트리를방문한다. 9. 1번의오른쪽을마찬가지중위탐색을하면결과는 => HDIBEAFCG 가된다. H 왼쪽트리 L B A C D E F G I 오른쪽트리 R 7
중위탐색예 2) 결과 => A / B * C * D + E ( 중위표기식 ) 1 + 2 * 17 E 3 * 14 D 18 19 4 / 11 C 15 16 5 A 8 B 12 13 6 7 9 10 트리의예 - 수식트리 (expression tree) 8
순서 호출노드번호 루트의값 동작 순서 호출노드번호 루트의값 동작 1 1 + 없음 2 2 * 없음 3 3 * 없음 4 4 / 없음 5 5 A 없음 6 6 NULL 없음 7 5 A printf 8 7 NULL 없음 9 4 / printf 10 8 B 없음 11 9 NULL 없음 12 8 B printf 13 10 NULL 없음 14 3 * printf 15 11 C 없음 16 12 NULL 없음 17 11 C printf 18 13 NULL 없음 19 2 * printf 20 14 D 없음 21 15 NULL 없음 22 14 D printf 23 16 NULL 없음 24 1 + printf 25 17 E 없음 26 18 NULL 없음 27 17 E printf 28 19 NULL 없음 중위탐색알고리즘과중위탐색과정 => A / B * C * D + E 9
(2) 전위탐색 (preorder traversal) 전위탐색은 루트노드 -> 왼쪽트리 -> 오른쪽트리순으로방문을하게된다. 중위탐색과마찬가지로왼쪽트리를방문할때왼쪽트리자체가트리이기때문에왼쪽트리에서도다시전위탐색을한다. 그러므로왼쪽트리의루트노드, 왼쪽트리의왼쪽트리, 왼쪽트리의오른쪽트리순이된다. 노드가 1 개있는트리는그냥왼쪽, 오른쪽트리가없기때문에바로방문을한다. 이알고리즘은다음과같다. 마찬가지로순환알고리즘이다. void preorder(tree_ptr ptr) { if(ptr) { printf( %d, ptr->data); preorder(ptr->left_child); preorder(ptr->right_child); 전위탐색 (preorder traversal) 알고리즘 10
(3) 후위탐색 (postorder traversal) 후위탐색은왼쪽트리 -> 오른쪽트리 -> 루트노드순으로방문을하게된다. 중위탐색과마찬가지로왼쪽트리를방문할때왼쪽트리자체가트리이기때문에왼쪽트리에서도다시후위탐색을한다. 그러므로왼쪽트리의왼쪽트리, 왼쪽트리의오른쪽트리, 왼쪽트리의루트노드순이된다. 노드가 1개있는트리는그냥왼쪽, 오른쪽트리가없기때문에바로방문을한다. 이알고리즘은다음과같다 void postorder(tree_ptr ptr) { if(ptr) { postorder(ptr->left_child); postorder(ptr->right_child); printf( %d, ptr->data); 후위탐색 (postorder traversal) 알고리즘 11
트리탐색을꼭순환알고리즘으로작성해야하는것은아니다. 아래예는중위탐색알고리즘을반복적인알고리즘으로작성한것이다. 방문하면서과거노드를 LIFO 순으로기억을해야하기때문에스택을사용하였다. 순환알고리즘과비교하여보자반복적중위탐색 (inorder traversal) 알고리즘 /* iterative inorder tree traversal */ void iter_inorder(tree_ptr 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; 12
(4) 레벨탐색 (level order traversal) 레벨탐색은레벨 1 노드들 -> 레벨 2 노드들 -> 레벨 3 노드들 -> 순서대로탐색을한다. 레벨 i를탐색할때방문노드의자식노드를저장을해둔다음레벨 i를다방문하면다음방문지는저장해둔노드를꺼내어방문한다. 이때저장해둔노드들은먼저저장된노드를먼저꺼내어방문을하면된다. 즉큐 (FIFO) 자료구조가되는것이다. 아래트리의경우레벨순으로방문을하면다음과같다. => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 13
레벨탐색 (level order traversal) 알고리즘 void level_order(tree_ptr ptr) { int front = rear = 0; tree_ptr queue[max_queue_size]; if(!ptr) return; add(front,&rear,ptr); for(;;) { ptr = delete(&front, rear); if(ptr) { printf( %d, ptr->data); if(ptr->left_child) add(front,&rear,ptr->left_child); if(ptr->right_child) add(front, &rear,ptr->right_child); else break; 14
Q/A 다음이진트리를탐색한결과는? 1. 중위탐색 2. 후위탐색 3. 전위탐색 4. 레벨탐색 15
2. 쓰레드 (Threaded) 이진트리 문제제기 : 이진트리를탐색할때일정한순서에따라노드를탐색하게된다. 이때노드의순서에따라미리다음노드를연결시켜놓으면훨씬검색속도가빠르지않을까? 방법 : 트리의링크에서자식이없는노드에링크필드값을 NULL 로비워두지말고다음방문할곳이나바로앞방문했던노드를가리키도록한다. 트리의전체노드수는 N 개이고링크의수는 2N 개이며이중 N+1 개의링크는비어있게된다. 이 N+1 개의링크를활용한다, 이링크를 thread 라고부른다. left_child data right_child data 쓰레드만들기 left_child right_child 비어있는링크값이왼쪽인지오른쪽인지에따라다음과같이구축한다. 1) 왼쪽링크가비어있으면 ( if ptr->left_child is null ), => 노드의링크값을중위탐방순서의바로전노드값을저장한다. 2) 오른쪽링크가비어있으면 ( if ptr->right_child is null ), => 노드의링크값을중위탐방순서의바로다음노드값을저장한다 16
A B C D E F G H I 쓰레드트리의예 17
노드의링크에저장된값이자식노드에대한포인터인지, 쓰레드인지구분을어떻게하는가? ( 정답 ) 필드를두어서표시하여야한다 필드변수이름 : left_thread and right_thread 변수값 : - ptr->left_thread = TRUE ptr->left_child 가 thread 값일경우 - ptr->left_thread = FALSE ptr->left_child 가왼쪽자식일경우 - ptr->right_thread = TRUE ptr->right_child 가 thread 값일경우 - ptr->right_thread = FALSE ptr->right_child 가오른쪽자식일경우 18
쓰레드트리를위한노드의선언과구조 쓰레드트리를만들기위해서는일반트리와같으나쓰레드인지구분하는필드를두게된다. struct tnode { short int left_thread; struct tnode *left_child; char data; struct tnode *right_child; short int right_thread; ; typedef struct tnode threaded_tree; typedef threaded_tree *threaded_ptr; left_thread left_child data right_child right_thread 19
머리노드 : 쓰레드트리에서는왼쪽끝과오른쪽끝의두노드는가리킬곳이없으므로전체트리를관리하는머리노드 ( 헤드노드 ) 를둔다. 트리가비어있어도머리노드는남아있게된다. 예 ) 머리노드의예 : 일반노드와구조는같다. left_thread left_child data right_child right_thread TRUE FALSE 20
예 ) 헤드노드를가진쓰레드이진트리 : 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 21
쓰레드트리의중위탐색 이진트리를쓰레드트리로바꾼후에는중위탐색을편하게할수있다. 자식노드가있으면자식노드에대한링크값을바로알수있고자식노드가없으면쓰레드링크에다음방문지링크값이포함되어있으므로역시바로찾을수있다. 이과정을알고리즘으로설명하면다음과같다. 먼저임의의노드의다음방문링크를찾는 insucc() 함수를만들어보자 알고리즘 insucc() : (inorder traversal of a threaded binary tree) { find the inorder successor of ptr - if ptr->right_thread=true, then ptr->right_child -otherwise follow a path of left-child links from the right-child of ptr until we reach a node with left_thread=true 22
쓰레드트리의중위탐색에대한다음노드값찾기 insucc() 노드의포인터값 tree 를인자로주면반환되는값은주위탐색의다음방문노드이다. threaded_ptr insucc(threaded_ptr tree) { threaded_ptr temp; temp = tree->right_child; if(!tree->right_thread) while(!temp->left_thread) temp = temp->left_child; return temp; 프로그램 tinorder() : 쓰레트트리의중위탐색알고리즘 쓰레드트리의중위탐색알고리즘쓰레드트리의중위탐색알고리즘은루트노드에서시작하여서다음노드를계속찾아나가면된다. void tinorder(threaded_ptr tree) { threaded_ptr temp = tree; for(;;) { temp = insucc(temp); if(temp = tree) break; printf( %3c, temp->data); 프로그램 tinorder() : 쓰레트트리의중위탐색알고리즘 23
쓰레드이진트리에새로운노드를첨가한다면어떻게될까? 알고리즘 insert_right() : 쓰레드트리에서노드의오른쪽자식노드삽입 { 1) parent->right_threaded 를 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 로변경 24
프로그램 insert_right() : 쓰레드트리에서임의의노드의오른쪽에새로운노드를삽입하는프로그램 void insert_right(threaded_ptr parent, threaded_ptr child) { 프로그램 tinorder() : 쓰레트트리의중위탐색알고리즘 threaded_ptr temp; child->right_child=parent->right_child; (4) child->right_thread=parent->right_thread; (2) child->left_child=parent; (3) child->left_thread=true; (2) parent->right_child=child; (5) parent->right_thread=false; (1) if(!child->right_thread) { /* 오른쪽자식이있는경우 */ temp=insucc(child); temp->left_child=child; 25
예 1) 쓰레드트리에서임의의노드의오른쪽에새로운노드를삽입하는그림 오른쪽자식이없는경우 root root A A B parent B parent C D child C D child 삽입전 삽입후 26
예 2) 쓰레드트리에서임의의노드의오른쪽에새로운노드를삽입하는그림 오른쪽자식이있는경우 root root A A B parent B parent C D C X child E F D 삽입전 child X E F 삽입후 27
3. 이진트리에관한알고리즘 1. 이진트리복사 : 이진트리가있을때똑같은모양의이진트리를만든다면? 똑같은이진트리를한개더만든다면트리를탐색하면서새로운노드를만날때마다노드를복사하여야한다. 후위탐색방법을이용하여복사하여보도록하자. /* program copy() */ 이진트리의복사알고리즘 tree_ptr copy(tree_ptr original) { tree_ptr temp; if(original) { temp = (tree_ptr)malloc(sizeof(node)); temp->left_child = copy(original->left_child); 1 temp->right_child = copy(original->right_child); 2 temp->data = original->data; 3 return temp; return NULL; 28
original? nul 1 0 2 nul 복사 null 3 null null 4 null 29
2. 이진트리동등비교 : 두개의이진트리가있을때두이진트리가모양과노드에값이똑같은지비교하려면? 두개의이진트리를탐색하면서노드를만날때마다두트리의노드의값을비교하면된다. 탐색방법은여러가지탐색방법중택하면되지만전위탐색방법을이용하여비교하도록하자. 이진트리의동등검사알고리즘 /* program equal() */ 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
first second first second 0 0 nul 1 2 nul nul 1 2 nul null 3 null null 4 null null 3 null null 4 null 31
Review 트리는중요한자료구조중의하나이다. 또트리에관한대부분프로그램은트리의탐색에서시작한다. 이장에서는트리의탐색방법으로중위탐색, 전위탐색, 후위탐색과레벨탐색에대한알고리즘을살펴보았다. 탐색은대부분순환알고리즘을이용하여작성된다. 이진트리를효율적으로탐색하는방법은트리구조를쓰레드 (thread) 구조로바꾸는방법이있다. 중위탐색을효율적으로하기위한방법으로노드의링크값중사용하지않는값을중위탐색의다음이나, 전방문노드를가리키도록하는방법이다. 자료구조를변경하여프로그램의효율성을높이는대표적인예이다. 이진트리에관한알고리즘이많이있지만이진트리의복사알고리즘, 동등성검사알고리즘을통하여좀복잡한알고리즘에대하여살펴볼수있다. 32