9급국가직공무원 2011-04-09 컴퓨터일반 7번 문제 해설

요약: 최악의 경우 탐색 성능이 가장 우수한 자료 구조를 묻는 문제입니다.

정답 근거:
- 4. AVL 트리: 균형 잡힌 이진 탐색 트리로, 최악의 경우에도 탐색 시간 복잡도가 O(log n)입니다.

오답 포인트:
- 1. 정렬되지 않은 배열: 최악의 경우 O(n)의 선형 탐색 필요.
- 2. 체인법 해시 테이블: 충돌 시 최악의 경우 O(n) 성능 가능.
- 3. 이진 탐색 트리 (일반): 불균형 시 최악의 경우 O(n) 성능 가능.

핵심 개념:
- 균형 트리 (AVL 트리): 자동 균형 조정으로 최악의 탐색 효율 유지 (O(log n)).

마무리 요약: AVL 트리는 균형 유지로 인해 최악의 탐색 상황에서도 가장 빠른 성능을 보장합니다.