데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호
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
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
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
Figure 5.2. Sample Tree Level 1 2 3 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
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
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
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
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
5.1.2 Tree 의표현방법 ( 변환과정 ) E F G tree E F G binary tree E F G left child-right sibling tree 10
Figure 5.5: Tree 표현법비교정리 tree left child-right sibling tree binary tree tree left child-right sibling tree binary tree 11
이진트리의정의 이진트리는 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
inary Tree 의비교 0 개의 node 를가진 tree 는없지만, empty binary tree 는존재한다. inary tree 에서는 children 의 order 를구분하지만, tree 에서는구분하지않는다. 다음의 2 개의 binary tree 는다르다. 13
Figure 5.6. Skewed tree 와 complete tree 의비교 E F G E H I skewed binary tree complete binary tree 14
5.2.2. 이진 (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
5.2.2. 이진 (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 2 + 1. ( 증명 ) - 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 2 + 1 이다. - 예제 : Figure 5.6(a) 는 n 0 = 1, n 2 =0 이다. Figure 5.6(b) 는 n 0 = 5, n 2 =4 이다. 16
5.2.2. 이진 (binary) 트리의특성 (3) 정의, depth k 의 full binary tree : k 가 0 이상일때, 2 k -1 개의 node 를갖는 depth k 의 binary tree 이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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
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 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]
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
이진트리의링크표현방식예제 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
이진트리의링크표현방식예제 ( 계속 ) 단말노드 (leaf node) 의링크는 NULL 을가진다. NULL data NULL leaf node 부모노드를알고싶으면, parent field 를추가한다. parent left_child parent data right_child data left_child right_child 22