Ch.1 Introduction

Transcription

1 Tree & Heap SANGJI University Kwangman Ko

2 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2

3 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조 ~ 배열 탐색은빠르지만 O(logN), 삽입 / 삭제는느림 (O(N)) ~ 연결리스트 삽입 / 삭제는빠르지만 (O(1)), 탐색은느림 (O(N)) ~ 트리 삽입과삭제, 탐색이모두빠름 (O(logN)) kkman@sangji.ac.kr 3

4 트리에서자주사용하는용어 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드, 아래있는노드를자식노드. 경로 (path) ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. 키 (key) ~ 자료항목을찾거나또는다른동작을하기위해필요한값 ~ 각자료항목을구분해주는역할, 자료항목을대표하는값 kkman@sangji.ac.kr 4

5 A B C D E F G H I J kkman@sangji.ac.kr 5

6 6

7 트리의일반적인성질 한노드에서다르노드로가는경로가유일 ~ 임의의두노드에대해최소공통선조 (least common ancestor) 를갖음. 두노드가가질수있는가장가까운선조 ~ 경로가중복되지않는다면두노드간의경로는반드시한노드에서최소공통선조까지올라갔다다른노드로내려오는유일한경로만이존재. N 개의노드를갖는트리는 N-1 개의링크. ~ 그래프와달리루트를제외하고는모든노드가자신의선조를향한하나의링크를가지고있음. ~ N 개의노드를가진트리는 N-1 개의링크를갖음. kkman@sangji.ac.kr 7

8 2. 이진트리 이진트리 (binary tree) ~ 트리구조중자식을최대둘까지가질수있는트리 ~ 모든노드의차수가 2 이하 구현하기가편리함 ~ 모든노드가 2 개의서브트리를가지고있는트리 ~ 서브트리는공집합일수있음. ~ 이진트리에는서브트리간의순서가존재 ~ 각노드들은자식이없거나, 하나또는두개의자식노드를유지 ~ 가장보편적인트리구조, 이진탐색트리 (binary search tree) kkman@sangji.ac.kr 8

9 특징 ~ 왼쪽자식 (left child), 오른쪽자식 (right child). ~ 루트키 (key) 값 왼쪽자식노드의키값보다크다. 오른쪽자식노드의키값보다작다. 50 < < kkman@sangji.ac.kr 9

10 노드의개수가 n 개 ~ 간선 (edge) 의개수는?? ~ n-1 A B C D E F G kkman@sangji.ac.kr 10

11 높이가 h 인이진트리 ~ 최소 h 개의노드 ~ 최대 2 h -1 개의노드 kkman@sangji.ac.kr 11

12 n 개의노드를가지는이진트리높이 ~ 최대 n, 최소 log 2 (n+1) kkman@sangji.ac.kr 12

13 완전이진트리 (complete binary tree) ~ 마지막레벨을제외한각레벨의노드들이모두차있고, 마지막레벨에서는노드들이순서대로존재하는상태 포화이진트리 (full binary tree) ~ 모든레벨이꽉찬이진트리 kkman@sangji.ac.kr 13

14 이진트리에서노드번호 kkman@sangji.ac.kr 14

15 3. 이진트리구현 배열표현법 ~ 모든이진트리를포화이진트리라고가정 ~ 각노드에번호부여, 그번호를배열의인덱스 B 1 A D E F G C A B C D E F G kkman@sangji.ac.kr 15

16 배열구현법에서인덱스결정 ~ 노드 i의부모노드인덱스 : i/2 ~ 노드 i의왼쪽자식노드인덱스 : 2i ~ 노드 i의오른쪽자식노드인덱스 : 2i+1 경사이진트리 A B C D E kkman@sangji.ac.kr 16

17 연결리스트표현법 ~ 노드의링크를이용하여부모노드가자식노드를가리키게 ( 포인팅 ) 하는방법 1 A A 2 3 B C B C F D E F G kkman@sangji.ac.kr 17

18 노드구조 (in C) ~ 구조체로구현 ~ 각노드가포인터 (= 링크 ) 를가지고있어노드와노드를연결 typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } kkman@sangji.ac.kr 18

