CHAP 7:트리

트리(TREE) 트리: 계층적인 구조를 나타내는 자료구조 트리는 부모-자식 관계의 노드들로 이루어진다. 응용분야: 리스트, 스택, 큐 등은 선형 구조 트리는 부모-자식 관계의 노드들로 이루어진다. 응용분야: 계층적인 조직 표현 컴퓨터 디스크의 디렉토리 구조 인공지능에서의 결정트리 (decision tree)

회사의 조직

파일 디렉토리 구조

결정 트리 (예) 골프에 대한 결정 트리

트리의 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브트리(subtree): 하나의 노드와 그 노드의 자손 노드들로 이루어진 (전체 트리의) 부분 트리

트리의 용어 단말노드(leaf node or terminal node): 자식이 없는 노드(E,F,G,H,I,J) 비단말노드/내부노드(internal node): 적어도 하나의 자식을 가지는 노드 (A,B,C,D)

트리의 용어 깊이/레벨 1 2 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 1 2 C 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 깊이(depth): 루트에서 특정노드까지의 경로에 존재하는 edge의 수를 그 노드의 depth라 함 높이(height): 트리의 최대 깊이 차수(degree): 노드가 가지고 있는 자식 노드의 개수

예제 A는 루트 노드이다. B는 D와 E의 부모노드이다. C는 B의 형제 노드이다. D와 E는 B의 자식노드이다. 위의 트리의 높이는 3이다.

이진트리 (binary tree) 이진 트리(binary tree) : 모든 노드가 최대 2개의 자식 노드를 가지는 트리 모든 노드의 차수가 2 이하가 된다.

이진트리의 성질 높이가 h인 이진트리의 경우, 최소 h+1 개의 노드를 가지며 최대 2h+1-1개의 노드를 가진다. 1 + x1 + ••• + xn = (1–xn+1)/(1–x), x≠1 ← x =2, n = h 높이 = 2

이진트리의 성질 n개의 노드를 가지는 이진트리의 높이 최대 n - 1 최소 n = 2h+1 - 1 → h = log2(n+1) - 1 = log2n 높이 = 6 높이 = 2

이진트리의 분류 포화 이진 트리(full binary tree) 완전 이진 트리(complete binary tree) 기타 이진 트리

포화 이진 트리 트리의 각 노드가 자식이 없거나 또는 자식이 둘인 이진트리. 즉, 자식이 하나인 노드가 없는 이진트리 A full binary tree is a tree in which every node other than the leaves has two children.

완전 이진 트리 완전 이진 트리(complete binary tree): 마지막 레벨을 제외한 모든 레벨에는 노드가 꽉 채워져 있으며, 마지막 레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 배치되어 있는 이진트리

이진트리의 표현 배열을 이용하는 방법 포인터를 이용하는 방법

배열 표현법 배열표현법: 이진트리의 각 노드에 완전이진트리에서와 같이 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

부모와 자식 인덱스 관계 노드 i의 부모 노드 인덱스 = i/2 노드 i의 왼쪽 자식 노드 인덱스 = 2i

링크 표현법 링크 표현법: 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

링크의 구현 노드는 구조체로 표현 링크는 포인터로 표현 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode;

링크 표현법 프로그램 #include <stdio.h> #include <stdlib.h> #include <memory.h> typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // n1 // / | // n2 n3 void main() { TreeNode *n1, *n2, *n3; n1= (TreeNode *)malloc(sizeof(TreeNode)); n2= (TreeNode *)malloc(sizeof(TreeNode)); n3= (TreeNode *)malloc(sizeof(TreeNode));

링크 표현법 프로그램 n1->data = 10; // 첫번째 노드를 설정한다. n1->left = n2; n1->right = n3; n2->data = 20; // 두번째 노드를 설정한다. n2->left = NULL; n2->right = NULL; n3->data = 30; // 세번째 노드를 설정한다. n3->left = NULL; n3->right = NULL; }

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

전위 순회 1. 루트 노드를 방문한다 2. 왼쪽 서브트리를 방문한다 3. 오른쪽 서브트리를 방문한다

전위순회 프로그램 순환 호출을 이용한다. preorder(x) if x≠NULL then print DATA(x); preorder(LEFT(x)); preorder(RIGHT(x));

전위 순회 응용 (예) 구조화된 문서출력

중위 순회 1. 왼쪽 서브트리를 방문한다 2. 루트 노드를 방문한다 3. 오른쪽 서브트리를 방문한다

중위순회 알고리즘 순환 호출을 이용한다. inorder(x) if x≠NULL then inorder(LEFT(x)); print DATA(x); inorder(RIGHT(x));

중위 순회 응용 (예) 수식 트리 4 6 5 7

