**탐색(Searching)**은 데이터 구조에 저장된 수많은 값 중에서 원하는 키(Key)를 가진 항목을 찾아내는 프로세스입니다.
1. 탐색 알고리즘 비교
| 알고리즘 | 전제 조건 | 시간 복잡도 (최악) | 특징 |
|---|---|---|---|
| 순차 탐색 (Sequential) | 없음 (정렬 불필요) | $O(N)$ | 첫 번째 원소부터 하나씩 순차적으로 비교 |
| 이진 탐색 (Binary Search) | 데이터 정렬 필수 | $O(log N)$ | 중앙값 비교 후 탐색 범위를 1/2씩 줄여나감 |
| 이진 탐색 트리 (BST) | BST 구조 조건 만족 | $O(N)$ (편향 트리) $O(log N)$ (평균) |
동적 데이터의 빠른 탐색, 삽입, 삭제 지원 |
2. 이진 탐색(Binary Search) 원리와 구현
정렬된 배열에서 중앙값(Mid)과 목표값(Target)을 비교하여 탐색 범위를 반으로 축소합니다.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 실행
data = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(data, 7)) # 인덱스 3 반환
3. 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 다음 조건을 만족해야 합니다:
- 모든 노드의 키는 유일함.
- 왼쪽 서브트리 키 < 부모 노드 키 < 오른쪽 서브트리 키
- 삭제 연산 3가지 케이스:
- 단말 노드 삭제: 노드 제거.
- 자식이 1개인 노드 삭제: 자식을 부모 노드에 연결.
- 자식이 2개인 노드 삭제: 오른쪽 서브트리의 최솟값(후계 노드)을 복사해오고 해당 후계 노드를 삭제.
4. 자주 묻는 질문 (Q&A)
Q. BST의 편향(Skewed) 문제를 해결하는 방법은 무엇인가요? A. 사전에 오름차순으로 정렬된 데이터가 들어오면 BST가 사슬 형태의 $O(N)$ 편향 트리가 될 수 있습니다. 이를 막기 위해 스스로 높이 균형을 맞추는 AVL 트리나 **레드-블랙 트리(Red-Black Tree)**를 사용합니다.