이진탐색트리
이진탐색트리 (BST)
이진탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 따르는 자료구조입니다.
시간 복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
| 탐색 | $O(\log n)$ | $O(n)$ |
| 삽입 | $O(\log n)$ | $O(n)$ |
| 삭제 | $O(\log n)$ | $O(n)$ |
최악의 경우는 트리가 한쪽으로 치우칠 때 발생합니다. (편향 이진 트리)
균형 트리
AVL 트리, Red-Black 트리는 회전(rotation) 연산을 통해 자동으로 균형을 유지하여 항상 $O(\log n)$을 보장합니다. 회전은 부모-자식 관계를 재배치해 트리의 높이를 낮추는 핵심 연산입니다.
순회
- 중위 순회 (Inorder): 정렬된 순서로 출력
- 전위 순회 (Preorder): 트리 복사
- 후위 순회 (Postorder): 트리 삭제