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 Trees) 9. Forests 10. 집합표현 (Set Representation) 11. 이진트리의개수계산 5 장. 트리 (Page 2)
1. Introduction 트리의정의 하나이상의 node 로이루어진유한집합으로서 Root 라고하는노드가하나존재 나머지노드들은 n ( 0) 개의분리집합 T 1,, T n 으로분할될수있다. T 1,, T n : 각각하나의트리 Root 의서브트리 (subtree) 예 : 그림 5.1 가계도의두가지형태 5 장. 트리 (Page 3)
두종류의가계도 Dusty Honey Bear Brandy Brunhilde Terry Coyote Nugget Gill Tansey Tweed Zoe Crocus Primrose Nous Belle (a) 가계도 Proto Indo-European Italic Hellenic Germanic Osco-Umbrian Latin Greek North Germanic West Germanic Osco Umbrian Spanish French Italian Icelandic Norwegian Swedish Low High Yiddish (b) 언어의파생 5 장. 트리 (Page 4)
트리에관련된용어들 Sample Tree Level 1 B C D E F G H I J K L M Level 2 Level 3 Level 4 노드의차수 (degree) (: 3), 트리의차수 (degree) (3) 단말노드 (leaf or terminal node) (K, L, F, G, M, I, J) Parent (E: B), Children (B: E & F), Siblings (E & F) ncestor (M: H, D, ), Descendants (B: E, F, K, L) Level (Root: 1), Height or Depth (4) 5 장. 트리 (Page 5)
트리의표현 리스트표현 ( (B (E (K, L), F), C (G), D (H (M), I, J))) 연결리스트 : 링크필드의수가가변 data Link 1 Link 2 Link n Left Child - Right Sibling 표현 트리의모든노드마다 2개의링크필드만포함 data left child right child 5 장. 트리 (Page 6)
Left-Child Right-Sibling 표현 B C D E F G H I J K L M 이진트리 (Binary Tree) B C D E F G H I J K L M 5 장. 트리 (Page 7)
이진트리 원트리 D B C 노드 B 의자식노드의수? 이진트리 원트리 I E F J G M H C 의부모노드? 이진트리 원트리 K L 단말노드의수? 이진트리 원트리 5 장. 트리 (Page 8)
2. 이진트리 추상적데이터타입 이진트리의성질 이진트리의표현 5 장. 트리 (Page 9)
2.1 추상적데이터타입 이진트리의주요특징 모든노드의차수 (degree) 는 2 를넘지않는다 왼쪽서브트리와오른쪽서브트리가구분 이진트리는 0 개의노드를포함할수도있다. 이진트리의정의 유한개의노드들의집합으로서 노드수는 0 이될수있으며, 하나의 root 노드와왼쪽서브트리, 그리고오른쪽서브트리로구성 각서브트리는다시이진트리이다. 5 장. 트리 (Page 10)
DT 5.1: 이진트리 DT DT Binary_Tree (abbreviated BinTree) 객체 : 유한개의노드집합으로, 하나의 root 노드와왼쪽 Binary_Tree, 그리고오른쪽 Binary_Tree 로구성함수 : for all bt, bt1, bt2 BinTree, item element BinTree Create() ::= 노드수가 0인이진트리생성 Boolean IsEmpty(bt) ::= if (bt의노드수 == 0) return TRUE else return FLSE BinTree MakeBT(bt1, item, bt2) ::= 왼쪽서브트리는 bt1, 오른쪽서브트리는 bt2, 그리고 root 노드에 item을저장한이진트리를반환 BinTree Root(bt) ::= if (IsEmpty(bt)) return error else bt의루트노드를반환 BinTree Rchild(bt) ::= if (IsEmpty(bt)) return error else bt의오른쪽서브트리를반환 5 장. 트리 (Page 11)
그림 5.8: 서로다른두이진트리 B B 5 장. 트리 (Page 12)
그림 5.9: 편향트리와완전이진트리 Level 1 B B C 2 C D E F G 3 D H I 4 E 5 편향 (skewed) 완전 (complete) 이진트리 이진트리 5 장. 트리 (Page 13)
2.2 이진트리의성질 보조정리 5.1 [ 최대노드수 ] 이진트리의레벨 i에서최대노드수는 2 i-1 (i 1) 깊이가 k인이진트리가가질수있는최대노드수 = k i= 1 2 i 1 = 2 1 보조정리 5.2 [ 단말노드수와차수가 2 인노드수 ] n 0 : 단말노드수, n 2 : 차수가 2 인노드의수 n 0 = n 2 + 1 ( 증명 ) n = n 0 + n 1 + n 2 & n = E + 1 = n 1 + 2n 2 + 1 정의 : 깊이가 k 인포화이진트리 (full binary tree) 깊이가 k 이고노드수가 2 k 1 (k 0) 인이진트리 k 5 장. 트리 (Page 14)
완전이진트리 (Complete Binary Tree) 완전이진트리란? 깊이가 k 이고노드수가 n 인이진트리의각노드들이깊이가 k 인포화이진트리에서 1 부터 n 까지의번호를붙인노드들과 1 대 1 로일치하는이진트리 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 장. 트리 (Page 15)
연습문제 깊이가 k 인이진트리의두가지종류로노드수가가장많은트리를, 노드수가가장적은트리를 B 라고할때, 아래질문에답하라. 단, 루트노드의레벨은 1 로한다. 레벨 i 에존재하는노드수의최소값과최대값은얼마인가? 의노드수에서 B 의노드수를뺀값은얼마인가? 에서단말노드가아닌노드의수에서단말노드의수를뺀값은얼마인가? 5 장. 트리 (Page 16)
2.3 이진트리의표현 배열표현보조정리 5.3 을이용하여 1 차원배열에저장 보조정리 5.3: n 개의노드를가진완전이진트리가순차적으로표현되어있다면 (depth = log 2 (n + 1) ), 인덱스 i (1 i n) 를갖는임의의노드에대해다음이성립. parent(i) = i/2 if i 1. If i = 1 (root), no parent. lchild(i) = 2i if 2i n. If 2i > n, i has no left child. rchild(i) = 2i + 1 if 2i + 1 n. If 2i + 1 > n, no right child. 5 장. 트리 (Page 17)
그림 5.11: 그림 5.9 의배열표현 [1] [2] [3] [4] [5] [6] [7] [8] [9]... [16] B -- C -- -- -- D -- 그림 5.9(a) 편향트리... E [1] [2] B [3] C [4] D [5] E [6] F [7] G [8] H [9] I 그림 5.9(b) 완전이진트리 5 장. 트리 (Page 18)
링크표현 typedef struct node *tree_pointer; struct node { int data; struct node *left_child; struct node *right_child; }; data left_child data right_child left_child right_child 5 장. 트리 (Page 19)
그림 5.13: 그림 5.9 의링크표현 NULL root root B C B NULL D NULL E NULL NULL F NULL NULL G NULL C NULL NULL H NULL NULL I NULL D NULL NULL E NULL 1. 노드수가 n 일경우, 링크의수? 2. NULL 인링크의수? 5 장. 트리 (Page 20)