후위 순회 1. 왼쪽 서브트리를 방문한다 2. 오른쪽 서브트리를 방문한다 3. 루트 노드를 방문한다

후위순회 알고리즘 순환 호출을 이용한다. postorder(x) if x≠NULL then postorder(LEFT(x)); postorder(RIGHT(x)); print DATA(x);

후위 순회 응용 (예) 디렉토리 용량 계산 “정지영상”디렉토리의 파일들의 총 합: 200 (정지영상의 서브디렉토리 없음) “정지영상”디렉토리의 파일들의 총 합: 200 (정지영상의 서브디렉토리 없음) “동영상”디렉토리의 파일들의 총 합: 500 (동영상의 서브디렉토리 없음) “그림”디렉토리의 파일들의 총 합: 100 (서브 디렉토리 제외) -- 그림 디렉토리 크기 총 합: 200 + 500 + 100 = 800

순회 프로그램 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // 15 // 4 20 // 1 16 25 TreeNode n1 = {1, NULL, NULL}; TreeNode n2 = {4, &n1, NULL}; TreeNode n3 = {16, NULL, NULL}; TreeNode n4 = {25, NULL, NULL}; TreeNode n5 = {20, &n3, &n4}; TreeNode n6 = {15, &n2, &n5}; TreeNode *root = &n6;

// 중위 순회 inorder( TreeNode *root ){ if ( root ){ inorder( root->left ); // 왼쪽서브트리 순회 printf("%d", root->data ); // 노드 방문 inorder( root->right ); // 오른쪽서브트리 순회 } // 전위 순회 preorder( TreeNode *root ){ preorder( root->left ); // 왼쪽서브트리 순회 preorder( root->right ); // 오른쪽서브트리 순회

// 후위 순회 postorder( TreeNode // 후위 순회 postorder( TreeNode *root ){ if ( root ){ postorder( root->left ); // 왼쪽서브트리 순회 postorder( root->right ); // 오른쪽서브트리순회 printf("%d", root->data ); // 노드 방문 } void main() { inorder(root); preorder(root); postorder(root);

레벨 순회 레벨 순회(level order)는 각 노드를 레벨 순으로 검사하는 순회 방법 레벨 순회는 큐를 사용하는 순회법 B C D C D D

레벨 순회 알고리즘 level_order(root) initialize queue; enqueue(queue, root); while is_empty(queue)≠TRUE do x← dequeue(queue); if( x≠NULL) then print DATA(x); enqueue(queue, LEFT(x)); enqueue(queue, RIGHT(x));

수식 트리 수식트리: 산술식을 트리형태로 표현한 것 예) 비단말노드: 연산자(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);

프로그램 typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; // + // * + // 1 4 16 25 TreeNode n1={1, NULL, NULL}; TreeNode n2={4, NULL, NULL}; TreeNode n3={'*', &n1, &n2}; TreeNode n4={16, NULL, NULL}; TreeNode n5={25, NULL, NULL}; TreeNode n6={'+', &n4, &n5}; TreeNode n7={'+', &n3, &n6}; TreeNode *exp= &n7;

