슬라이드 1

Transcription

1 CHAP 7: 트리

2 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree)

3 회사의조직

4 파일디렉토리구조

5 결정트리 ( 예 ) 골프에대한결정트리

6 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드 (A) 서브트리 (subtree): 하나의노드와그노드들의자손들로이루어진트리

7 트리의용어 단말노드 (terminal node): 자식이없는노드 (E,F,G,H,I,J) 비단말노드 : 적어도하나의자식을가지는노드 (A,B,C,D)

8 트리의용어 자식, 부모, 형제, 조상, 자손노드 : 인간과동일 레벨 (level): 트리의각층의번호 높이 (height): 트리의최대레벨 (3) 차수 (degree): 노드가가지고있는자식노드의개수

9 예제 A B C D E F G H A 는루트노드이다. B 는 D 와 E 의부모노드이다. C 는 B 의형제노드이다. D 와 E 는 B 의자식노드이다. B 의차수는 2 이다. 위의트리의높이는 4 이다. I

10 트리의종류 이진트리 트리 일반트리

11 이진트리 (binary tree) 이진트리 (binary tree) : 모든노드가 2 개의서브트리를가지고있는트리 서브트리는공집합일수있다. 이진트리의노드에는최대 2 개까지의자식노드가존재 모든노드의차수가 2 이하가된다 구현하기가편리함 이진트리에는서브트리간의순서가존재

12 이진트리검증 이진트리는공집합이거나 루트와왼쪽서브트리, 오른쪽서브트리로구성된노드들의유한집합으로정의된다. 이진트리의서브트리들은모두이진트리이어야한다.

13 이진트리의성질 노드의개수가 n 개이면간선의개수는 n-1

14 이진트리의성질 높이가 h 인이진트리의경우, 최소 h 개의노드를가지며 최대 2 h -1 개의노드를가진다.

15 이진트리의성질 n 개의노드를가지는이진트리의높이 최대 n 최소

16 이진트리의분류 포화이진트리 (full binary tree) 완전이진트리 (complete binary tree) 기타이진트리

17 포화이진트리 용어그대로트리의각레벨에노드가꽉차있는이진트리를의미한다. 포화이진트리에는다음과같이각노드에번호를붙일수있다.

18 완전이진트리 완전이진트리 (complete binary tree): 레벨 1 부터 k-1 까지는노드가모두채워져있고마지막레벨 k 에서는왼쪽부터오른쪽으로노드가순서대로채워져있는이진트리 포화이진트리와노드번호가일치

19 이진트리의표현 배열을이용하는방법 포인터를이용하는방법

20 배열표현법 배열표현법 : 모든이진트리를포화이진트리라고가정하고각노드에번호를붙여서그번호를배열의인덱스로삼아노드의데이터를배열에저장하는방법

21 부모와자식인덱스관계 노드 i 의부모노드인텍스 = i/2 노드 i 의왼쪽자식노드인텍스 = 2i 노드 i 의오른쪽자식노드인텍스 = 2i+1

22 링크표현법 링크표현법 : 포인터를이용하여부모노드가자식노드를가리키게하는방법

23 링크의구현 노드는구조체로표현 링크는포인터로표현 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode;

24 링크표현법프로그램 #include <stdio.h> #include <stdlib.h> #include <memory.h> typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // n1 // / // n2 n3 void main() { TreeNode *n1, *n2, *n3; n1= (TreeNode *)malloc(sizeof(treenode)); n2= (TreeNode *)malloc(sizeof(treenode)); n3= (TreeNode *)malloc(sizeof(treenode));

25 n1->data = 10; // 첫번째노드를설정한다. n1->left = n2; n1->right = n3; n2->data = 20; // 두번째노드를설정한다. n2->left = NULL; n2->right = NULL; n3->data = 30; // 세번째노드를설정한다. n3->left = NULL; n3->right = NULL; }

26 이진트리의순회 순회 (traversal): 트리의노드들을체계적으로방문하는것 3 가지의기본적인순회방법 전위순회 (preorder traversal) : VLR 자손노드보다루트노드를먼저방문한다. 중위순회 (inorder traversal) : LVR 왼쪽자손, 루트, 오른쪽자손순으로방문한다. 후위순회 (postorder traversal) : LRV 루트노드보다자손을먼저방문한다.

