1. 이진 트리의 종류 : (기본 구조에 따라)
ㅇ 전 이진 트리 (Full Binary Tree)
- 모든 노드의 차수/자식이 0 또는 2 이어야 함
. 자식이 없으면 리프 노드(단말 노드)
. 자식이 있으면 반드시 2개 모두 있어야 함
* 쉽게, 외동 자식이 없는 이진 트리
. 자식이 하나만 있는 노드가 존재 안함
ㅇ 포화 이진 트리 (Perfect Binary Tree)
- 모든 레벨이 빈틈없이 꽉 찬 이진 트리
. 모든 내부 노드가 자식 2개를 가지며,
. 모든 리프 노드가 동일한 레벨(깊이)에 위치한 트리
* 레벨 수 i일 때, 2i-1개 노드를 갖음 ☞ 트리 용어 참조
* 포화 이진 트리는, 전 이진 트리이면서 동시에 완전 이진 트리이기도 함
ㅇ 완전 이진 트리 (Complete Binary Tree)
- 포화 이진 트리의 맨아래 리프 노드(단말 노드)들을, 오른쪽부터 하나씩 제거하면, 얻어지는 트리
. 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며,
. 마지막 레벨은 왼쪽부터 연속적으로 채워지는 트리
. 중간에 빈 자리가 있으면 안됨
- 즉, 마지막 레벨의 노드를, 왼쪽부터 오른쪽으로 빈틈없이 채움
* 레벨 수 h일 때, h-1 레벨까지, 2h-1-1개 노드를 갖음
* 쉽게, 왼쪽부터 빈틈없이 채워지는 이진 트리
. 여기서, 완전(complete)은,
. 부모가 자식을 왼쪽부터 채운다는 말임 ☞ 순서 트리 참조
2. 이진 트리의 종류 : (편향성에 따라)
ㅇ 편향 이진 트리 (Skewed Binary Tree)
- 이진 트리에서, 각 내부 노드가 한쪽 자식만 갖는 형태로 한쪽으로 치우친 트리
- 왼쪽 편향 이진 트리 (Left-Skewed Binary Tree)
. 각 내부 노드가 왼쪽 자식만 갖는 형태
- 오른쪽 편향 이진 트리 (Right-Skewed Binary Tree)
. 각 내부 노드가 오른쪽 자식만 갖는 형태
* 만일, 극단적으로 편향되면,
. 트리가 연결 리스트(Linked List)와 유사한 형태가 됨
3. 이진 트리의 자료구조
ㅇ (검색 및 순서 관리)
- 이진 검색 트리 (Binary Search Tree, BST)
. 왼쪽 서브트리 < 루트 < 오른쪽 서브트리의 순서 관계를 이용하는 검색 트리
. 이진 트리 구조를 갖으나, 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조
. 각 노드는 2개의 자식 노드를 각각 가리키는 2개의 포인터를 갖음
ㅇ (우선순위 관리)
- 이진 힙 (Binary Heap)
. 완전 이진 트리를 기반으로, 부모와 자식 간의 대소 관계를 유지하는 자료구조
.. 부모와 자식 간에는 대소 관계가 유지됨
.. 형제 노드 간에는 대소 관계가 정해지지 않음
. 최대 힙 (Max Heap)
.. 부모 ≥ 자식
. 최소 힙(Min Heap)
.. 부모 ≤ 자식
. 따라서, 부분 순서 트리(Partially Ordered Tree) 라고도 함
4. 이진 트리의 균형화
ㅇ 균형 트리 (Balanced Tree)
- 좌우 서브 트리의 높이 차이가 크지 않도록 유지되는 트리
. 특정 한쪽으로 치우치지 않게 함
- 탐색 성능 저하를 방지하기 위해 사용됨
* 쉽게, 좌우 균형을 맞춘 트리
* 例) AVL Tree, Red-Black Tree 등
ㅇ AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)
- 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되게하는 이진 탐색 트리
- 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리
ㅇ 레드-블랙 트리 (Red-Black Tree)
- 색상 규칙을 이용하여 균형을 유지하는 이진 검색 트리
5. 이진 트리의 확장
ㅇ 다진 트리 (Multiway Tree)
- 하나의 노드가 3개 이상의 자식을 가질 수 있는 트리
ㅇ 다진 검색 트리 (Multiway Search Tree)
- 다수의 자식 및 키를 이용하여 검색하는 트리
- 이진 검색 트리 : 최대 2개의 자식 노드를 가질 수 있음
- 다진 검색 트리 : 최대 3 이상의 자식 노드를 갖는 검색 트리 (k진 검색 트리)
ㅇ B 트리 (B-Tree, Balanced Tree)
- 하나의 노드가 여러 개의 자식과 키를 가질 수 있는, 균형 잡힌 다진 검색 트리
- 대용량 데이터의 검색에 적합하도록 설계된 자료구조
. 데이터베이스 및 파일시스템 등에 널리 사용됨
ㅇ B+ 트리 (B+ Tree)
- B 트리의 수정 버전
. 트리 구조의 리프 노드(leaf node)에 만 키 값을 저장시킴
. 여기서 리프 노드는, 실제 저장된 레코드의 주소 값을 갖음