제 7 장. 트리(Tree)

7.1 트리의 정의

7.1 트리의 정의 ￭ 트리의 구성요소 ￭ 트리의 정의 - 정점(vertics)인 노드(node) - 그들을 연결하는 가지(branch)로 이루어진 그래프(graph)형식의 구조 - 나무나 가족 관계처럼 한 줄기에서 계속 가지를 치는 형태 ￭ 트리의 정의 ※ 트리 T는 한 개 이상의 노드들로 이루어진 유한집합으로 다음의 조건 을 만족한다. - 루트(root)로 불리는 특정한 1개의 노드가 존재한다. - 루트를 제외한 나머지 노드들은 T1,…,Tn (n≥0)의 부분집합으로 나뉘어지며, 이들 각각은 하나의 트리가 된다. 이때 이들 트리를 루트의 부트리(sub tree)라 한다.

7.1 트리의 정의 ※ 트리의 예

7.1 트리의 정의 ￭ 트리의 구조 - 부자관계(parent-child) : 한 가지(branch)로 연결된 두 노드 부모에 해당되는 노드는 자식에 해당되는 부트리(subtree)를 갖게 된다. - 차수(degree) : 각 노드가 가진 가지(자식)의 수 - 단노드(단말노드, terminal node) 또는 리프노드(leaf node) : 자식이 없는 차수가 0인 노드 - 간노드(비단말노드, nonterminal node) 또는 가지 노드(branch node) : 차수가 0이 아닌 자식을 갖고 있는 노드

7.1 트리의 정의 ※ 트리의 예

7.1 트리의 정의 ※ 트리의 예(용여의 예) 노드 (node) : A, B, C, D, E, F, G, H, I 근노드 (root node) : A 차수 (degree) : A의 차수 → 3, F의 차수 → 1, G의 차수 → 2 트리의 차수 (degree of tree) : 3 * 그 트리에 있는 노드의 최대차수 조상 노드(ancestor node) : G의 조상 노드는 A, D 자손 노드(descendent node) : G의 자손 노드는 I, J 부노드(parent node) : F의 부노드 B 자노드(children node) : B의 자노드 H 형제노드(brother node) : C의 자노드 B, D 간노드(nonterminal node) : A, B, D, F, G 단노드(terminal node) : C, E, H, I, J 높이(height) 혹은 깊이(depth) : 4 * 그 트리의 최대 레벨 * 노드의 레벨순서(level order) : 트리의 노드들에 레벨별로 위에서 아래로, 같은 레벨 안에서는 왼편에서 오른편으로 차례로 순서를 매긴 것 포레스트(forest)의 개수 : 3

7.1 트리의 정의 포리스트(숲, forest) - n0개의 분리된 트리의 집합 트리 T에서 루트 A를 제거한 결과로 얻은 포리스트 ※ 트리의 예(포리스트)

7.2 트리의 종류

7.2.1 순서트리(ordered tree)와 비순서 트리(oriented tree) ￭ 순서트리와 비순서 트리 구분하는 방법 ※ 각 노드들의 위치를 기준으로 보는 방법 - 트리에서 같은 레벨에 존재하는 노드들의 좌우 위치의 순서가 중요한 트리를 순서 트리(ordered tree)라고 하며, 위치상의 의미가 중요하지 않는 트리를 비순서 트리(oriented tree)라고 한다. <트리의 위치에 따른 분류의 예>

7.2.2 닮은 트리(similar tree)와 대등한 트리(equivalent tree) ￭ 구분 방법 ※ 노드의 수나 위치 등과 같은 트리의 구조는 같지만 노드의 자료가 다른 경우를 두개의 트리는 서로 닮은 트리(similar tree)라고 하고, 트리의 구조와 같은 위치에 동일한 자료를 갖고 있을 때 두 개의 트리는 대등한 트리(equivalent tree)라 한다. <닮은 트리의 예>

