슬라이드 1

Transcription

1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005

2 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀

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

4 이진트리 (binary tree) 이진트리 (binary tree) : 모든노드가 2 개의서브트리를가지고있는트리 서브트리는공집합일수있다. 이진트리 (binary tree) 이진트리의노드에는최대 2 개까지의자식노드가존재 모든노드의차수가 2 이하가된다 -> 구현하기가편리함 이진트리에는서브트리간의순서가존재

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

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

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

8 이진트리의표현 배열표현법 : 모든이진트리를포화이진트리라고가정하고각노드에번호를붙여서그번호를배열의인덱스로삼아노드의데이터를배열에저장하는방법 링크표현법 : 포인터를이용하여부모노드가자식노드를가리키게하는방법

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

10 전위순회 루트를먼저방문하는순회방법 응용분야 : ( 예 ) 구조화된문서출력 1 // 전위순회 preorder( TreeNode *root ){ if ( root ){ printf("%d", root->data ); // 노드방문 preorder( root->left );// 왼쪽서브트리순회 preorder( root->right );// 오른쪽서브트리순회 } } 자료구조 자료구조와알고리즘이란? 2. 기초적인자료구조 3. 고급자료구조 자료구조 1.2 알고리즘 2.1 스택 2.2 큐 2.3 리스트 3.1 트리 3.2 그래프

11 중위순회 왼쪽서브트리-> 루트-> 오른쪽서브트리순으로방문 * / a b c d // 중위순회 inorder( TreeNode *root ){ if ( root ){ inorder( root->left );// 왼쪽서브트리순회 printf("%d", root->data ); // 노드방문 inorder( root->right );// 오른쪽서브트리순회 } } 8

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

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

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

15 이진트리연산 : 노드개수 탐색트리안의노드의개수를계산 각각의서브트리에대하여순환호출한다음, 반환되는값에 1 을더하여반환 6 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; }

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

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

18 이진탐색트리 탐색작업을효율적으로하기위한자료구조 key( 왼쪽서브트리 ) key( 루트노드 ) key( 오른쪽서브트리 ) 이진탐색를중위순회하면오름차순으로정렬된값을얻을수있다.

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

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

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

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

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

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

25 이진트리연산 : 노드개수