Internet Computing Laboratory @ KUT Youn-Hee Han 10장. 트리 Internet Computing Laboratory @ KUT Youn-Hee Han

1. 트리 개요 비선형 자료 구조 선형 자료 구조 비선형 구조 고안 동기 리스트, 스택, 큐가 데이터 집합을 한 줄로 늘어 세운 선형 자료구조 트리(Tree)는 데이터 집합을 여러 갈래로 나누어 세운 비 선형 구조 비선형 구조 고안 동기 효율성 삽입, 삭제, 검색에 대해서 선형 구조보다 나은 시간적 효율을 보임 Data Structure

1. 트리 개요 Definitions 트리의 구성 요소에 해당하는 A, B, C, ..., F를 노드 (Node)라 함. B의 바로 아래 있는 E, F를 B의 자식노드 (Child Node)라 함. B는 E, F의 부모노드 (Parent Node)이고, A는 B, C, D의 부모노드 (Parent Node)임. 같은 부모 아래 자식 사이에 서로를 자매노드 (Sibling Node)라 함. B, C, D는 서로 자매노드이며, E, F도 서로 자매노드임. 주어진 노드의 상위에 있는 노드들을 조상노드 (Ancestor Node)라 함. B, A는 F의 조상노드임. 어떤 노드의 하위에 있는 노드를 후손노드 (Descendant Node)라 함. B, E, F, C, D는 A의 후손노드임. Data Structure

1. 트리 개요 Definitions 부모가 없는 노드 즉, 원조격인 노드를 루트 노드 (Root Node)라 함. C, D, E, F처럼 자식이 없는 노드를 리프노드 (Leaf Node)라 함. 리프노드를 터미널 노드 (Terminal Node)라고도 함. 리프노드를 제외한 모든 노드를 내부노드 (Internal Node)라 함. 주어진 트리의 부분집합을 이루는 트리를 서브트리 (Subtree)라 함. 서브트리는 임의의 노드와 그 노드에 달린 모든 후손노드를 합한 것임. 임의의 트리에는 여러 개의 서브트리가 존재할 수 있음. 그림의 B, E, F가 하나의 서브트리이며, C 자체로서도 하나의 서브트리 Data Structure

1. 트리 개요 Definitions 둘 이상의 자식노드를 가지는 트리를 일반트리 (General Tree)라 함. 최대 두 개까지의 자식노드를 가질 수 있는 트리를 이진트리 (Binary Tree)라 함. Data Structure

1. 트리 개요 Definitions 삼진트리 (Ternary Tree) Data Structure

1. 트리 개요 일반트리의 이진트리 변환 모든 일반 트리는 이진 트리로 바꾸어 표현 가능 변환 이유 예 일반트리에서는 자식노드의 수가 몇 개가 있는지 예측 불가 부모노드 (Parent Node)가 무조건 첫 자식노드 (First Child Node)를 가리키게 첫 자식노드로(First Child Node)부터 일렬로 자매 노드 (Sibling Node)들을 이으면 이진 트리 Data Structure

1. 트리 개요 일반트리의 이진트리 변환 Data Structure

1. 트리 개요 이진트리 (Binary Tree) 이진트리의 재귀적 정의 (Recursive Definition) A binary tree is a tree data structure in which each node has at most two children the child nodes are called left and right 이진트리의 재귀적 정의 (Recursive Definition) 1) 아무런 노드가 없는 트리이거나, 2) 가운데 노드를 중심으로 좌우로 나뉘되, 좌우 서브트리 (Subtree) 모두 이진트리다. 1)번 때문에, 아무런 노드가 없는 트리도 주어진 트리의 서브트리이며 동시에 이진트리가 됨. 1)번은 재귀호출의 Base-case에 해당 Data Structure

1. 트리 개요 트리의 레벨(Level) 트리의 높이(Height) 루트노드를 레벨 0으로 하고 아래로 내려오면서 증가 트리의 높이는 최대 레벨 그 자체와 일치 루트만 있는 트리의 높이는 0 비어있는 트리의 높이는 -1 (=3) Data Structure

1. 트리 개요 트리의 높이(Height)에 대한 다른 정의 트리의 높이(Height)에 대한 재귀적 정의 루트노드에서 가장 먼 리프노드까지 가는 데 필요한 링크(Link) 개수 트리의 높이(Height)에 대한 재귀적 정의 트리의 높이 = 1 + Max{왼쪽 서브트리의 높이, 오른쪽 서브트리의 높이} Data Structure

Perfect binary tree 는 level i 인 node의 갯수가 정확히 2(i+1)-1 인binary tree 1. 트리 개요 Perfect Binary Tree (완벽 이진트리) 높이가 h인 이진트리에서 모든 리프노드가 레벨 h에 있는 트리 리프노드 위쪽의 모든 노드는 반드시 두개의 자식노드를 거느려야 함. 시각적으로 볼 때 포화될 정도로 다 차 들어간 모습. A perfect binary tree is a binary tree in which all leaves (vertices with zero children) are at the same depth Perfect binary tree 는 level i 인 node의 갯수가 정확히 2(i+1)-1 인binary tree Data Structure

1. 트리 개요 Full Binary Tree (포화 이진트리) or Proper Binary Tree A full binary tree is a tree in which every node has zero or two children In other words, every node is either a leaf or has two children. 완벽 이진트리이면 포화 이진트리. 그러나 역은 성립 안 됨. Data Structure

1. 트리 개요 Complete Binary Tree (완전 이진트리) 레벨 (h-1)까지는 완벽 이진트리 하나라도 건너뛰고 채워지면 안됨. 완벽 이진트리이면 완전 이진트리. 그러나 역은 성립 안 됨. A complete binary tree to be a binary tree in which all leaves are at depth n or n-1 for some n. All the children on the last level must occupy the leftmost spots consecutively, with no spot left unoccupied in between any two. Data Structure

2. 추상 자료형 트리 작업 Create: 새로운 트리를 만들기 Destroy: 사용되던 트리를 파기하기 Insert: 트리에 새로운 노드를 삽입하기 Delete: 트리의 특정 노드를 삭제하기 Search: 주어진 키를 가진 노드 레코드를 검색하기 IsEmpty: 빈 트리인지를 확인하기 CopyTree: 주어진 트리를 복사하기 Traverse: 트리 내부 노드를 하나씩 순회하기 Data Structure

3. 배열에 의한 이진트리 구현 배열을 사용한 이진트리 선언 #define MAXNODE 100 최대 노드 수 typedef struct {                  배열 요소는 구조체       char Name[ ];              이름 필드 int LChild;                    왼쪽 자식 int RChild;                    오른쪽 자식 } node; typedef node treeType[MAXNODE]; treeType은 구조체 배열 타입 Index Structure Name LChild RChild Park 1 2 Kim -1 3 Seo 4 Lee Cho 5 UnUsed   6 7 Data Structure

3. 배열에 의한 이진트리 구현 인덱스와 Child 값의 의미 Lee 삭제 Park의 LChild = 1  LChild인 Kim이 인덱스 1번에 있음을 의미 인덱스 -1은 빈 트리(Empty Tree)를 의미 Lee 삭제 데이터 필드에서 Lee를 찾아서 해당 엔트리를 Unused로 표시 부모 노드인 Kim의 Rchild도 -1로 부모노드를 찾기 위해서는 Lee의 인덱스 3을 가지고 배열 전체를 뒤져야 함.  시간면에서 매우 비효율적임. 배열에 의한 이진트리는 거의 사용 안 함 하지만! Perfect (or Complete) Binary Tree 는 배열로 구현하는 경우가 있음 Data Structure

3. 배열에 의한 이진트리 구현 완전 이진트리 (Complete Binary Tree)와 배열 완전 이진트리는 왼쪽에서 오른쪽으로 빠짐없이 노드가 채워짐 인덱스를 정하는 규칙이 정형화됨 인덱스 K에 있는 노드의… 왼쪽 자식은 (2K + 1) 오른쪽 자식은 (2K + 2) 부모 노드는 (K - 1) / 2 완전 이진트리의 이러한 특성은 Heap을 구현하는데 이용됨 Data Structure

4. 포인터에 의한 이진트리 구현 포인터를 사용한 이진트리 선언 typedef struct { char Name[ ];        이름 필드 node* LChild;          왼쪽 자식을 가리키는 포인터 node* RChild;          오른쪽 자식을 가리키는 포인터 } node;                  노드는 구조체 타입 typedef node* Nptr;  노드를 가리키는 포인터를 Nptr 타입으로 정함 Data Structure

4. 포인터에 의한 이진트리 구현 포인터를 사용한 이진트리 구성 예 (주의 – 실제로는 좀 더 효율적으로 구현해야 함) Nptr nodeA; Nptr nodeB; Nptr nodeC; Nptr nodeG; Nptr nodeF; Nptr nodeQ; … void configNode(Nptr n, char[] nm, Nptr lt, Nptr rt) { n->Name = nm; n->LChild = lt; n->RChild = rt; } configNode(nodeA, “A”, nodeC, nodeB); configNode(nodeC, “C”, nodeG, nodeF); configNode(nodeG, “G”, nodeQ, null); configNode(nodeQ, “Q”, null, null); Data Structure

왼쪽 서브트리와 오른쪽 서브트리로 나누어서 재귀호출 4. 포인터에 의한 이진트리 구현 순회 (Traversal) 이진 트리의 작업 중에 가장 중요한 작업 삽입, 삭제, 검색을 하기 위하여 우선적으로 선행되는 작업 트리 정의가 재귀적. 따라서 순회도 재귀적. 순회에 대한 Pseudo Code 현재 노드에 대한 작업이 어디에 위치하는가에 따라… 전위순회, 중위순회, 후위순회 Traverse(T) { if (T is Empty) { … } else { Traverse(Left Subtree of T); Traverse(Right Subtree of T); } 왼쪽 서브트리와 오른쪽 서브트리로 나누어서 재귀호출 Data Structure

4. 포인터에 의한 이진트리 구현 전위순회 (Pre-order Traversal) void PreOrder (Nptr T) { if (T != NULL) { Visit(T->Name); 필요한 작업 수행 PreOrder(T->LChild); 왼쪽 재귀호출 PreOrder(T->RChild); 오른쪽 재귀호출 } 방문 순서: G, C, A, E, L 깊이우선탐색 (DFS, Depth First Search)과 일치 Data Structure

4. 포인터에 의한 이진트리 구현 중위순회 (Pre-order Traversal) and 후위순회(Post-order Traversal) void InOrder (Nptr T) { if (T != NULL) { InOrder(T->LChild); Visit(T->Name); InOrder(T->RChild); } void PostOrder (Nptr T) { if (T != NULL) { PostOrder(T->LChild); PostOrder(T->RChild); Visit(T->Name); } 방문 순서: A, C, E, G, L 방문 순서: A, E, C, L, G Data Structure

4. 포인터에 의한 이진트리 구현 Traversal 순서 알아내는 좋은 방법 Inorder (중위) Traversal Preorder (전위) Traversal Postorder (후위) Traversal Traversal 순서 알아내는 좋은 방법 Data Structure

4. 포인터에 의한 이진트리 구현 큐에 의한 레벨순회 (Level-order Traversal)  Breadth First Search 트리의 위에서 아래로 진행하되, 같은 레벨에서는 왼쪽에서 오른쪽으로 진행 void LevelOrder (Nptr T) { Q.Create( );                           Q.Add(T);                             while (! Q.IsEmpty( )) {  Nptr Current = Q.GetFront( ); Visit(Current->Name); if (Current->LChild != NULL) Q.Add(Current->LChild);        if (Current->RChild != NULL) Q.Add(Current->RChild);  } 방문 순서: G, C, L, A, E 너비우선탐색 (BFS, Breadth First Search)과 일치 Data Structure