트리와 그래프에 대해 작성하던 중 트리의 종류(이진 트리, 이진 탐색 트리)에 대한 하위 카테고리가 다양한 것을 확인해 각 종류에 대한 글을 따로 작성하기로 했다.
이진 트리 (Binary Tree, B-Tree)
: 자식 노드를 최대 2개 가질 수 있는 트리
- 종류
전 이진 트리, 완전 이진 트리, 포화 이진 트리, 균형 이진 트리, 편향 이진 트리
※ 하나의 이진 트리는 위 카테고리 여러 개에 동시에 해당할 수도 있음
- 전(or 정) 이진 트리 (Full/Strict Binary Tree)
모든 노드가 0개 또는 2개의 자식 노드를 가짐
- 완전 이진 트리 (Complete Binary Tree)
마지막 레벨 외 노드들은 모두 채워져 있어야 함 (2개의 자식 노드)
말단 노드들은 왼쪽에서부터 차례대로 채워짐
배열로 구현하는 것이 편리함
ex) 힙(Heap)
- 포화 이진 트리 (Perfect Binary Tree)
모든 레벨의 노드가 2개의 자식 노드 가짐 (전 이진 트리 조건 만족)
모든 말단 노드들은 동일한 레벨에 속함
- 균형 이진 트리 (Balanced Binary Tree)
왼쪽, 오른쪽 서브 트리 레벨이 1 이상 차이 나지 않음
ex) AVL 트리, Red-black 트리
- 변질 이진 트리 (Degenerate Binary Tree)
각 노드들은 하나의 자식 노드만 가짐
(⊃ 편향 이진 트리(Skewed Binary Tree ) : 왼쪽 또는 오른쪽 한 방향으로만 자식을 가짐)
LinkedList와 유사한 구조
참고
'Programming > 알고리즘' 카테고리의 다른 글
| [백준/자바] 트리 1967번 - 트리의 지름 (0) | 2023.06.03 |
|---|---|
| [자료구조] 이진 탐색 트리 (0) | 2023.06.02 |
| [자료구조] 트리, 그래프 (0) | 2023.05.11 |
| DFS, BFS (0) | 2023.05.04 |
| DP(Dynamic Programming, 동적 계획법) (0) | 2023.04.07 |
