강의 #7 트리(Tree)

트리(TREE) 트리: 계층적인 구조를 나타내는 자료구조 트리는 부모-자식 관계의 노드들로 이루어진다. 응용분야: 계층적인 조직 표현 파일 시스템 인공지능에서의 결정트리

트리의 용어 (1) 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 루트노드 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 A B C D E F G H I J 서브트리

트리의 용어 (2) 단말노드(terminal node): 자식이 없는 노드(A,B,C,D) 비단말노드(non-terminal node): 적어도 하나의 자식을 가지는 노드(E,F,G,H,I,J) 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대 레벨(3) 차수(degree): 노드가 가지고 있는 자식 노드의 개수 비단말 노드 A B C D E F G H I J 단말 노드

이진 트리(binary tree) 이진 트리(binary tree) : 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리 서브 트리는 공집합일수 있다. 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재 일반 트리는 자식 노드의 개수에 제한이 없다 모든 노드의 차수가 2 이하가 된다  구현하기가 편리함 이진 트리에는 서브트리간의 순서가 존재 (a*b)+(c/d)

이진 트리의 성질 (1) 노드의 개수가 n개이면 간선의 개수는 n-1 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2h-1개의 노드를 가진다.

이진 트리의 성질 (2) n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소

이진트리의 분류 포화 이진 트리(full binary tree): 트리의 각 레벨에 노드가 꽉 차있는 이진트리 완전 이진 트리(complete binary tree): 높이가 h일 때 레벨 1부터 h-1까지는 노드가 모두 채워져 있고 레벨 h에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

이진 트리의 표현 (1) 배열 표현법: 모든 이진 트리를 포화 이진 트리라고 가정 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장 이진 트리의 깊이가 k이면 최대 2k-1 개의 연속 공간이 필요  완전 이진 트리가 아닌 경우 기억장소 낭비 부모 및 자식 노드 사이의 인덱스 관계: 노드 i의 부모 노드 인덱스 = i/2 노드 i의 왼쪽 자식 노드 인덱스 = 2i 노드 i의 왼쪽 자식 노드 인덱스 = 2i +1

이진 트리의 표현 (2) 링크 표현법: 연결 리스트를 사용 포인터를 이용하여 부모 노드가 자식 노드에 대한 연결 정보를 가지도록 저장하는 방법 데이터 왼쪽 자식 노드 오른쪽 자식 노드 tyepdef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode;

이진 트리의 순회(Traversal) 순회(traversal): 3가지의 기본적인 순회방법 트리의 노드들을 체계적으로 방문하는 것 3가지의 기본적인 순회방법 전위순회(preorder traversal): VLR 자손노드보다 루트노드를 먼저 방문한다. 중위순회(inorder traversal): LVR 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다. 후위순회(postorder traversal): LRV 루트노드보다 자손을 먼저 방문한다. 왼쪽 자손, 오른쪽 자손, 루트 순으로 방문한다.

전위 순회(Preorder Traversal) 루트를 먼저 방문하고 자식노드를 순회방법 응용분야: 구조화된 문서출력 // 전위 순회 preorder( TreeNode *root ){     if ( root ){       printf("%d", root->data );  // 노드 방문       preorder( root->left ); // 왼쪽서브트리 순회       preorder( root->right );// 오른쪽서브트리 순회     } } 1 5 9 2 4 6 7 8 10 11 3

중위 순회 (Inorder Traversal) 왼쪽서브트리->루트->오른쪽 서브트리 순으로 방문 // 중위 순회 inorder( TreeNode *root ){     if ( root ){       inorder( root->left );// 왼쪽서브트리 순회       printf("%d", root->data );  // 노드 방문       inorder( root->right );// 오른쪽서브트리 순회     } } 4 + * / a b c d 2 6 1 3 5 7

후위 순회 (Postorder Traversal) 루트->왼쪽서브트리->오른쪽서브트리 순으로 방문 (예) 디렉토리 용량 계산 // 후위 순회 postorder( TreeNode *root ){ if ( root ){ postorder( root->left ); // 왼쪽서브트리 순회 postorder( root->right );// 오른쪽서브트리순회 printf("%d", root->data );// 노드 방문 } 5 4 1 2 3

프로그램 실습 #1 이진 트리를 연결 리스트을 사용하여 구현 이진 트리에 대한 3가지 순회 기법을 구현하고 순회 결과를 제시한다.

이진트리 응용: 수식 트리 수식 트리: 산술식을 트리 형태로 표현한 것 예) 비단말노드: 연산자(operator) 단말노드: 피연산자(operand) 예) 수식 a + b a - (b × c) (a < b) or (c < d) 전위순회 + a b - a × b c or < a b < c d 중위순회 a - b × c a < b or c < d 후위순회 a b + a b c × - a b < c d < or

이진트리 응용: 수식 트리 계산 후위순회를 사용 서브 트리의 값을 순환호출로 계산 비단말노드를 방문할때 양쪽 서브 트리의 값을 저장된 연산자를 이용하여 계산한다 evaluate(exp) if exp = NULL then return 0; else x←evaluate(exp->left); y←evaluate(exp->right); op←exp->data; return (x op y);

프로그램 실습 #2 수식 트리 계산 프로그램 작성 및 테스트

이진트리연산: 노드 개수 탐색 트리안의 노드의 개수를 계산 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환 int get_node_count(TreeNode *node) { int count=0; if( node != NULL ) count = 1 + get_node_count(node->left)+ get_node_count(node->right); return count; } 1 3 2 6