7.2.3 이진트리(binary tree) ￭ 이진트리(binary tree) ※ 트리를 형성하는 각 노드들의 차수(degree)에 제한을 두는 것 : 원칙적으로 이진트리는 각 노드의 차수가 2 또는 0일 경우 즉, 공집합이거나 좌,우측 서브트리(subtree)로 분리된 트리에 의해 구성된 집합체. ※ 일반 트리와 이진트리의 차이점 : 공백의 이진트리가 존재한다는 점과 이진트리는 순서 트리(ordered tree)라는 점 즉, 이진 트리에는 공백 이진 트리가 있지만, 일반 트리에는 공백 트리가 없음 이진 트리에서는 서브 트리의 순서를 구분

7.2.3 이진트리(binary tree) ￭ 이진트리(binary tree)의 종류 ※ 엄밀한 이진트리 : 각 노드의 차수(degree)가 2 혹은 0인 이진트리 ※ 크누스 이진트리(Knuth binary tree) : 각 노드의 차수(degree)가 2이하인 이진트리 <트리의 예> 엄밀한 이진트리 크누스 이진트리

<엄밀한 이진트리(a) Knuth 이진트리(b) 사향 이진트리(c,d)> 7.2.3 이진트리(binary tree) ※ 사향 이진트리(경사, skewed binary tree) : 모든 노드가 좌,우 어느 한쪽으로만 치우쳐 있는 이진트리 <엄밀한 이진트리(a) Knuth 이진트리(b) 사향 이진트리(c,d)>

7.2.3 이진트리(binary tree) ※ 정이진트리(full binary tree) : 각 레벨에 존재하는 노드의 개수가 정확히 2k-1개(k: 트리의 깊이 (depth))로 구성된 트리 = 2k-1 ※ 전이진트리(complete binary tree) : 깊이(depth)가 k인 이진트리가 k-1 레벨까지는 정이진트리와 같은 수의 노드를 갖고 k레벨에서는 왼쪽부터 오른쪽으로 노드들이 순 차적으로 존재하는 트리를 말한다. 2k-1 - 1 < n < 2k - 1

7.2.3 이진트리(binary tree) ※ 전이진트리(a)와 정이진트리(b)의 예

7.3 트리의 표현법

7.3.1 연속 배열을 이용하는 방법 ※ 이진트리를 정이진트리라 가정하고 적용하는 방법 : 레벨 순서대로 왼쪽에서 오른쪽 순서로 최대 2k-1개(k : 깊이)의 할당된 기억장소에 연속적으로 저장시킨다. <이진트리의 배열 표현>

7.3.1 연속 배열을 이용하는 방법 ※ 저장방법 ① 트리의 루트는 배열 T[1]에 저장된다. ② 노드의 부모 노드는 i≠1일 경우 ⌊i/2⌋의 위치에 있게 된다. 따라서 i=1일 경우에는 i는 루트이므로 부모가 없다. ③ 노드 i의 왼쪽 자식 노드는 2i≤n일 경우, 2i의 위치에 있게 된다. 따라서 2i>n이면 i는 왼쪽 자식을 가질 수 없다. ④ 노드 i의 오른쪽 자식 노드는 2i+1≤n일 경우, 2i+1의 위치에 있게 된다. 따라서 2i+1>n이면 i는 오른쪽 자식 노드를 가질 수 없다.

7.3.2 연속 리스트를 이용하는 방법 ※ 일반트리의 문제점 - 노드의 차수(degree)가 일정하지 않기 때문에 노드들의 차수에 의해 결정되는 기억공간들을 할당하기가 어려움 ※ 문제해결 - 모든 노드들의 차수 중 최대의 차수인 트리의 차수로 노드들의 링크 의 개수를 결정하며 이들 링크들은 자신에게 연결된 자노드의 위치를 알려주게 된다.