19 4. 트리순회 (traverse) 순회 (traversal) ~ 트리의노드들을일정한순서로방문 순회방법 ~ 전위순회 (preorder traversal), VLR. ~ 루트노드, 왼쪽자손, 오른쪽자손노드순서로방문 ~ 중위순회 (inorder traversal), LVR. ~ 왼쪽자손, 루트, 오른쪽자손노드순서로방문 ~ 후위순회 (postorder traversal), LRV. ~ 왼쪽자손, 오른쪽자손, 루트노드순서로방문 kkman@sangji.ac.kr 19

20 V A L R B C D E F G kkman@sangji.ac.kr 20

21 전위순회 (Preorder Traverse) ~ 루트를먼저방문하는순회방법 1. 루트노드. 2. 왼쪽서브트리. 3. 오른쪽서브트리. preorder( TreeNode *root ){ if ( root ){ printf("%d", root->data ); // 노드방문 preorder( root->left ); // 왼쪽하위트리 preorder( root->right ); // 오른쪽하위트리 } } kkman@sangji.ac.kr 21

22 전위방문순서?? kkman@sangji.ac.kr 22

23 중위순회 (Inorder Traverse) ~ 왼쪽서브트리 -> 루트 -> 오른쪽서브트리순서로방문 1. 왼쪽서브트리방문. 2. 루트노드방문. 3. 오른쪽서브트리. inorder( TreeNode *root ){ if ( root ){ inorder( root->left ); printf("%d", root->data ); inorder( root->right ); } } // 왼쪽서브트리 // 루트노드 // 오른쪽서브트리 kkman@sangji.ac.kr 23

24 a * b + c / d + a * b c / d * / a b c d kkman@sangji.ac.kr 24

25 kkman@sangji.ac.kr 25

26 후위순회 (Postorder Traverse) ~ 왼쪽서브트리-> 오른쪽서브트리 -> 루트노드순으로방문 1. 왼쪽서브트리방문. 2. 오른쪽서브트리방문. 3. 루트노드방문. postorder( TreeNode *root ){ if ( root ){ postorder( root->left ); // 왼쪽서브트리 postorder( root->right ); // 오른쪽서브트리 printf("%d", root->data ); // 루트노드 } } kkman@sangji.ac.kr 26

27 kkman@sangji.ac.kr 27

28 28

29 수식트리 (evalaution tree) ~ 산술식을트리형태로표현한것 비단말노드 : 연산자 (operator) 단말노드 : 피연산자 (operand) kkman@sangji.ac.kr 29

30 + 수식 전위순회 a + b + a b a b 중위순회 a + b 후위순회 a b + kkman@sangji.ac.kr 30

31 - 수식 a - (b c) a * 전위순회 중위순회 b c 후위순회 kkman@sangji.ac.kr 31

32 이진트리연산 노드개수 ~ 탐색트리안의노드의개수를계산 ~ 각서브트리에대하여순환호출한다음, 반환되는값에 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; } kkman@sangji.ac.kr 32

33 트리높이구하기 ~ 서브트리에대하여순환호출 ~ 서브트리들의반환값중에서최대값을구하여반환 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; } kkman@sangji.ac.kr 33

34 스레드 (thread) 이진트리 정의및특징 ~ 이진트리의 NULL 링크를이용하여순환호출없이도트리의노드들을순회 ~ NULL 링크에중위순회시에후속노드인중위후속자를저장시켜놓은트리 ~ 단말노드와비단말노드의구별을위히여 is_thread 필드필요 kkman@sangji.ac.kr 34

35 이진트리탐색 이진트리 (binary tree) ~ 모든원소의키는유일 ~ 왼쪽서브트리의키값들은루트의키값보다작다. ~ 오른쪽서브트리의키값들은루트의키값보다크다. ~ 왼쪽과오른쪽서브트리도이진트리특성유지. kkman@sangji.ac.kr 35

36 이진트리에서탐색 (search) ~ 어떤주어진키를가지고그키와동일한값을갖는노드를찾는것. ~ 루트노드부터방문하여노드의키값과주어진키값을비교하여내려가는식으로진행. 이진트리의탐색특징 ~ 탐색작업을효율적으로하기위한자료구조 ~ key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) ~ 이진탐색를중위순회하면오름차순으로정렬. kkman@sangji.ac.kr 36

37 루트 왼쪽서브트리 오른쪽서브트리 루트보다작은값 루트보다큰값 kkman@sangji.ac.kr 37

38 탐색 (search) ~ 어떤주어진키를가지고그키와동일한값을갖는노드를찾는것. ~ 루트노드부터방문하여노드의키값과주어진키값을비교하여내려가는식으로진행. Public Node find(int key) { } Node current = root; while (current.keydata!= key) { } if (current == null) return null; if (key < current.keydata) else current = current.leftchild; current = current.rightchild; return current; kkman@sangji.ac.kr 38

39 특징 ~ 탐색작업을효율적으로하기위한자료구조 ~ key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) ~ 이진탐색를중위순회하면오름차순으로정렬 kkman@sangji.ac.kr 39

