1. 이진 탐색 트리(BST)의 정의 및 조건
- 개념: 데이터 저장과 동시에 정렬을 유지하는 이진 트리 기반의 자료구조.
- 핵심 조건:
- 왼쪽 서브트리: 부모 노드의 값보다 작은 노드들로만 구성.
- 오른쪽 서브트리: 부모 노드의 값보다 큰 노드들로만 구성.
- 재귀성: 모든 서브트리 역시 위의 조건을 만족해야 함.
2. 주요 연산 및 시간 복잡도
트리의 균형이 잘 잡혀 있는 경우, 트리의 높이는 log n이 되며 효율적인 탐색이 가능.
| 연산 (Operation) | 평균 시간 복잡도 | 최악의 경우 (Worst Case) |
|---|---|---|
| 검색 (Search) | O(log n) | O(n) |
| 저장 (Insert) | O(log n) | O(n) |
| 삭제 (Delete) | O(log n) | O(n) |
3. 이진 트리(Binary Tree)와의 차이점 및 최악의 경우
- 이진 트리 정의: 모든 노드의 자식 노드 개수가 2개 이하인 트리 구조.
- 최악의 경우 (Skewed Tree):
- 균형이 깨져서 데이터가 한쪽으로만 치우친 경우 발생.
- 논리적으로 연결 리스트(Linked List)와 동일한 구조가 되어 탐색 성능이 O(n)으로 저하.
4. 자가 균형 이진 탐색 트리 (Self-Balancing BST)
최악의 경우를 방지하기 위해 트리의 균형을 유지하며 높이를 가능한 낮게 유지하는 알고리즘.
- 대표 사례: AVL 트리, Red-Black 트리.
- 실무 활용: Java의 HashMap은 데이터 저장 시 효율성을 위해 연결 리스트와 Red-Black 트리를 병행하여 사용.
핵심 정리
- 정의: 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 정렬된 이진 트리임.
- 성능: 평균 연산 속도는 O(log n)이나, 트리 불균형 시 O(n)까지 성능 저하 가능함.
- 해결책: 성능 저하 방지를 위해 AVL 트리나 Red-Black 트리 같은 자가 균형 BST를 활용함.
추가 정리
Q. BST를 효과적으로 설명하려면?
- 단순한 정의보다 데이터가 저장될 때 어떤 규칙에 따라 노드가 배치되는지를 그림으로 설명하는 것이 좋음.
- 특히 정렬된 데이터가 순차적으로 들어올 때 발생하는 ‘치우친 트리(Worst Case)’ 상황과 이를 방지하는 자가 균형 트리의 필요성을 연관 짓는 것이 핵심.
Q. BST의 높이가 왜 O(log n)인가?
- 균형 잡힌 이진 트리에서 각 층을 내려갈 때마다 탐색 범위가 절반씩 줄어들기 때문.