[DB-26] 자료구조 - 트리 (Tree)

1. 트리의 정의 

• Linked List로 표현할 때 가장 효율적임
• 계층형 구조(hierarchical structure)를 나타내기 편리함

2. 트리의 용어 정리

• Node - Tree의 기본 구성요소 (A, B, C, D, E, F, G, H)
• 근 노드(Root Node) - 가장 상위에 위치한 노드 (A)
• 레벨(Level) - 근 노드를 기준으로 특정 노드까지의 경로 길이 (E의 레벨은 3)
• 조상 노드(Ancestors Node) - 특정 노드에서 루트에 이르는 경로상의 모든 노드 (D의 조상 노드 B, A)
• 자식 노드 - 특정 노드에 연결된 다음 레벨의 노드 (B의 자식 노드 D, E)
• 부모 노드 - 특정 노드에 연결된 이전 레벨의 노드 (F의 부모 노드 D)
• 형제 노드(Sibling) - 같은 부모를 가진 노드 (F의 형제 노드 G, H)
• 깊이(Depth, Height) - 트리의 최대 레벨(위 트리의 깊이는 4)
• 차수(Degree) - 특정 노드에 연결된 자식 노드의 수(D의 차수는 3)
• 단말 노드(Terminal Node, Leaf Node) - 트리의 제일 마지막에 위치한 노드(F, G, H, E, C)
• 트리의 차수 - 트리의 노드 중 가장 큰 차수 (3)

3. 트리의 운행법(Traversal)

• 컴퓨터 기억 공간에 표현된 트리의 각 노드를 중복되지 않게 정해진 순서대로 전부 검색하여 트리의 정보에 관한 사항을 알고자 함
• 이진트리의 운행법은 산술식의 표기법과 관련됨

4. 운행법 종류

- Preorder(root-Left-Right) : A, B, D, E, G, H, C, F

- Inorder(Left-root-Right) : D, B, G, E, H, A, C, F

- Postorder(Left-Right-root) : D, G, H, E, B, F, C, A

5. 수식의 표기법 

X = A + ( B + C ) * D

- Prefix(root-Left-Right) : + A * + B C D // 연산자를 앞으로

- Infix(Left-root-Right) : A + B + C * D

- Postfix(Left-Right-root) : A B C + D * + // 연산자를 뒤로

 

- Infix 표기를 Prefix로 변환하기

X = A / B * (C + D) + E

(X = (((A / B) * (C + D))+E)) : 연산 우선순위에 따라 괄호로 묶는다.

=(X+(*(/(A B)+(C D))E)) : 연산자를 해당 괄호 앞으로 옮긴다.

=X+*/AB+CDE : 필요 없는 괄호를 제거한다

 

- Infix 표기를 Postfix로 변환하기

X = A / B * (C + D) + E

(X = (((A / B) * (C + D))+E)) : 연산 우선순위에 따라 괄호로 묶는다.

(X(((A B)/(C D)+)*E)+)= : 연산자를 해당 괄호의 뒤로 옮긴다.

XAB/CD+*E+= : 필요 없는 괄호를 제거한다.

 

- Postfix 표기를 Infix로 변환하기

A B C - / D E F + * +

((A (B C -) /) (D (E F +) *) +) : 먼저 인접한 피연산자 두 개와 오른쪽 연산자를 괄호로 묶는다.

((A / (B - C)) + (D * (E + F))) : 연산자를 해당 피연산자의 가운데로 이동시킨다

A / (B - C) + D * (E + F) : 필요 없는 괄호를 제거한다.

 

- Prefix 표기를 Infix로 변환하기

+ / A - B C * D + E F

(+ (/ A (- B C)) (* D (+ E F))) : 먼저 인접한 피연산자 두 개와 왼쪽 연산자를 괄호로 묶는다.

((A / (B - C)) + (D * (E + F))) : 연산자를 해당 피연산자의 가운데로 이동시킨다

A / (B - C) + D * (E + F) : 필요 없는 괄호를 제거한다.

6. 트리의 종류 - 이진트리

• 정의 - Degree가 2 이하로 구성된 트리
• 길이가 K인 이진트리의 최대 노드의 수 : 2^k - 1
• 이진트리의 레벨 i에서 최대 노드의 수 : 2^(i-1)
• 정이진 트리(FBT, Full Binary Tree)

정이진 트리

• 전이진 트리(CBT, Complete Binary Tree)

전이진 트리

• 사향 이진트리(SBT, Skewed Binary Tree) : 이진트리가 한쪽 방향

사향 이진 트리

• 스레드(thread) 이진트리 : 비순환적인 이진트리 운행 알고리즘에서 스택을 사용하지 않고 낭비되는 널 연결 필드를 활용하여 트리 운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 이진트리
• AVL 트리 : 각 노드의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리, 탐색 시간이 빠름
• 균형 트리 : 트리의 단말 노드의 레벨이 모두 같게 만든 트리, 실제 레코드까지의 탐색 길이가 동일하게 색인부를 완전 균형 트리로 구성
• B- 트리 : 한 노드 안에 있는 키 값은 오름차순을 유지함, 인덱스 파일에서 인덱스를 구성하는 방법 중의 하나임
• B+ 트리 : B- 트리의 추가, 삭제 시 발생하는 노드의 분열과 합병 연산 과정을 줄일 수 있는 트리구조, 단말 노드가 아닌 인덱스 세트와 단말 로드로 구성된 데이터 세트로 이루어짐
• m-원 트리 : 키값의 일부분이 동일한 문자열이나 숫자로 구성된 자료를 표현하는데 효율적, 한 노드가 최대 (m-1) 개의 키와 m개의 subtree를 갖도록 구성됨
• 신장 트리 : 그래프에서 간선들이 사이클이 되지 않도록 만든 트리

신장 트리