7.3.2 연속 리스트를 이용하는 방법 ※ 연결 리스트 노드 구조 struct node { struct node *left_child; char data; struct node *right_child; }

7.3.2 연속 리스트를 이용하는 방법 ※ 연결 리스트를 이용한 일반 트리의 표현

7.3.3 일반 트리를 이진트리로 변환하는 방법 ① 각각의 모든 제노드(brother node)들을 수평선으로 연결한다. <변환전의 일반 트리>

7.3.3 일반 트리를 이진트리로 변환하는 방법 ② 부노드(parent node)에서 자노드(children node)로 연결된 가지 (branch) 중 맨 좌측의 가지만 제외하고 모두 제거한다. < 일반 트리에서 이진트리로의 변환 1단계>

7.3.3 일반 트리를 이진트리로 변환하는 방법 ③ 왼쪽과 오른쪽의 부트리(subtreee)를 구별하기 위해 맨 좌측의 가지를 기준으로 시계 방향으로 45°방향으로 끌어 당겨준다. < 일반 트리에서 이진트리로의 변환 완료>

<트리군(forest)의 예> 7.3.3 일반 트리를 이진트리로 변환하는 방법 ￭ 포리스트(forest)를 이진트리로 변환하는 방법 ① 인 경우, 즉 이면, 대응되는 이다 ② 인 경우, 루트는 의 루트 , 왼쪽 부트리는 의 부트리 , 오른쪽 부트리는 로 구성된다. <트리군(forest)의 예>

7.3.3 일반 트리를 이진트리로 변환하는 방법 ※ 여러 트리들을 하나의 이진트리로의 변환 과정(1)

7.3.3 일반 트리를 이진트리로 변환하는 방법 ※ 여러 트리들을 하나의 이진트리로의 변환 과정(2)

7.3.3 일반 트리를 이진트리로 변환하는 방법 ※ 여러 트리들을 하나의 이진트리로의 변환 과정(3)

7.4 이진트리의 운행

7.4 이진트리의 운행 ￭ 운행(traversal) - 트리내의 각 노드들을 중복되지 않게 한 번씩만 찾아가는 것을 의미 - 운행될 때에는 모든 노드들을 방문(visit) ※ 이진트리의 운행 알고리즘 단계 - 자료부분인 루트(root)의 방문, - 왼쪽 부트리의 운행 - 오른쪽 부트리의 운행 ※ 각 단계의 진행 순서에 따른 운행법 - 중위 운행(in-order traversal) - 후위 운행(post-order traversal) - 전위 운행(pre-order traversal) LEFT, ROOT, RIGHT : 중위 운행 LEFT, RIGHT, ROOT : 후위 운행 ROOT, LEFT, RIGHT : 전위 운행 ROOT, RIGHT, LEFT RIGHT, ROOT, LEFT RIGHT, LEFT, ROOT

7.4 이진트리의 운행 ￭ 전위 운행(pre-order) 1. 루트를 방문하다. 2. 왼쪽 부트리를 전위운행 방법으로 운행한다. 3. 오른쪽 부트리를 전위운행 방법으로 운행한다. 1. void preorder(struct node *node) 2. { 3. if(node != NULL) 4. { 5. printf("%c\n", node->data); 6. preorder(node->left_child); 7. preorder(node->right_child); 8. } 9. }

7.4 이진트리의 운행 ￭ 전위 운행(pre-order)의 예

7.4 이진트리의 운행 ￭ 중위 운행(in-order) 1. 왼쪽 부트리를 전위운행 방법으로 운행한다. 2. 루트를 방문한다. 3. 오른쪽 부트리를 전위운행 방법으로 운행한다. 1. void inorder(struct node *node) 2. { 3. if(node != NULL) 4. { 5. inorder(node->left_child); 6. printf("%c\n", node->data); 7. inorder(node->right_child); 8. } 9. }