int evaluate(TreeNode int evaluate(TreeNode *root) { if( root == NULL) return 0; if( root->left == NULL && root->right == NULL) return root->data; else { int op1 = evaluate(root->left); int op2 = evaluate(root->right); switch(root->data){ case '+': return op1+op2; case '-': return op1-op2; case '*': return op1*op2; case '/': return op1/op2; } void main() { printf("%d", evaluate(exp));

디렉토리 용량 계산 디렉토리의 용량을 계산하는데 후위 트리 순회 사용

디렉토리 용량 계산 프로그램 int calc_direc_size(TreeNode *root) { int size = 0, left_size = 0, right_size = 0; if (root != NULL) { left_size = calc_direc_size( root->left ); right_size = calc_direc_size(root->right ); size = root->data + left_size + right_size; } return size; void main() { TreeNode n4={500, NULL, NULL}; TreeNode n5={200, NULL, NULL}; TreeNode n3={100, &n4, &n5}; TreeNode n2={50, NULL, NULL}; TreeNode n1={0, &n2, &n3}; printf("디렉토리의 크기=%d\n",calc_direc_size(&n1)); 서브디렉토리의 개수가 최대 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; } 6 3 2 1 1 1

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

스레드 이진 트리 G C F A B D E 이진트리의 NULL 링크를 이용하여 순환호출 없이도 트리의 노드들을 순회 NULL 링크에 중위 순회시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리가 스레드 이진 트리(threaded binary tree) 4 G 2 6 C F 1 3 5 7 A B D E

스레드 이진 트리의 구현 오른쪽 링크에 자식노드의 주소가 저장되어 있는지 아니면 스레드(후속자 노드의 주소)가 저장되어 있는지를 구별해주는 태그 필드(is_thread)가 필요 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; } TreeNode; 만약 오른쪽 링크가 자식노드가 아닌 후속자 노드를 가리키면 is_thread는 TRUE

스레드 이진 트리의 구현 중위 후속자를 찾는 함수 작성 // TreeNode *find_successor(TreeNode *p) { // q는 p의 오른쪽 포인터 TreeNode *q = p->right; // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환 // NULL인 경우 후속자 노드가 없음을 의미 가장 마지막 노드를 의미 if( q==NULL || p->is_thread == TRUE) return q; // 만약 오른쪽 자식이면 다시 가장 왼쪽 노드로 이동 // 이 경우 오른쪽 자식(q)을 루트노드로 하는 서브트리의 가장 왼쪽 자손 // 노드가 p의 후속자 노드가 됨 while( q->left != NULL ) q = q->left; }

스레드 이진 트리의 구현 스레드 버전 중위 순회 함수 작성 void thread_inorder(TreeNode *t) { TreeNode *q = t; while (q->left) q = q->left;// 가장 왼쪽 노드로 간다. do printf("%c ", q->data); // 데이터 출력 q = find_successor(q); // 후속자 함수 호출 } while(q); // NULL이 아니면 }

이진탐색트리 탐색작업을 효율적으로 하기 위한 자료구조 모든 노드 x에 대하여 아래 조건을 만족하는 이진트리를 이진탐색트리(binary search tree)라 한다. key(x->left)≤key(x)≤key(x->right) 이진탐색를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

이진탐색트리에서의 탐색연산 주어진 키 값이 현재 노드의 키 값보다 작으면 탐색은 현재 노드의 왼쪽 자식을 기준으로 다시 시작한다. 주어진 키 값이 현재 노드의 키 값보다 크면 탐색은 현재 노드의 오른쪽 자식을 기준으로 다시 시작한다. 주어진 키 값이 현재 노드의 키 값과 같으면 탐색 성공

이진탐색트리에서의 탐색연산 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);

탐색을 구현하는 방법 순환적 방법 반복적 방법

순환적인 방법 //순환적인 탐색 함수 TreeNode *search(TreeNode *node, int key) { if ( node == NULL ) return NULL; if ( key == node->key ) return node; else if ( key < node->key ) return search(node->left, key); else return search(node->right, key); }

반복적인 방법 // 반복적인 탐색 함수 TreeNode *search(TreeNode *node, int key) { while(node != NULL){ if( key == node->key ) return node; else if( key < node->key ) node = node->left; else node = node->right; } return NULL; // 탐색에 실패했을 경우 NULL 반환

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

이진탐색트리에서의 삽입연산 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

이진탐색트리에서의 삽입연산 // key를 이진 탐색 트리에 삽입한다. // key가 이미 존재하면 삽입되지 않는다. void insert_node(TreeNode **root, int key) { TreeNode *p, *t; // p는 부모노드, t는 현재노드 TreeNode *n; // n은 새로운 노드 t = *root; p = NULL; // 탐색을 먼저 수행 while (t != NULL){ if( key == t->key ) return; p = t; if( key < t->key ) t = t->left; else t = t->right; }

이진탐색트리에서의 삽입연산 // key가 트리 안에 없으므로 삽입 가능 n = (TreeNode *) malloc(sizeof(TreeNode)); if( n == NULL ) return; // 데이터 복사 n->key = key; n->left = n->right = NULL; // 부모 노드와 링크 연결 if( p != NULL ) if( key < p->key ) p->left = n; else p->right = n; else *root = n; // empty tree인 경우 }

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

이진탐색트리에서의 삭제연산 CASE 2:삭제하려는 노드가 하나의 자식 노드만을 갖고 있는 경우 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 갖고 있음. 그 노드는 삭제하고 서브 트리는 부모 노드 위치로 올려준다.

이진탐색트리에서의 삭제연산 CASE 3:삭제하려는 노드가 두개의 자식 노드를 갖고 있는 경우 삭제노드의 successor 노드는 왼쪽 자식이 없음 successor를 삭제노드 위치로 이동시키고 successor의 오른쪽 자식(만약 존재한다면)은 successor 위치로 이동. 30

삭제 연산 구현 코드 교재 참조

이진탐색트리의 성능분석 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을때 h에 비례한다. h값은 트리의 형태와 노드의 개수 n에 따라 달라짐 h = log2n

이진탐색트리의 성능분석 최선의 경우 최악의 경우 h = n-1 h = log2n 이진 트리가 균형적으로 생성되어 있는 경우 한쪽으로 치우친 경사이진트리의 경우 h = n-1 순차탐색과 시간복잡도가 같다. h = log2n h = n-1