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