7.4 이진트리의 운행 ￭ 전위 운행(pre-order)의 예(반복문 이용) 1. voiditerinorder (treePointer ptr) 2. { 3. int top = -1; 4. treePointer stack[MAX_SIZE]; 5. for (;;) 6. { 7. for (; ptr; ptr=ptr->leftChild) 8. add(&top, ptr); 9. ptr = delete(&top); 10. if (!ptr) break; 11. printf("%c", ptr->data); 12. ptr= ptr->rightChild; 13. } 14. }

7.4 이진트리의 운행 ￭ 후위 운행(pos-order) 1. 왼쪽 부트리를 전위운행 방법으로 운행한다. 2. 오른쪽 부트리를 전위운행 방법으로 운행한다. 3. 루트를 방문한다. 1. void postorder (struct node *node) 2. { 3. if (node != NULL) 4. { 5. postorder(node->left_child); 6. postorder (node->right_child); 7. printf("%c", node → data); 8. } 9. }

7.4 이진트리의 운행 ￭ 전위 운행(pre-order)의 예

7.4 이진트리의 운행 ￭ 전위 운행(pre-order)의 예

7.4 이진트리의 운행 ￭ 여러가지 트리의 운행 법 (a) (b) 전위 운행 /+*+ab/cd％efg MEBADLPNVTZ 중위 운행 a+b*c/d+e％f/g ABDELMNPTVZ 후위 운행 ab+cd/*ef％+g/ ADBLENTZVPM

7.4 이진트리의 운행 ￭ 비 순환적 중위 운행 방법의 정의 1. #define maxsize 10 2. void nonrecursive_inorder(current_node) 3. struct node { 4. struct node *lchild; 5. char data; 6. struct node *rchild; }; 7. struct node *courrent_node; 8. { 9. /* 스택의 top 포인터 초기화 */ 10. int top = 0; 11. /* 부모 노드로 되돌아가기 위하여 사용되는 포이터용 스택 배열 정의 */ 12. struct node *stack[maxsize]; 13. enum boolean {FALSE, TRUE} done; 14. /* 반복 조건의 초기화 */ 15. done = TRUE; 16. do{ 17. /* 현재의 노드 주소를 스택에 저장한 후 왼쪽 서브트리로 이동 */ 18. while(current_node != NULL) { 19. top=top+1; 20. if(top>maxsize){

7.4 이진트리의 운행 21. printf("stack overflows \n"); 22. exit(1);};/* end if */ 23. /* 스택에 push() */ 24. stack[top]=current_node; 25. /* 실제 왼쪽 서브트리로 이동 */ 26. current_node=current_node -> lchild; 27. }/* end while */ 28. 29. /* 근노드 출력 및 오른쪽 서브트리로 이동 */ 30. if(top!=0) { 31. current_node=stack[top]; 32. /* 스택에서 pop() */ 33. top=top-1; 34. printf("%c", current_node -> data); 35. current_node=current_node -> rchild;}; 36. else 37. done=FALSE; 38. }/* end if */ 39. }while(done); /* end do while */ 40. }/* end nonrecursive_inorder */

7.4 이진트리의 운행 ￭ 산술식 a/b+(c-d)*e에 대한 이진트리의 예

7.4 이진트리의 운행 ￭ 노드의 기억 장소 주소를 부여한 이진트리

7.5 트리의 경로 길이

7.5 트리의 경로 길이 ￭ 탐색 길이 기대 값(탐색이 성공적으로 끝났을 경우) Ci : 키 ki에 도달하기까지 요구되는 비교횟수 Si : 키 ki가 탐색의 대상이 될 확률 ￭ 탐색 길이 기대 값(탐색이 비정상적으로 끝났을 경우) Ii : 노드 Ri에 대해 탐색이 비성공적으로 끝났을 때의 비교 횟수 Pu : 비성공적으로 탐색할 확률

7.6 트리의 삽입과 삭제