27 전위순회 1. 루트노드를방문한다 2. 왼쪽서브트리를방문한다 3. 오른쪽서브트리를방문한다 1 루트 2 3 왼쪽서브트리 오른쪽서브트리

28 전위순회프로그램 순환호출을이용한다. preorder(x) if x NULL then print DATA(x); preorder(left(x)); preorder(right(x));

29 전위순회응용 ( 예 ) 구조화된문서출력 자료구조 1. 자료구조와알고리즘이란? 2. 기초적인자료구조 3. 고급자료구조 1.1 자료구조 1.2 알고리즘 2.1 스택 2.2 큐 2.3 리스트 3.1 트리 3.2 그래프

30 중위순회 1. 왼쪽서브트리를방문한다 2. 루트노드를방문한다 3. 오른쪽서브트리를방문한다 2 루트 1 3 왼쪽서브트리 오른쪽서브트리

31 중위순회알고리즘 순환호출을이용한다. inorder(x) if x NULL then inorder(left(x)); print DATA(x); inorder(right(x));

32 중위순회응용 ( 예 ) 수식트리

33 후위순회 1. 왼쪽서브트리를방문한다 2. 오른쪽서브트리를방문한다 3. 루트노드를방문한다 3 루트 1 2 왼쪽서브트리 오른쪽서브트리

34 후위순회알고리즘 순환호출을이용한다. postorder(x) if x NULL then postorder(left(x)); postorder(right(x)); print DATA(x);

35 후위순회응용 ( 예 ) 디렉토리용량계산

36 순회프로그램 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // 15 // 4 20 // TreeNode n1={1, NULL, NULL}; TreeNode n2={4, &n1, NULL}; TreeNode n3={16, NULL, NULL}; TreeNode n4={25, NULL, NULL}; TreeNode n5={20, &n3, &n4}; TreeNode n6={15, &n2, &n5}; TreeNode *root= &n6;

37 // 중위순회 void inorder( TreeNode *root ){ if ( root ){ inorder( root->left ); printf("%d", root->data ); inorder( root->right ); } } // 전위순회 void preorder( TreeNode *root ){ if ( root ){ printf("%d", root->data ); preorder( root->left ); preorder( root->right ); } } // 왼쪽서브트리순회 // 노드방문 // 오른쪽서브트리순회 // 노드방문 // 왼쪽서브트리순회 // 오른쪽서브트리순회

38 // 후위순회 void postorder( TreeNode *root ){ if ( root ){ postorder( root->left ); postorder( root->right ); printf("%d", root->data ); } } // 왼쪽서브트리순회 // 오른쪽서브트리순회 // 노드방문 void main() { inorder(root); preorder(root); postorder(root); }

39 레벨순회 레벨순회 (level order) 는각노드를레벨순으로 검사하는순회방법 지금까지의순회법이 스택을사용했던것에비해레벨순회는큐를사용하는순회법이다.

40 레벨순회알고리즘 level_order(root) 1. initialize queue; 2. enqueue(queue, root); 3. while is_empty(queue) TRUE do 4. x dequeue(queue); 5. if( x NULL) then 6. print DATA(x); 7. enqueue(queue, LEFT(x)); 8. enqueue(queue, RIGHT(x));

41 수식트리 수식트리 : 산술식을트리형태로표현한것 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) 예 )

42 수식트리계산 후위순회를사용 서브트리의값을순환호출로계산 비단말노드를방문할때양쪽서브트리의값을노드에저장된연산자를이용하여계산한다

43 수식트리알고리즘 evaluate(exp) 1. if exp = NULL 2. then return 0; 3. if (exp->left = NULL) and (exp->right = NULL) 4. then return exp->data; 5. x evaluate(exp->left); 6. y evaluate(exp->right); 7. op exp->data; 8. return (x op y);

44 프로그램 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // + // * + // TreeNode n1={1, NULL, NULL}; TreeNode n2={4, NULL, NULL}; TreeNode n3={'*', &n1, &n2}; TreeNode n4={16, NULL, NULL}; TreeNode n5={25, NULL, NULL}; TreeNode n6={'+', &n4, &n5}; TreeNode n7={'+', &n3, &n6}; TreeNode *exp= &n7;

45 int evaluate(treenode *root) { if( root == NULL) return 0; if( root->left == NULL && root->right == NULL) return root->data; else { int op1 = evaluate(root->left); int op2 = evaluate(root->right); switch(root->data){ case '+': return op1+op2; case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; } } return 0; } void main() { printf("%d", evaluate(exp)); }