40 알고리즘 ~ 비교한결과가같으면탐색성공. ~ 주어진키값이루트노드의키값보다작으면탐색은이루트노드의왼쪽자식을기준으로다시시작. ~ 주어진키값이루트노드의키값보다크면탐색은이루트노드의오른쪽자식을기준으로다시시작. kkman@sangji.ac.kr 40

41 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); 41

42 42

43 최대값과최소값탐색 ~ 현노드보다작은값은왼쪽자식에, 큰값은오른쪽자식에위치. 최소값 : 트리의가장왼쪽 ~ 루트에서왼쪽자식을따라내려가면서더이상왼쪽자식이없는노드를만나면그노드가최소값을가진노드. 최대값 : 트리의가장오른쪽에존재 ~ 최대값은오른쪽자식을따라가면찾을수있다. kkman@sangji.ac.kr 43

44 44

45 이진트리에서삽입 방법 ~ 노드가삽입될위치탐색. ~ 적절한경로를따라내려간뒤그위치의부모가되는노드탐색 ~ 삽입될위치의부모노드의키보다삽입될노드의키가작다면부모노드의왼쪽자식으로, 크다면부모노드의오른쪽자식으로생성. kkman@sangji.ac.kr 45

46

47 47

48 이진트리에서삭제 삭제노드가단말노드일경우 삭제노드가하나의왼쪽이나오른쪽서브트리중하나만가지고있는경우 ~ 삭제하려는노드의자식노드가하나일때 삭제하려는노드가두개의서브트리모두가지고있는경우 ~ 삭제하려는노드의자식노드가둘일때 kkman@sangji.ac.kr 48

49 1. 삭제하려는노드의자식이없을경우 ~ 단말노드삭제 ~ 삭제노드의부모노드에게서삭제노드를가리키는링크를 null kkman@sangji.ac.kr 49

50 단말노드의부모노드를찾아서연결을삭제 (null)

51 2. 삭제하려는노드의자식이하나일때 ~ 삭제하려는노드의자식노드와부모노드를바로연결.

52

53 3. 삭제하려는노드의자식이둘일때 ~ 삭제하려는노드의자식중하나로그위치를대체할수없음 ~ 삭제될노드의위치를채워줄후보노드선정. 후보노드 (candidate node) ~ 삭제될노드의키값보다바로위의키값을가진노드나바로아래의키값을가진값을후보노드로선택.

54 후보노드선정 1 ~ 삭제될노드보다큰값을갖는 ( 오른쪽 ) 서브트리선택. ~ 서브트리에서가장작은값을갖는노드를후보노드로지정.

55 후보노드선정 2 ~ 삭제될노드보다작은값을갖는 ( 왼쪽 ) 서브트리선택. ~ 서브트리에서가장큰값을갖는노드를후보노드로지정.

56 후보노드가삭제노드의오른쪽자식일경우 ~ 부모노드에서삭제노드에대한링크절단 ~ 후보노드로링크를연결. ~ 삭제노드의왼쪽자식은삭제노드와의링크절단, 후보노드의왼쪽자식으로링크.

57 후보노드가삭제노드의오른쪽자식의왼쪽자손일경우 ~ 후보노드의오른쪽자식 후보노드의부모노드에대한왼쪽자식노드로저정 ~ 삭제노드의오른쪽자식 후보노드의오른쪽자식으로지정. ~ 부모노드에서삭제노드에대한링크절단, 후보노드로연결 ~ 삭제노드의왼쪽자식 삭제노드와의링크를끊고후보노드의왼쪽자식으로연결

