Microsoft PowerPoint - chap10_tree

Transcription

1 Chap. 10 : Tree 2007 학년도 2 학기

2 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-

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

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

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

6 하위트리 (subtree) ~ 하나의큰트리에속해있는부분트리. 방문 (visiting) ~ 노드에도착해노드의자료값을읽는행위. 순회 (traversing) ~ 트리의노드전체를방문하는행위. 레벨 (level) ~ 어떤노드의레벨은루트노드로부터얼마나많이떨어졌는지를의미 ~ 여기에서는루트를레벨 1 로가정. 높이 (height) ~ 높이는최장루트 - 잎경로의길이이다. -6-

7 노드 (node) ~ 트리의구성요소 루트 (root) ~ 부모가없는노드 (A) 서브트리 (subtree) ~ 하나의노드와그노드들의자손들로이루어진트리 단말노드 (leaf node) ~ 자식이없는노드 (A,B,C,D) 비단말노드 ~ 적어도하나의자식을가지는노드 (E,F,G,H,I,J) 레벨 (level) ~ 트리의각층의번호 높이 (height) ~ 트리의최대레벨 (3) 차수 (degree) ~ 노드가가지고있는자식노드의개수 A B C D E F G H I J -7-

8 -8-

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

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

11 특징 4.1 생김새 ~ 왼쪽자식 (left child), 오른쪽자식 (right child). ~ 왼쪽자식의키 (key) 는부모노드의키보다작고, 오른쪽자식의키는부모노드의키보다크다. -11-

12 노드의개수가 n 개이면간선의개수는 n-1-12-

13 높이가 h 인이진트리 ~ 최소 h 개의노드 ~ 최대 2 h -1 개의노드 -13-

14 n 개의노드를가지는이진트리의높이 ~ 최대 n, 최소 log 2 (n+1) -14-

15 완전이진트리 (complete binary tree) ~ 마지막레벨을제외한각레벨의노드들이모두차있고, 마지막레벨에서는노드들이순서대로존재하는상태 꽉찬이진트리 (full binary tree) ~ 모든레벨이꽉찬이진 v 트리 -15-

16 -16-

17 배열표현법 4.2 이진트리구현 ~ 모든이진트리를포화이진트리라고가정 ~ 각노드에번호부여, 그번호를배열의인덱스 -17-

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

19 노드클래스 노드클래스 in Java ~ 노드의키값이저장될공간과두자식에대한참조변수로구성 class Node { public int keydata; public Node leftchild; public Node rightchild; } } public void shownode() { System.out.print( [ ); System.out.print(keyData); System.out.print( [ ); -19-

20 트리클래스 in Java class BinaryTree { private Node root; } public void tracerse() { } public Node find(int key) { } public void insert(int key) { } public boolean delete(int key) { } -20-

21 4.3 트리순회 (traverse) 순회 (traversal) ~ 트리의노드들을체계적으로방문하는것 순회방법 ~ 전위순회 (preorder traversal), VLR ~ 자손노드보다루트노드를먼저방문. ~ 중위순회 (inorder traversal), LVR ~ 왼쪽자손, 루트, 오른쪽자손노드순서로방문. ~ 후위순회 (postorder traversal), LRV ~ 루트노드보다자손노드를먼저방문. -21-

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

23 -23-

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

25 * / a b c d -25-

26 -26-

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

28 -28-

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

30 수식 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 -30-

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

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

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

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

35 -35-

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

37 pubilc Node findmin() { Node current = root; while (current.leftchild!= null) current = current.leftchild; return current; } public Node findmax() { Node current = root; while (current.rightchild!= null) current = current.rightchild; return current; } -37-

38 -38-

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

40 -40-

41 BT insert in C 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; if p=null then root z;// 트리가비어있음 else if z->key < p->key then p->left z else p->right z -41-

42 BT insert in Java public void insert(int key) { Node insertnode = new Node(); insertnode.keydata = key; if (root == null) root = insertnode; else { Node current = root, parent; while(true) { parent = current; if (key < current.keydata) { current = current.leftchild; if (current == null) { parent.leftchild = insertnode; return; } } else { current = current.rightchild; if (current == null) { parent.rightchild = insertnode; return; } } } } } -42-

43 3 가지의경우 4.5 이진트리에서삭제 ~ 삭제하려는노드가단말노드일경우 ~ 삭제하려는노드가하나의왼쪽이나오른쪽서브트리중하나만가지고있는경우 삭제하려는노드의자식노드가하나일때 ~ 삭제하려는노드가두개의서브트리모두가지고있는경우 삭제하려는노드의자식노드가둘일때 -43-

44 1. 삭제하려는노드의자식이없을때, 단말노드삭제 ~ 삭제노드의부모노드에게서삭제노드를가리키는링크를 null If (current.leftchild == null && current.rightchild == null) { if (current == root) root = null; else if (current == parent.leftchild) parent.leftchild = null; else parent.rightchild = null; } -44-

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

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

47 -47-

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

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

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

51 삭제하려는노드의자식이둘일때 ~ 잘못된대체의예 -51-

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

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

54 -54-

55 -55-

56 특징 4.7 효율성 ~ 트리연산은하위레벨로의탐색을포함. ~ 꽉찬트리에서노드의반정도가맨아래레벨에존재. ~ 노드들에대한연산 ( 삽입, 삭제등 ) 은최하위레벨에있는노드까지찾는연산을필요로함 ~ 탐색하는동안최소한하나의레벨에하나의노드를방문 ~ 어떠한연산을하는데걸리는시간은트리의레벨에따라유추 노드의수를 N, 레벨의수를 L ~ L = log 2 (N + 1) -56-