46 디렉토리용량계산 디렉토리의용량을계산하는데후위트리순회사용

47 디렉토리용량계산프로그램 int calc_direc_size(treenode *root) { int left_size, right_size; if ( root ){ left_size = calc_direc_size( root->left ); right_size = calc_direc_size(root->right ); return (root->data + left_size + right_size); } } void main() { TreeNode n4={500, NULL, NULL}; TreeNode n5={200, NULL, NULL}; TreeNode n3={100, &n4, &n5}; TreeNode n2={50, NULL, NULL}; TreeNode n1={0, &n2, &n3}; printf(" 디렉토리의크기 =%d\n",calc_direc_size(&n1)); }

48 이진트리연산 : 노드개수 탐색트리안의노드의 개수를계산 각각의서브트리에대하여순환호출한다음, 반환되는값에 1 을더하여반환 6 int get_node_count(treenode *node) { int count=0; if( node!= NULL ) count = 1 + get_node_count(node->left) + get_node_count(node->right); return count; }

49 이진트리연산 : 높이 서브트리에대하여순환호출하고서브트리들의반환값중에서최대값을구하여반환 int get_height(treenode *node) { int height=0; if( node!= NULL ) height = 1 + max(get_height(node->left), get_height(node->right)); return height; }

50 스레드이진트리 이진트리의 NULL 링크를이용하여순환호출없이도트리의노드들을순회 NULL 링크에중위순회시에후속노드인중위후속자 (inorder successor) 를저장시켜놓은트리가스레드이진트리 (threaded binary tree) 1 2 C 3 4 G F A B D E 5 6 7

51 스레드이진트리의구현 단말노드와비단말노드의구별을위하여 is_thread 필드필요 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; // 만약오른쪽링크가스레드이면 TRUE } TreeNode;

52 스레드이진트리의구현 중위후속자를찾는함수작성 // TreeNode *find_successor(treenode *p) { // q 는 p 의오른쪽포인터 TreeNode *q = p->right; // 만약오른쪽포인터가 NULL 이거나스레드이면오른쪽포인터를반환 if( q==null p->is_thread == TRUE) return q; // 만약오른쪽자식이면다시가장왼쪽노드로이동 while( q->left!= NULL ) q = q->left; return q; }

53 스레드이진트리의구현 스레드버전중위순회함수작성 void thread_inorder(treenode *t) { TreeNode *q; q=t; while (q->left) q = q->left;// 가장왼쪽노드로간다. do { printf("%c ", q->data);// 데이터출력 q = find_successor(q); // 후속자함수호출 } while(q); // NULL 이아니면 }

54 이진탐색트리 탐색작업을효율적으로하기위한자료구조 key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) 이진탐색트리를중위순회하면오름차순으로정렬된값을얻을수있다.

55 이진탐색트리에서의탐색연산 비교한결과가같으면탐색이성공적으로끝난다. 비교한결과가, 주어진키값이루트노드의키값보다작으면탐색은이루트노드의왼쪽자식을기준으로다시시작한다. 비교한결과가, 주어진키값이루트노드의키값보다크면탐색은이루트노드의오른쪽자식을기준으로다시시작한다.

56 이진탐색트리에서의탐색연산 search(x, k) if x=null then return NULL; if k=x->key then return x; else if k < x->key then return search(x->left, k); else return search(x->right, k);

57 탐색을구현하는방법 반복적방법 순환적방법

58 순환적인방법 // 순환적인탐색함수 TreeNode *search(treenode *node, int key) { if ( node == NULL ) return NULL; if ( key == node->key ) return node; (1) else if ( key < node->key ) return search(node->left, key); (2) else return search(node->right, key); (3) }

59 반복적인방법 // 반복적인탐색함수 TreeNode *search(treenode *node, int key) { while(node!= NULL){ if( key == node->key ) return node; else if( key < node->key ) node = node->left; else node = node->right; } return NULL; // 탐색에실패했을경우 NULL 반환 }

60 이진탐색트리에서의삽입연산 이진탐색트리에원소를삽입하기위해서는먼저탐색을 수행하는것이필요 탐색에실패한위치가바로새로운노드를삽입하는위치

61 이진탐색트리에서의삽입연산 insert_node(t, z) p NULL; // 부모노드 t T; // 탐색을위한노드 while t NULL do p t; if z->key < p->key then t p->left; else t p->right; if p=null then T z; // 트리가비어있음 else if z->key < p->key then p->left z else p->right z

