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

**요약:** 최악의 경우 탐색 성능이 가장 우수한 자료 구조를 묻는 문제입니다. **정답 근거:** - **4. AVL 트리:** 균형 잡힌 이진 탐색 트리로, 최악의 경우에도 탐색 시간 복잡도가 O(log n)입니다. **오답 포인트:** - **1. 정렬되지 않은 배열:** 최악의 경우 O(n)의 선형 탐색 필요. - **2. 체인법 해시 테이블:** 충돌 시 최악의 경우 O(n) 성능 가능. - **3. 이진 탐색 트리 (일반):** 불균형 시 최악의 경우 O(n) 성능 가능. **핵심 개념:** - **균형 트리 (AVL 트리):** 자동 균형 조정으로 최악의 탐색 효율 유지 (O(log n)). **마무리 요약:** AVL 트리는 균형 유지로 인해 최악의 탐색 상황에서도 가장 빠른 성능을 보장합니다.