Microsoft PowerPoint - Chap5 [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chap5 [호환 모드]"

정 선우
5 years ago
Views:

1 데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호

2 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs hapter 07: Sorting hapter 08: Hashing hapter 09: Heap Structures hapter 10: Search Structures Special Lecture : Index Structures for Multimedia 2

3 hapter 5 -Trees- 5.1 Introduction 5.2 inary Trees 5.3 inary Tree Traversal 5.4 dditional inary Tree Operations 5.5 Threaded inary Trees 5.6 Heaps 5.7 inary Search Trees 5.8 Selection Trees 5.9 Forests 5.10 ( 생략 ) Set Representation 5.11 ( 생략 ) ounting inary Trees

4 efinition:: tree 5.1 Introduction Tree 는다음의성질을가진하나이상의 node 로이루어진 finite set 이다. Root 라고불리우는특정 node 가있다. 나머지 node 들은 n 개 (n 0) 의 disjoint set 인 T 1, T 2, T n 으로분할된다. 이때, 각 set 은 tree 이다. T 1, T 2, T n 를 root 의 subtree 라고부른다. Tree 는 root 를가진 acyclic graph( 비순환그래프 ) 이고, 계층적구조를가진다. subtre e subtree 의 root Honey ear usty Root subtree 의 root randy subtre e runhilde Terry oyote Nugget Gill Tansey Tweed Zoe rosus Primrose Nous elle Figure 5.1: Pedigree 4

5 Figure 5.2. Sample Tree Level E F G H I J Node 의 degree node 의 subtree 수를말한다., 는 3, E 는 2, H 는 1 K, F, G, M, I, J 는 0 Tree 의 degree tree 에있는 node 의 degree 중최대값 예 : 왼쪽 tree 의 degree 는 3 이다 4 K L M Leaf (terminal node) degree 가 0 인 node 를일컫는다. Figure 5.2. Tree 예 : 왼쪽 tree 에서 leaf 는 K, L, F, G, M, I, I 이다. 5

6 Figure 5.2. Sample Tree 계속 K E F G H I J L Tree 의 height (depth) Tree 에있는 node 의최대 level 값이다. M 상기 tree 의 height 는 4 이다. Parent node Subtree 를갖는 node 는그 subtree 들의 parent 이다. hildren nodes Parent 를갖는 subtree 들의 root 들은그 parent node 의 children 이다. Sibling nodes 같은 parent 의 children 을말한다. Grand parent node Parent 의 parent Grand children nodes hildren 의 children ncestor nodes 한 node 의 ancestor 는 root 에서그 node 까지의 path 상에있는모든 node 들 예 : M 의 ancestor 는,, H escendents nodes 한 node 의 descendents 는그 node 의 subtree 에있는모든 node 들 예 : 의 descendents 는 E, F, K, L 6

7 5.1.2 Tree 의표현방법 List 로표현하는방법 Figure 5.2 의 tree 를 inorder navigation 하여그결과 list 로표현하면, ( ( (E (K,L), F), (G), (H (M),I,J) ) ) 단, root 를먼저쓰고, subtree 의 list 를나중에쓴다. Linked list 구조를이용하여 tree 를표현하는경우문제점 한 node 에있는 field 수는 branch 의개수에따라변하기때문에 node structure 구현이힘들다. 다음과같이 n 개의 child 마다각각하나의 link 를둔다. data link 1 link 2 link n 7

8 5.1.2 Tree 의표현방법 ( 계속 ) Left hildren-right Sibling Tree 표현방법 고정된크기의 node 구조를사용한다. 그러므로, 연산 (operation) 이쉽다. 다음그림과같이, Node 마다두개의 link 또는 pointer field를가진다. 데이터 (data) left child link right sibling link 아래 Figure 5.3 은 5 page 의 Figure 5.2 에대한 left child-right sibling 표현법임 E F G H I J Figure 5.3. Left hildren-right Sibling 표현 K L M 8

9 5.1.2 Tree 의표현방법 ( 계속 ) egree Two Tree Representation 일명, left child-right child tree, 또는 binary tree 라고한다. E left child-right sibling tree 를 45 도시계방향으로회전시킨모양이다. K F G 한 node 의 children 을 left child 와 right child 로구분한다. L M H I 오른쪽에있는 Figure 5.4 는 Figure 5.2 의 left child-right child 표현을 binary tree 로의변환표현이다. Figure 5.4 binary tree J 9

10 5.1.2 Tree 의표현방법 ( 변환과정 ) E F G tree E F G binary tree E F G left child-right sibling tree 10

11 Figure 5.5: Tree 표현법비교정리 tree left child-right sibling tree binary tree tree left child-right sibling tree binary tree 11

12 이진트리의정의 이진트리는 empty 이거나, 5.2 inary Trees root 와 2 개의 disjoint binary tree(left subtree 와 right subtree) 로구성된다. T(bstract ata Type) on inary_tree struct inary_tree (abbreviated intree) is objects: a finite set of nodes either empty or consisting of a root node, left inary_tree, and inary_tree. functions: for all bt, bt1, bt2 inary Tree, item element intree reate ( ) ::= create an empty binary tree oolean IsEmpty (bt) ::= if (bt == empty binary tree) return TRUE else return FLSE intree MakeT (bt1, item, bt2) ::= return a binary tree whose left subtree is bt1, whose right subtree is bt2, and whose root node constraints the data item. intree Lchild (bt) ::= if (IsEmpty(bt)) return error else return the left subtree of bt intree Rchild (bt) ::= if (IsEmpty(bt)) return error else return the data in the root node of bt element ata (bt) ::= if (IsEmpty(bt)) return error else return the right subtree of bt 12

13 inary Tree 의비교 0 개의 node 를가진 tree 는없지만, empty binary tree 는존재한다. inary tree 에서는 children 의 order 를구분하지만, tree 에서는구분하지않는다. 다음의 2 개의 binary tree 는다르다. 13

14 Figure 5.6. Skewed tree 와 complete tree 의비교 E F G E H I skewed binary tree complete binary tree 14

15 이진 (binary) 트리의특성 (1) Lemma 5.2 :: node 의최대개수 (p.214) inary tree 의 level i 에있는 node 의최대개수는 2 i-1 이다 (i 1) 깊이 (depth) k 의 binary tree 에있는 node 의최대개수는 2 k -1 이다 (k 1) ( 증명 ) 1. level i 에대한 introduction 에의하여, induction base: i=1 인경우를따져본다. 즉, root 가유일한 node 인경우, i=1 이고, 이때, 2 i-1 = 2 0 = 1 이성립 induction hypothesis: 1 j i 인경우를가정해본다. 상기조건인모든 level j 에대해서, level j 의최대 node 개수는 2 j-1 라고가정 induction step: 그렇다면, 상기가정에의해, level i-1 의최대 node 의개수는 2 i-2 이다. binary tree 의각 node 는최대 degree 가 2 이므로, level i 의최대 node 개수는, (level i-1 의최대 node 개수의 2 배인 ) 2 i-1 가된다. 2. 깊이 (depth) k 인 binary tree 의최대노드개수는 k Σ (i 는 1~k, 즉, level i 에있는 node 의최대개수 ) = Σ 2 i-1 = 2 k -1 i=1 k i=1 15

16 이진 (binary) 트리의특성 (2) Lemma 5.3 :: degree 2 인어떤 node 와 leaf node 의개수간의관계 Non-empty binary tree T 에대해서, n 0 가 leaf node 의개수이고, n 2 가 degree 2 인 node 의개수라면, à n 0 = n ( 증명 ) - n 1 이 degree 1 인 node 개수이고, n 이전체 node 개수라고하자. T 의모든 node 들은최대 degree 가 2 이므로, (degree 0 은 leaf node 가될것임 ) 전체 node 개수인, n = n 0 + n 1 + n 2 ( 식 5.1) - 만약, binary tree 의 branch 개수를센다면, root 를제외한모든 node 는자신으로들어오는 branch 가있다. 를전체 branch (edge) 의개수라고한다면, 전체 node 개수인, n = +1 이다. ( 식 5.2) 모든 branch 는 degree 가 1 이거나, 2 인 node 들로부터시작됨으로 Tree 전체의 branch (edge) 개수, = n 1 + 2n 2 가된다. - 그러므로, 전체 node 개수인, n = 1 + n 1 + 2n 2 ( 식 5.3) ß ( 식 5.2) 에의해. ( 식 5.3) 과 ( 식 5.1) 을 n 에대한등호로놓으면, 위의식이성립함을알수있다. 그러므로, n 0 = n 이다. - 예제 : Figure 5.6(a) 는 n 0 = 1, n 2 =0 이다. Figure 5.6(b) 는 n 0 = 5, n 2 =4 이다. 16

17 이진 (binary) 트리의특성 (3) 정의, depth k 의 full binary tree : k 가 0 이상일때, 2 k -1 개의 node 를갖는 depth k 의 binary tree 이다 Figure 5.7: 연속적인 node 숫자들을가진깊이 4 의 full binary tree 정의, omplete binary tree: n 개의 node 들을가지고 depth 가 k 인 binary tree 의 node 들이 depth 가 k 인 full binary tree 의 1 부터 n 까지 node 들과순서가일치한다면, 그 binary tree 는 complete 하다. 17

18 5.2.3 inary Tree 의표현방법 (1) rray 로표현하는방법 Figure 5.7 의 number 부여방법 (numbering scheme) 에근거하여 1- 차원 array (1~n) 로표현 ( 저장 ) 한다. 이후, 아래 Lemma 5.3 을이용하면, binary tree 에서어떤 node i 에대한 parent, left child, right child 의위치를쉽게파악 ( 검색 ) 할수있다. 이런표현 ( 저장 ) 방법은 complete binary tree 의표현에는공간이낭비없이저장되므로, 이상적 ( 장점 ) 이다. 그러나, skewed ( 한쪽으로만기울어진 ) binary tree 의경우에대해서는빈공간이많이생겨, 공간활용도측면에서비효율적 ( 문제점 ) 이다. 노드의삽입 / 삭제가힘듦 : 한노드가삽입되면, 그노드의부트리들이모두움직여야한다. Lemma 5.3 n 개의 node 를갖는 complete binary tree (depth = log 2 n +1 ) 가순차적으로표현되면, 1 i n 인 index i 를가진 node 는다음의특성을가진다. 1. Parent(i): i 가 1 이아니면, i/2 이고, i 가 1 이면, i 는 root 이고, parent 가없다. 2. Left child (i): 2i n 이면, 2i 이고, 그렇지않은경우, i 는 left child 가없다. 3. Right child (i): 2i+1 n 이면, 2i+1 이고, 그렇지않은경우, i 는 right child 가없다. ( 증명 ) Lemma 5.2 와유사하게, i 에대한 induction 에의해서증명하면된다. 18

19 19 I E F G H [9] [8] [7] [6] [5] [4] [3] [2] [1] I H G F E complete binary tree E skewed binary tree E [9] [8] [7] [6] [5] [4] [3] [2] [1] [16]

20 5.2.3 inary Tree 의표현방법 (2) Linked List 로표현하는방법 Node 의 parent 파악이좀어렵지만, 대부분의 tree 표현응용에적합하다. Parent node 의파악을위해서, node 정의에 parent field 를추가하면된다. typedef struct node *tree_ptr; typedef struct node { int data; tree_ptr left_child, right_child; }; 이진트리의노드표현 data left_child data right_child left_child right_child 20

21 이진트리의링크표현방식예제 root root NULL H NULL NULL I NULL NULL E NULL NULL F NULL NULL complete binary tree G NULL NULL NULL E NULL NULL NULL NULL skewed binary tree 21

22 이진트리의링크표현방식예제 ( 계속 ) 단말노드 (leaf node) 의링크는 NULL 을가진다. NULL data NULL leaf node 부모노드를알고싶으면, parent field 를추가한다. parent left_child parent data right_child data left_child right_child 22

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection