슬라이드 1

Transcription

1 Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University

2 트리의개념

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

4 트리예시 - 회사의조직 대표이사 총무부 영업부 생산부 총무부영업부생산부 전산팀구매팀경리팀생산1 팀생산2 팀 4

5 트리예시 파일디렉토리구조 나의문서 받은파일음악그림 정지영상 동영상 5

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

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

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

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

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

11 이진트리의소개

12 이진트리 (binary tree) Textbook 이진트리 서브트리는공집합 ( 단말노드 ) 일수있음 이진트리의노드에는최대 2개까지의자식노드가존재 모든노드의차수가 2 이하가됨 구현하기가편리함 이진트리에는서브트리들이구별됨 A T left T right 12

13 이진트리 (binary tree) 정의 : BT(Binary Tree) (1) a root (internal node or terminal node) (2) LBT(Left sub-bt) (3) RBT(Right sub-bt) A T left T right 13

14 이진트리검증 이진트리는공집합이거나 루트와왼쪽서브트리, 오른쪽서브트리로구성된노드들의유한집합 으로정의됨, 이진트리의서브트리들은모두이진트리여야함 SUB1 A SUB2 B C SUB3 공집합공집합공집합 D 공집합 공집합 14

15 이진트리의성질 노드의개수가 n 개이면간선의개수는 n-1 + 노드의개수 : 7 간선의개수 : 6 * / a b c d 15

16 이진트리의성질 높이가 h 인이진트리의경우, 최소 h 개의노드를가지며최대 2 h 1 개의노드를가짐 = 2 높이 = 3 * * / = 2 a a b c d = 2 최소노드개수 = 3 최대노드개수 = = = 7 16

17 이진트리의성질 n 개의노드를가지는이진트리의높이 최대 n 최소 log 2 (n + 1) 높이 = 높이 = (a) 최대높이 (b) 최소높이 17

18 이진트리의분류 포화이진트리 (full binary tree) 완전이진트리 (complete binary tree) 기타이진트리 A A A B C B C B C D E F G D E F G D E F G H I J I (a) 포화이진트리 (b) 완전이진트리 (c) 기타이진트리 18

19 포화이진트리 포화이진트리 (full binary tree) 정의 : 트리의각레벨에노드가꽉차있는이진트리 전체노드개수 : k 1 = k 1 i=0 2 i = 2 k 1 포화이진트리에서노드의번호

20 완전이진트리 완전이진트리 (complete binary tree) 정의 : 높이가 k 일때레벨 1 부터 k-1 까지는노드가모두채워져있고, 마지막레벨 k 에서는왼쪽부터오른쪽으로노드가순서대로채워져있는이진트리 중간에빈곳이있어서는안됨 포화이진트리와노드번호가일치 (a) 완전이진트리 (a) 완전이진트리가아님 20

21 이진트리의표현

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

23 배열표현법 배열표현법 모든이진트리를포화이진트리라고가정하고각노드에번호를붙여서그번호를배열의인덱스로삼아노드의데이터를배열에저장하는방법 1 A 2 3 B C D E F (a) 완전이진트리 0 1 A 2 B 3 C 4 D 5 E 6 F D 1 A 2 B 4 C (a) 경사이진트리 0 1 A 2 B 3 4 C D 23

24 부모와자식인덱스관계 노드 i 의부모노드인덱스 = i/2 노드 i 의왼쪽자식노드인덱스 = 2i 노드 i 의오른쪽자식노드인덱스 = 2i A 2 3 B C D E F 0 1 A 2 B 3 C 4 D 5 E 6 F

25 링크표현법 링크표현법 포인터를이용하여부모노드가자식노드를가리키게하는방법 완전이진트리 A A B C B C NULL D E F NULL D NULL NULL E NULL NULL F NULL 경사이진트리 A A B B C C NULL D NULL D NULL 25

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

27 링크표현법프로그램 (1/2) #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)); 27

28 링크표현법프로그램 (2/2) n1->data = 10; // 첫번째노드를설정한다. n1->left = n2; n1->right = n3; n2->data = 20; // 두번째노드를설정한다. n2->right = NULL; n3->data = 30; // 세번째노드를설정한다. n3->right = NULL; } 28

29 이진트리의순회

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

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

32 전위순회알고리즘 순환호출을이용 preorder(x) if x NULL then print DATA(x); preorder(left(x)); preorder(right(x)); 32

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

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

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

36 중위순회응용 예 ) 수식트리 * / 6 1 a b c d 36

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

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

39 후위순회응용 예 ) 디렉토리용량계산 5 나의문서 1 음악 50KB 그림 4 100KB KB 500KB 정지영상 동영상 39

40 순회프로그램 (1/3) 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; 40

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

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

43 레벨순회 각노드를레벨순으로검사하는순회방법 지금까지의순회법이스택을사용했던것에비해레벨순회는 큐를사용하는순회법 * / / A B 2 * / 3 A B C D B C D 4 A B 5 6 C D 7 C D D 43