7.6.1 이진트리에 구성된 노드들에 대한 배열 위치 부여 방법 ￭ 이진트리와 연결 표현 배열에서의 각 노드의 위치는 왼쪽 서브트리를 기준으로 순서화한다.

7.6.1 이진트리에 구성된 노드들에 대한 배열 위치 부여 방법 ￭ 이진트리와 연결 표현 DATA LCHILD RCHILD 1 + 2 5 / 3 4 a NULL b * 6 7 - 8 9 e c d

7.6.2 삽입 조작의 예 ￭ ‘*’와 ‘f’ 가 노트가 삽입된 이진트리

7.6.1 삽입 조작의 예 ￭ 이진트리와 연결 표현 DATA LCHILD RCHILD 1 + 2 5 / (10) 4 3 a NULL b * 6 7 - 8 9 e c d 10 (*) (3) (11) 11 (f) (NULL)

7.6.2 삭제 조작의 예 ￭ 삭제 후 이진트리에 대응되는 산술식:(f*a)/b+(c-d)

7.6.1 삽입 조작의 예 ￭ 이진트리와 연결 표현 DATA LCHILD RCHILD 1 + 2 (6) / 10 4 3 a NULL b 5 6 - 8 9 7 c d * 11 f (NULL)

7.7 스레드(된) 이진트리(Threaded Binary Tree)

7.7 스레드 이진트리 ￭ 전위 운행 스레드 이진트리

7.7.1 스레드 이진트리의 표현법 ￭ 스레드 이진트리의 노드 구조 ※ 각각의 노드 구조의 필드 의미 ① leftThread=FALSE이면, leftchild=정상적인 연결 필드 ② leftThread=TRUE이면, leftchild=스레드 연결 필드 ③ rightThread=FALSE이면, rightchild=정상적인 연결 필드 ④ rightThread=TRUE이면, rightchild=스레드 연결 필드 1. struct ThreadNode { 2. int info ; 3. Node left ; 4. Node right ; 5. Node righThread; 6. Node leftThread; 7. }

7.7.1 스레드 이진트리 ￭ 산술식 a/b+(c-d)*e에 대한 스레드 이진트리 표현

7.7.1 스레드 이진트리 ￭ rightThread(알고리즘) 1. struct ThreadBinTree { 2. public void inorder (Node firstin) { 3. Node p; 4. p = firstin ; 5. while (p != null) { 6. System.out.println(p.info) ; 7. p = p.rightThread; 8. } 9. } 10. } ￭ 단노드의 포인터를 이용한 전위 순회 스레드 이진트리(알고리즘) 1. type nodeptr = ↑nodetype; 2. nodetype = record 3. left : nodeptr; 4. threadflag:0..1; 5. info:integer; 6. right:nodeptr 7. end;

7.7.1 스레드 이진트리 ￭ 단노드의 포인터를 이용한 전위 순회 스레드 이진트리

7.7.2 스레드 이진트리의 중위 운행 ￭ 스레드 이진트리의 중위 운행 표현 예 중위 운행 순서 : D G B E A F H C

7.7.2 스레드 이진트리의 중위 운행 ￭ 스레드 이진트리의 중위 운행 표현 예(알고리즘) 1. threadedPoiner insucc(threadedPointer tree) 2. { 3. threadedPointer temp; 4. temp = tree->rightChild; 5. if (!tree->rightThread) 6. while (!temp->leftThread) 7. temp = temp->leftChild; 8. return temp; 9. } 11. void tinorder (threadedPointer tree) 12. { 13. threadedPointer temp = tree; 14. for (;;) 14. { 15. temp = insucc(temp); 16. if (temp == tree) break; 17. printf("%c", temp->data); 18. } 19. }