이진트리연산: 단말 노드 개수 탐색 트리안의 단말 노드의 개수를 계산 순회하면서 만약 왼쪽 자시과 오른쪽 자식이 동시에 0이면 단말 노드이므로 1를 반환 서브 트리에 대해 순환 호출하여 반환되는 값을 더한다 int get_leaf_count(TreeNode *node) { int count=0; if( node != NULL ) { if (node->left==NULL && node->right==NULL) return 1; else count = get_leaf_count(node->left)+ get_leaf_count(node->right); return count; }

이진트리연산: 높이 서브 트리에 대하여 순환호출하고 서브 트리들의 반환값 중에서 최대값을 구하여 반환 int get_height(TreeNode *node) { int height=0; if( node != NULL ) height = 1 + max(get_height(node->left), get_height(node->right)); return height; }

스레드 이진 트리 (1) 이진 트리 순회는 순환 호출을 사용  함수 호출에 따른 부하 증가로 인하여 비효율적 이진 트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들의 순회가 가능 NULL 링크에 중위 순회시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진 트리(threaded binary tree) 단말노드와 비단말노드의 구별을 위히여 is_thread 필드 필요 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE } TreeNode;

스레드 이진 트리 (2) 스레드 이진 트리 순회 TreeNode *find_successor(TreeNode *p) { TreeNode *q = p->right; if (q==NULL || p->is_thread==TRUE) return q; while (q->left != NULL) q = q->left; } void thread_indorder(TreeNode *t) TreeNode *q = t; while (q->left) q = q->left; do { printf(“%c”, q->data); q = find_successor(q); } while(q); 4 6 2 1 3 7 5

프로그램 실습 #3 스레드 이진 트리 구현 스레드 이진 트리 순회 프로그램 작성 및 테스트

탐색(Search) 예: 일상생활에서의 탐색-전화번호찾기, 사전찾기 등 가장 중요한 컴퓨터응용 중에 하나 실행 시간을 많이 요구하므로 가능한 효율적으로 수행하도록 구현 요구 탐색 연산의 정의 레코드(record)의 집합에서 특정한 레코드를 찾는 작업 Field, record, table Primary key 학번 이름 주소 필드 1 필드 2 필드 3 레코드 1 -> 레코드 2 -> 레코드 3 -> 테이블

이진탐색트리(Binary Search Tree) 탐색작업을 효율적으로 하기 위한 자료구조 이진탐색트리의 정의: 모든 원소의 키는 유일한 키이어야 한다 key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리) 왼쪽 및 오른쪽 서브 트리도 이진탐색트리이다 이진탐색트리를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

이진탐색트리에서의 탐색연산 비교한 결과가 같으면 탐색이 성공적으로 끝난다. 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다. 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다. 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);

이진탐색트리에서의 삽입연산 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치 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

이진탐색트리에서의 삭제연산 3가지의 경우 CASE 1: 삭제하려는 노드가 단말 노드일 경우 1. 삭제하려는 노드가 단말 노드일 경우 2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중에 하나만 가지고 있는 경우 3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우 CASE 1: 삭제하려는 노드가 단말 노드일 경우 단말노드의 부모 노드를 찾아서 연결을 끊으면 된다. 　

이진탐색트리에서의 삭제연산 CASE 2:삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우 : 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리 중에 하나만 가지고 있는 경우에는 노드는 삭제하고 서브 트리는 부모 노드에 붙여준다.

이진탐색트리에서의 삭제연산 CASE 3:삭제하려는 노드가 두 개의 서브 트리를 가지고 있는 경우: 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져온다.

이진탐색트리의 성능 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을때 h에 비례한다 최선의 경우 이진 트리가 균형적으로 생성되어 있는 경우 h=log2n 최악의 경우 한쪽으로 치우친 경사이진트리의 경우 h=n 순차탐색과 시간복잡도가 같다.

프로그램 실습 #4 이진 탐색 트리 및 기능 구현 이진 탐색 트리를 이용한 영어 사전 프로그램 구현

프로그램 과제(1) 정수를 입력받아 이진탐색트리에 저장하고, 다음 화면의 기능을 수행하는 프로그램을 작성하여라. h

프로그램 과제(2) 기능 설명: 입력(i) : 사용자로부터 정수를 입력받아 이진탐색트리에 추가한다. 삭제(d) : 사용자로부터 입력받은 숫자를 이진탐색트리에서 삭제한다. 탐색(s) : 사용자로부터 입력받은 숫자가 이진탐색트리에 존재하는지 여부를 확인한다. 순회(v) : 이진탐색트리를 3가지 표준적인 순회방법으로 순회하고, 순회 결과를 출력한다. 높이(h) : 현재의 이진탐색트리의 높이를 반환한다. 노드의 개수(c) : 현재 생성되어 있는 이진탐색트리의 전체 노드 수를 반환한다. 단말 노드의 개수(t) : 현재 생성되어 있는 이진탐색트리의 단말 노드 수를 반환한다.

프로그램 과제(3) 기능 설명: 최대값(m) : 이진탐색트리 내에서 가장 큰 정수값을 반환한다. 최소값(n) : 이진탐색트리 내에서 가장 작은 정수값을 반환한다. 노드삭제(d) : 이진탐색트리의 모든 노드를 삭제한다. 출력(p) : 이진탐색트리에 저장된 모든 정수를 오름차순으로 출력한다. 종료(q) : 프로그램을 종료한다.