44 레벨순회알고리즘 level_order(root) 1. initialize queue; 2. if(root=null) then return; 3. enqueue(queue, root); 4. while is_empty(queue) TRUE do 5. x dequeue(queue); 6. print DATA(x); 7. if(x->left!= NULL) then 8. enqueue(queue, x->left); 9. if(x->right!= NULL) then 10. enqueue(queue, x->right); 44

45 수식트리 수식트리 : 산술식을트리형태로표현한것 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) 예 ) + - or a b a < < b c a b c d 수식 a + b a - (b c) (a < b) or (c < d) 전위순회 + a b - a b c or < a b < c d 중위순회 a + b a - b c a < b or c < d 후위순회 a b + a b c - a b < c d < or 45

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

47 수식트리알고리즘 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); 47

48 프로그램 (1/2) 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; 48

49 프로그램 (2/2) 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)); } 49

50 디렉토리용량계산 디렉토리용량을계산하는데후위트리순회사용 나의문서 음악 50KB 그림 100KB 200KB 500KB 정지영상 동영상 50

51 디렉토리용량계산프로그램 int calc_direc_size(treenode *root) { } void main() { } int left_size, right_size; if ( root ) { } left_size = calc_size( root->left ); right_size = calc_size(root->right ); return (root->data + left_size + right_size); 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)); 51

52 이진트리의연산

53 이진트리연산 : 노드의개수 탐색트리안의노드의개수를계산 각각의서브트리에대하여순환호출한다음, 반환되는값에 1 을더하여반환 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;

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

55 스레드이진트리

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

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

58 스레드이진트리의구현 (2/3) 중위후속자를찾는함수작성 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; 58

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

60 이진탐색트리

61 이진탐색트리 정의 : 이진탐색트리의성질을만족하는이진트리 이진탐색트리의성질 모든노드의키는유일 key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) 왼쪽과오른쪽서브트리도이진탐색트리 이진탐색를중위순회하면오름차순으로정렬된값을얻을수있음 루트 왼쪽서브트리 오른쪽서브트리 루트보다작은값루트보다큰값루트보다작은값루트보다큰값 27 61

62 이진탐색트리의탐색연산 (1/2) 탐색연산 비교한결과가같으면탐색이성공적으로끝남 비교한결과가, 주어진키값이루트노드의키값보다작으면탐색은이루트노드의왼쪽자식을기준으로다시시작함 비교한결과가, 주어진키값이루트노드의키값보다크면탐색은이루트노드의오른쪽자식을기준으로다시시작함 탐색

63 이진탐색트리의탐색연산 (2/2) 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); 탐색

64 탐색을구현하는방법 순환적방법 TreeNode *search(treenode *node, int key) { if ( node == NULL ) return NULL; if ( key == node->key ) return node; else if ( key < node->key ) return search(node->left, key); else return search(node->right, key); } 반복적방법 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 반환 } 64

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

66 삽입연산알고리즘 insert_node(t,z) p NULL; t root; while t NULL do p t; if z->key < p->key then t p->left; else t p->right; z make_node(key); if p=null then root z; else if z->key < p->key then p->left z else p->right z // 트리가비어있음 66

67 삽입연산프로그램 (1/2) // 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 < p->key ) t = p->left; else t = p->right; } 67

68 삽입연산프로그램 (2/2) } // 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; 68

69 이진탐색트리에서의삭제연산 삭제연산 3 가지의경우 삭제하려는노드가단말노드일경우 삭제하려는노드가왼쪽이나오른쪽서브트리중하나만가지고있는경우 삭제하려는노드가두개의서브트리모두가지고있는경우 69

70 삭제연산 단말노드삭제 CASE 1 : 삭제하려는노드가단말노드일경우 단말노드의부모노드를찾아서연결을끊는다

71 삭제연산 서브트리를하나가지고있는노드삭제 CASE 2 : 삭제하려는노드가하나의서브트리만갖고있는경우 삭제할노드는삭제하고그노드의서브트리는부모노드에붙여준다

72 삭제연산 두개의서브트리를가지고있는노드삭제 CASE 3 : 삭제하려는노드가두개의서브트리를갖고있는경우 삭제할노드를삭제하고삭제노드의후계자노드값을삭제된노드위치로가져온다 왼쪽서브트리에서제일큰값 오른쪽서브트리에서제일작은값 72

73 삭제함수코드 (1/4) // 삭제함수 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; } 73

74 삭제함수코드 (2/4) // 첫번째경우 : 단말노드인경우 if( (t->left==null) && (t->right==null) ) { if( p!= NULL ) { // 부모노드의자식필드를 NULL 로만든다. if( p->left == t ) p->left = NULL; else p->right = NULL; } } // 만약부모노드가 NULL이면삭제되는노드가루트 else *root = NULL; 74

75 삭제함수코드 (3/4) // 두번째경우 : 하나의자식만가지는경우 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; 75

76 삭제함수코드 (4/4) // 세번째경우 : 두개의자식을가지는경우 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); } 76

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

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