7.7.2 스레드 이진트리의 중위 운행 ￭ 스레드 트리의 운행 결과(DGBEAFHC)

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 스레드 이진트리의 알고리즘 1. struct ThreadBinTree { 2. .... 3. public void insert(TNode X, TNode Y) { 4. Y.left = null; 5. Y.right = X.right; 6. Y.leftthread = X; 7. Y.rightthread = X.rightthread; 8. X.right = Y; 9. X.rightthread = Y; 10. } 11. };

7.7. 3 스레드 트리 노드의 삽입․삭제 ￭ 이진트리의 노드 삽입 결과

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 스레드 트리의 오른쪽 부트리가 없을 경우 오른쪽 노드 삽입 방법 ① parent의 rightThread 값을 거짓으로 한다. ② child의 leftThread 와 child의 rightThread 값을 참으로 한다. ③ child의 leftChild가 parent를 가리키도록 한다. ④ child의 rightChild 값을 parent 의 rightChild 값으로 한다. ⑤ parent의 rightChild 가 child를 가리키도록 한다.

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 오른쪽 부트리가 없을 경우 오른쪽 노드 삽입 스레드 이진트리

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 오른쪽 부트리가 있을 경우 오른쪽 노드 삽입 스레드 이진트리

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 오른쪽 부트리가 없을 경우(알고리즘) 1. void insertRight (threadedPointer parent, threadedPointer child) 2. { 3. threadedPointer temp; 4. child->rightChild = parent->rightChild; 5. child->rightThread = parent->rightThread; 6. child->leftChild = parent; 7. child->leftThread = true; 8. parent->rightChild = child; 9. parent->rightThread = false; 10. if (!child->rightThread) { 11. temp = insucc(child); 12. temp->leftChild = child; 13. } 14. } ￭ 오른쪽 부트리가 있을 경우 오른쪽 노드 삽입 스레드 이진트리

7.7.3 스레드 트리 노드의 삽입․삭제 ￭ 오른쪽 부트리가 있을 경우(알고리즘) 1. type nodeptr = &nodetype; 2. nodetype = record 3. left : nodeptr; 4. info : integer; 5. right : nodeptr; 6. leftthread : nodeptr; 7. rightthread : nodeptr; 8. parent : nodeptr 9. end;

7.7.4 이진 탐색 트리의 균형 ￭ 오른쪽 부트리가 있을 경우(알고리즘) ※ 이진 탐색 트리의 성능 트리의 구조와 노드에 접근하는 확률에 의해 결정되며, 트리의 구조는 노드의 삽입이나 삭제에 의해 결정된다. ※ 휴리스틱(heuristic) 알고리즘 최적에 가까운 이진 탐색 트리를 만들어 냄 1. 접근 빈도가 높은 키를 가진 노드를 트리의 루트에 가깝게 놓는다. 2. 좌측과 우측 서브트리가 가능한 같은 수의 노드를 가질 수 있게 한다.

7.7.5 AVL-트리 ￭ AVL트리 - 높이가 균형된 트리(height balanced tree) <균형된 트리의 예>

7.7.5 AVL-트리 ￭ 회전을 통한 불균형 AVL트리의 재구성 LL: Y는 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입. LR: Y는 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입. RL: Y는 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입. RR: Y는 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입

7.7.5 AVL-트리 ￭ 노드삽입(1)

7.7.5 AVL-트리 ￭ 노드삽입(2)

7.7.5 AVL-트리 ￭ 노드삽입(3)

7.7.5 AVL-트리 ￭ 노드삽입(4)

7.7.5 AVL-트리 ￭ 노드삽입(5)

7.7.5 AVL-트리 ￭ 노드삽입(6)

7.7.6 BB-트리 ￭ BB트리 - 무게(weight)가 균형된 트리 - 무게를 균형 있도록 유지한다는 의미로 좌,우측 부트리에서 총 노드수의 제약을 둔 트리이다. - 균형을 제어하기 위해 인수 β(0<β≤½)를 사용

7.8 B 트리의 실습

7.8 B 트리의 실습 ￭ 교재 참조.