62 이진탐색트리에서의삽입연산 // key를이진탐색트리 root에삽입한다. // key가이미 root안에있으면삽입되지않는다. void insert_node(treenode **root, int key) { TreeNode *p, *t; // p는부모노드, t는현재노드 TreeNode *n; // n은새로운노드 t = *root; p = NULL; // 탐색을먼저수행 while (t!= NULL) { if( key == t->key ) return; p = t; if( key < t->key ) t = t->left; else t = t->right; } // 다음장에계속

63 이진탐색트리에서의삽입연산 } // key 가트리안에없으므로삽입가능 n = (TreeNode *) malloc(sizeof(treenode)); if( n == NULL ) return; // 데이터복사 n->key = key; n->left = n->right = NULL; // 부모노드와링크연결 if( p!= NULL ) if( key < p->key ) p->left = n; else p->right = n; else *root = n;

64 이진탐색트리에서의삭제연산 3 가지의경우 1. 삭제하려는노드가단말노드일경우 2. 삭제하려는노드가하나의왼쪽이나오른쪽서브트리중하나만가지고있는경우 3. 삭제하려는노드가두개의서브트리모두가지고있는경우 CASE 1: 삭제하려는노드가단말노드일경우 : 단말노드의부모노드를찾아서연결을끊으면된다.

65 이진탐색트리에서의삭제연산 CASE 2: 삭제하려는노드가하나의서브트리만갖고있는경우 : 삭제되는노드가왼쪽이나오른쪽서브트리중하나만갖고있을때, 그노드는삭제하고서브트리는부모노드에붙여준다.

66 이진탐색트리에서의삭제연산 CASE 3: 삭제하려는노드가두개의서브트리를갖고있는경우 : 삭제노드와가장비숫한값을가진노드를삭제노드위치로가져온다.

67 가장비슷한값은어디에있을까?

68 이진탐색트리에서의삭제연산 // 삭제함수 void delete_node(treenode **root, int key) { TreeNode *p, *child, *succ, *succ_p, *t; // key를갖는노드 t를탐색, p는 t의부모노드 p = NULL; t = *root; // key를갖는노드 t를탐색한다. while( t!= NULL && t->key!= key ){ p = t; t = ( key < t->key )? t->left : t->right; } // 탐색이종료된시점에 t가 NULL이면트리안에 key가없음 if( t == NULL ) { // 탐색트리에없는키 printf("key is not in the tree"); return; } // 다음장에계속

69 이진탐색트리에서의삭제연산 // 첫번째경우 : 단말노드인경우 if( (t->left==null) && (t->right==null) ) { if( p!= NULL ){ // 부모노드의자식필드를 NULL로만든다. if( p->left == t ) p->left = NULL; else p->right = NULL; } else // 만약부모노드가 NULL이면삭제되는노드가루트 *root = NULL; } // 다음장에계속

70 이진탐색트리에서의삭제연산 // 두번째경우 : 하나의자식만가지는경우 else if((t->left==null) (t->right==null)) { child = (t->left!= NULL)? t->left : t->right; if( p!= NULL ){ if( p->left == t ) // 부모를자식과연결 p->left = child; else p->right = child; } else // 만약부모노드가 NULL이면삭제되는노드가루트 *root = child; } // 다음장에계속

71 } // 세번째경우 : 두개의자식을가지는경우 else { // 오른쪽서브트리에서후계자를찾는다. succ_p = t; succ = t->right; // 후계자를찾아서계속왼쪽으로이동한다. while(succ->left!= NULL){ succ_p = succ; succ = succ->left; } // 후속자의부모와자식을연결 if( succ_p->left == succ ) succ_p->left = succ->right; else succ_p->right = succ->right; // 후속자가가진키값을현재노드에복사 t->key = succ->key; // 원래의후속자삭제 t = succ; } free(t);

72 이진탐색트리의성능분석 이진탐색트리에서의탐색, 삽입, 삭제연산의시간복잡도는트리의높이를 h 라고했을때 h 에비례한다

73 이진탐색트리의성능분석 최선의경우 이진트리가균형적으로생성되어있는경우 h=log 2 n 최악의경우 한쪽으로치우친경사이진트리의경우 h=n 순차탐색과시간복잡도가같다.