58

59

60 힙 (heap) ~ 우선순위큐와비슷한구체적인자료구조, 완전이진트리 ~ 우선순위설정방법, 우선순위높은자료추출등의방법포함 ~ 큐자료중우선순위가가장높은자료를선택

61 종류 ~ 최대히프 (max heap) 부모노드의키값이자식노드의키값보다크거나같은완전이진트리 key( 부모노드 ) key( 자식노드 ) ~ 최소히프 (min heap) 부모노드의키값이자식노드의키값보다작거나같은완전이진트리 key( 부모노드 ) key( 자식노드 ) kkman@sangji.ac.kr 61

62

63 이진힙 (binary heap) 이진힙조건 ~ 조건 1 : 완전이진트리 (complete binary tree) 구조. ~ 조건 2 : 부모노드는두자식노드보다우선순위가높다.

64 힙의구현방법 배열을이용한힙구현 ~ 완전이진트리의각노드에번호를부여. ~ 부연된번호를배열의인덱스로간주 왼쪽자식의인덱스 = ( 부모의인덱스 )*2 오른쪽자식의인덱스 = ( 부모의인덱스 )*2 + 1 부모의인덱스 = ( 자식의인덱스 )/2

65

66 완전이진트리의구현 ~ 배열을이용한레벨순서순회방법

67 배열, 부모노드와자식노드관계 ~ 왼쪽자식 = 부모노드 * ~ 오른쪽자식 = 부모노드 * ~ 부모노드 = ( 왼쪽자식 1) / 2 ~ 부모노드 = ( 오른쪽자식 2) / 2

68 힙구현 : 삽입연산 개념 ~ 회사에서신입사원이들어오면일단말단위치에앉힌다음에, 신입사원의능력을봐서위로승진시키는것과비숫 히프에새로운요소가들어오면, 일단새로운노드를히프의마지막노드에이어서삽입 삽입후에새로운노드를부모노드들과교환해서히프의성질을만족

69 조건 ~ 적어도삽입과삭제의두가지메소드필요 ~ 자료의삽입시자료의위치를바꿔트리의루트에우선순위가가장높은노드를확보 이진힙삽입알고리즘 ~ 단계 1. 삽입할자료를트리의마지막위치에넣는다. ~ 단계 2. 부모노드와우선순위를비교하여계속반복 부모노드의우선순위가더높을경우, 삽입종료 부모노드의우선순위가더낮을경우, 부모노드와교환 한뒤비교를계속 트리의루트가되면삽입동작종료.

70

71

72 입력순서 : 5, 3, 8, 14, 4, 16, 1, 10, 11, 2, 6, 20

73

74

75

76

77 힙구현 : 삭제연산 개념 ~ 최대히프에서의삭제는가장큰키값을가진노드를삭제 ~ 회사에서사장의자리가비게되면먼저제일말단사원을사장자리로올린다음에, 능력에따라강등시키는것과비숫. 루트노드를삭제, 마지막노드를루트노드로이동 루트에서부터단말노드까지의경로에있는노드들을교환하여힙성질만족.

78 이진힙삭제알고리즘 ~ 단계 1. 루트노드삭제 ~ 단계 2. 힙의마지막노드를루트노드자리로이동 ~ 단계 3. 자식노드들과우선순위를비교 3-1. 두자식노드의우선순위가더낮을경우, 삭제종료 3-2. 우선순위가더높은자식노드가있을경우, 두자식노드중우선순위가더높은노드와교환한뒤다시비교 3-3. 자식을갖지않는잎 (leaf) 노드가될경우, 삭제종료

79

80

81

82 응용 : 힙정렬 (Heap sort) 개요 ~ 삭제를수행할때마다우선순위가가장높은루트노드를반환 ~ 반환받은노드를별도의배열에순서대로저장하여정렬수행 ~ 단점 힙에사용된배열외에별도의메모리필요 비교적느린속도 효율적인메모리관리 ~ 삭제된자료를별도의배열에저장하는것이아니라, ~ 힙에서삭제되면서생긴빈공간에기록

83

84