CHAPTER 5 트리(Tree)

5.1 트리의 정의 및 용어 정의) 트리(tree) : 1개 이상의 노드로 이루어진 유한 집합 1) 루트(root)라고 하는 노드가 하나 존재 2) 나머지 노드들은 n≥0개의 분리집합 T1,T2,…,Tn 으로 분리. 3) T1,T2,…,Tn 은 각각 하나의 트리이며, 루트의 서브트리(subtree). ` A B C D G J K L E F H I 4 3 2 1 T1 T2 T

트리의 용어 트리의 차수(degree) : 서브트리의 개수 부모 노드(parent node) : 상위 레벨에 있으면서 에지로 연결된 노드 자식 노드(child node) : 하위 레벨에 있으면서 에지로 연결된 노드 터미널 노드(terminal node) 또는 리잎(leaf) : 자식 노드가 없는 노드 비 터미널 노드(non-terminal node) : 터미널 노드가 아닌 노드 형제/자매 노드(siblings) : 같은 레벨에 있으면서 같은 부모를 가진 노드 선조(ancestors) : 루트로부터 그 노드까지의 연결된 노드 후손(descendents) : 그 노드의 서브트리내의 모든 노드 트리의 높이(height)/길이(depth) : 트리에 속한 노드의 최대 레벨

5.2 트리의 표현 리스트표현 (A(B(D(H,I)E),C(F,G))) A B D H I E C F G A B C D E F (2)트리표현 (3)집합표현 (4)들여쓰기표현

5.2 트리의 표현 트리를 연결 리스트로 나타내기 위해서 서브트리 개수만큼의 링크 필드가 필요 => 링크 필드의 메모리를 낭비. 트리를 차수가 2인 트리로 표현하여 링크 필드를 절약 <차수가 2인 이진 트리(binary tree)로 변환한 경우> 이진 트리로 변환하는 방법 : 루트로부터 시작하여 왼쪽 링크 필드에는 자식 노드를, 오른쪽 링크 필드에는 형제/자매 노드를 연결. < 이진 트리의 리스트 표현> data left child right sibling

5.3 이진 트리 정의) 이진 트리 : 공집합이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 부르는 두 개의 분리된 이진 트리로 구성된 노드의 유한집합 이진 트리의 종류 완전이진트리(complete binary tree) 완전이진트리 깊이가 k인 이진 트리에 차례대로 붙인 1부터 n까지의 번호에 노드들이 1대1로 대응하는 트리 사향이진트리(skewed binary tree) 노드가 한쪽 방향으로만 치우진 이진트리 A B C D E F A B C A B C 사향이진트리 완전이진트리

(1) 이진 트리의 특성 ① 이진 트리의 레벨 i에서의 최대 노드 수는? 깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수는? ② 모든 이진 트리 T에 대해서 ③ 깊이가 k인 완전 이진 트리(full Binary Tree)의 노드 수는?         

(2) 이진 트리의 표현 배열 또는 연결 리스트를 이용하여 표현 ① 배열을 이용한 표현 이진트리의 각 노드들을 자기 위치번호에 맞는 배열의 인덱스 위치에 저장 n개의 노드를 가진 완전 이진 트리 ( )에서 인덱스 i번째 노드인 경우에 깊이 k인 완전 이진 트리는 2k-1의 노드를 저장할 수 있는 기억장소가 필요. 경사 이진 트리인 경우에는 2k-1개의 기억장소 중 k개만 사용하므로 기억장소가 낭비 => 연결리스트를 이용하여 문제 해결.

(2) 이진 트리의 표현 배열 또는 연결 리스트를 이용하여 표현 ② 연결 리스트를 이용한 표현 배열을 이용하여 표현할 경우 트리 중간의 노드를 삽입 또는 삭제할 때 노드가 저장된 위치를 변경해야 하는 경우가 발생하는 문제를 해결하기 위하여 연결 리스트를 사용. 각 노드별 왼쪽자식(leftChild)과 오른쪽 자식(rightChild)을 가리키는 두 개의 링크 필드를 정의.

(2) 이진 트리의 표현

5.4 이진 트리 순회(Binary Tree Traversal) 중위순회(Inorder Traversal) : 왼쪽 서브트리 중위순회 → 루트 방문 → 오른쪽 서브트리 중위순회 후위순회(Postorder Traversal): 왼쪽 서브트리 후위순회 → 오른쪽 서브트리 후위 순회 → 루트 방문 전위순회(Preorder Traversal): 루트 방문 → 왼쪽 서브트리 전위순회 → 오른쪽 서브트리 전위 순회

5.4 이진 트리 순회(Binary Tree Traversal) 예) X/Y*Z*A+B 중위 표기(사각형은 NULL 노드)

5.4 이진 트리 순회(Binary Tree Traversal) ① 중위순회(Left - Visit - Right) ⅰ) NULL 노드에 도달할 때까지 Left(왼쪽) 방향으로 이동 ⅱ) NULL 노드에 도착하면 NULL 노드의 부모를 Visit ⅲ) Right(오른쪽) 방향으로 순회 계속 void  inorder(treePtr  ptr) {   if(ptr) {    ① inorder(ptr→leftChild);    ② printf("%s", ptr→data);    ③ inorder(ptr→rightChild);   } } 순서 : X/Y*Z*A+B

5.4 이진 트리 순회(Binary Tree Traversal) ② 전위순회(Visit - Left - Right) ⅰ) 루트부터 노드를 Visit ⅱ) NULL 노드에 도착할 때가지 왼쪽(Left) 방향으로 이동 ⅲ) NULL 노드에 도착하면 오른쪽(Right) 방향으로 이동 void  preorder(treePtr  ptr) {   if(ptr) {     printf("%s", ptr→data);     preorder(ptr→leftChild);     preorder(ptr→rightChild);   } } 순서 : +**/XYZAB

5.4 이진 트리 순회(Binary Tree Traversal) ③ 후위순회(Left - Right - Visit) 왼쪽 서브트리의 모든 노드들을 출력하고, 오른쪽 서브트리의 모든 노드들을 출력한 후 부모 노드를 출력한다. void  postorder(treePtr  ptr) {   if(ptr) {     postorder(ptr→leftChild);     postorder(ptr→rightChild);     printf("%s", ptr→data);   } } 순서 : XY/Z*A*B+

5.4 이진 트리 순회(Binary Tree Traversal) <전위 운행> 1 N 3 2 2-1 3-1 2-2 2-3 3-2 3-3 3-3

5.4 이진 트리 순회(Binary Tree Traversal) <중위 운행> 2 N 3 1 1-2 3-2 1-1 1-3 3-1 3-3 3-3

5.4 이진 트리 순회(Binary Tree Traversal) <후위 운행> 3 N 2 1 1-3 2-3 1-1 1-2 2-1 2-2 3-3

5.4 이진 트리 순회(Binary Tree Traversal) 전위 운행 순서 중위 운행 순서 후위 운행 순서 ABDHIECFG A B C HDIBEAFCG F D E G HIDEBFGCA H I

5.5 쓰레드 이진 트리(Thread Binary Tree) 터미널 노드인 경우에 자식 노드가 없으므로 (n + 1)개의 NULL 링크가 발생 쓰레드 이진 트리 : 사용되지 않는 NULL 링크를 다른 노드를 가리키게 이진트리를 구성한 것 메모리 낭비  ptr→leftChild = (중위순회 선행 노드) ptr→rightChild = (중위순회 후행 노드)

5.5 쓰레드 이진 트리(Thread Binary Tree) ① 초기 쓰레드 트리 : ‘head node’만 존재. ② 생성된 쓰레드 트리 : ‘head node’로부터 연결.                                     

5.5 쓰레드 이진 트리(Thread Binary Tree) 중위순회 후행 노드 찾는 방법 if ptr→rightThread = TRUE then ptr→rightChild;                                      (후행 노드) else {   temp = ptr→rightChild;   while(!temp→leftThread) {     temp = temp→leftChild;     (후행 노드)   }   return  temp; }

5.5 쓰레드 이진 트리(Thread Binary Tree) 2) 노드 삽입 ⅰ) 오른쪽 서브트리가 공백인 부모 오른쪽에 자식으로 삽입 parent→rightThread = FALSE child→leftThread = TRUE child→rightThread = TRUE child→leftChild = parent child→rightChild = parent→rightChild parent→rightChild = child ⇒

5.5 쓰레드 이진 트리(Thread Binary Tree) 2) 노드 삽입 ⅱ) 오른쪽 서브트리가 공백이 아닌 경우 child→rightChild = parent→rightChild child→rightThread = parent→rightThread         /* FALSE */ child→leftThread = TRUE child→leftChild = parent parent→rightChild = child parent→rightThread = FALSE child의 중위순회가 자식을 가리키게 함 temp→leftChild = child

5.6 히프(Heap) 트리 히프 트리에 관한 용어 정의) ․ MAX 트리 : 각 노드의 key 값이 자식의 key 값보다 작지 않은 트리 ․ MAX 히프 : MAX 트리인 완전 이진 트리 ․ MIN 트리 : 각 노드의 key 값이 자식의 key 값보다 크지 않은 트리 ․ MIN 히프 : MIN 트리이면서 완전 이진 트리 히프 트리의 예)  MAX 히프 MIN 히프

5.6 히프(Heap) 트리 히프 트리를 이용하여 가능한 연산. ․ 공백 히프의 생성 ․ 히프에 새 원소 삽입 ․ 히프에서 가장 큰 원소 삭제 새로운 원소 13을 삽입하는 과정

5.7 이진 탐색 트리(Binary Search Tree) 정의) 이진 탐색 트리     ① 공백(empty)이거나     ② 공백이 아니면 다음 성질을 만족한다.       ⅰ) 모든 원소는 key를 가지며, key는 유일한 값을 가진다.       ⅱ) 왼쪽 서브 트리에 있는 key들은 루트의 key 보다 작다.       ⅲ) 오른쪽 서브 트리에 있는 키들은 루트의 key 보다 크다.       ⅳ) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 예)

5.7 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리를 이용한 연산 (1) 탐색(Search) key 값이 k인 노드를 탐색하기 위한 알고리즘은 다음과 같다. ⅰ) if 루트 == NULL return NULL; ⅱ) else         if 루트 key == k return 루트;         else if 루트 key < k           오른쪽 서브트리 탐색         else 왼쪽 서브트리 탐색 (2) 삽입(Insert) key 값이 k인 노드를 삽입하는 알고리즘은 다음과 같다. ⅰ) k가 있는지 탐색한 후 ⅱ) 탐색이 종료된 시점에 삽입

5.7 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리의 노드 삽입 과정 )

5.7 이진 탐색 트리(Binary Search Tree) (3) 노드 삭제(Delete) key 값이 k인 노드를 탐색하기 위한 알고리즘은 다음과 같다. ⅰ) 삭제하고자 하는 노드가 터미널노드 일 때 → NULL로 만들고 반환(return) ⅱ) 삭제하고자 하는 노드가 하나의 자식만을 가지는 비단말노드(예: 60) 일 때 ⅲ) 삭제하고자 하는 노드가 두 개의 자식을 가지는 비단말노드 일 때 → 왼쪽 서브트리에서 가장 크거나, 오른쪽 서브트리에서 가장 작은 것을 대체 예) ’70’을 삭제하고자 한다면, ①’65’를’70’이 있던 자리로 이동하고 ②’62’를’65’가 있던 자리로 이동한다.

5.8 선택 트리(Selection Tree) 선택 트리는 두 개의 자식 노드 중에서 원하는 것을 선택하는 과정을 표현. 아래 그림은 자식 노드로부터 가장 작은 수를 선택하는 과정을 보인다.

5.9 포리스트(Forest) 정의) 포리스트 : 포리스트를 이진 트리로 변환하는 과정. 포리스트를 이진 트리로 바꾸는 예) n ≥ 0개의 분리된 트리의 집합. 이진 트리에서 루트를 제거하면 포리스트가 된다. 포리스트를 이진 트리로 변환하는 과정. ․포리스트 : T1, T2,…, Tn ․이진트리 : B(T1, T2,…, Tn)    ⅰ) n = 0이면 B = 공백    ⅱ) B는 T1과 같은 루트를 가지며, 왼쪽 서브트리로 B(T11, T12,…, T1m) 을 가진다. 단, T11, T12,…, T1m 은 T1 의 서브트리이다. 오른쪽 서브트리는 B(T2, …, Tm) 이다. 포리스트를 이진 트리로 바꾸는 예) 

5.10 AVL 트리 AVL 트리 : 탐색 고정에서 노드의 비교 횟수가 비교적 적게 하기 위하여 서브트리들의 높이가 균형을 이루는 이진 트리. AVL 트리를 유지하는 과정의 예) 입력순서 : Mar, May, Nov, Aug, Apr, Jan, Dec, July, Feb, June, Oct, Sept 

5.11 2-3 트리(Two-three Trees) 정의) 2-3 트리 ① 공백이거나 ② 다음의 특성을 만족하는 탐색 트리. 정의) 2-3 트리      ① 공백이거나     ② 다음의 특성을 만족하는 탐색 트리.    Data_l Data_l.key , data_r

5.11 2-3 트리(Two-three Trees)    , data_r Data_l.key Data_r.key

5.12 B-트리(B-tree) 인덱스가 메인 메모리에 적재할 수 없을 정도로 클 경우에 사용.    인덱스가 메인 메모리에 적재할 수 없을 정도로 클 경우에 사용. AVL, 2-3 트리 등은 테이블이 모두 메인 메모리에 적재될 때 유용함. 정의) M-way 탐색트리(Search Tree) :     ① 공백이거나     ② 다음의 성질을 만족한다.       ⅰ) 루트는 많아야 m개의 서브트리를 가짐                 ⅱ) 1 ≤ i 〈 n에 대하여 Ki < Ki+1       ⅲ) 서브트리 Ai (0〈i〈n) 내의 모든 값은 Ki+1 보다는 작고 Ki 보다는 크다.       ⅳ) 서브트리 An 내의 모든 값들은 Kn 보다 크고 의 A0 모든 값들은 K1보다 작다.       ⅴ) 서브트리 Ai (0≤i≤n)은 m-way 탐색트리이다.   

5.12 B-트리(B-tree) AVL 트리는 2-way 탐색트리이며, 2-3 트리는 3-way 탐색트리이다. 예)    AVL 트리는 2-way 탐색트리이며, 2-3 트리는 3-way 탐색트리이다. 예) 정의) 차수 m인 B-트리 :   ① 공백이거나   ② m-way 탐색트리이다.     ⅰ) 루트는 적어도 2개의 자식 가짐     ⅱ) 루트와 외부노드를 제외한 모든 노드는 m/2개이상 m개이하의 자식 가짐     ⅲ) 모든 외부노드는 동일 레벨에 있음   a