← 회차 전체 문제편집복원내용 검수 완료2024년 정보처리기사 1회 필기 · 소프트웨어 개발 · 31번
서로 다른 키 1, 2, 3, 4, 5를 이 순서대로 빈 트리에 삽입한다. 별도의 균형 조정이 없을 때 최악의 검색이 선형 시간까지 늘어날 수 있는 구조는?
- 1
일반 이진 탐색 트리
정답 근거일반 이진 탐색 트리는 삽입 순서에 따라 연결 리스트처럼 편향되어 최악 검색이 O(n)이 된다. - 2
AVL 트리
오답 이유AVL 트리는 회전으로 각 노드의 높이 차를 제한해 검색 높이를 O(log n)으로 유지한다. - 3
2-3 트리
오답 이유2-3 트리는 모든 리프의 깊이가 같도록 분할·병합하는 균형 다진 탐색 트리다. - 4
레드-블랙 트리
오답 이유레드-블랙 트리는 색 규칙과 회전으로 루트-리프 경로 길이를 제한해 O(log n) 검색을 보장한다.
정답·상세해설정답 1번
일반 이진 탐색 트리에 오름차순 키를 삽입하면 모든 노드가 한쪽 자식으로 이어져 높이가 n에 가까워질 수 있고 검색은 O(n)이 된다. 나머지 구조는 높이를 로그 수준으로 제한하므로 ①이 답이다.
콘텐츠 기록콘텐츠 정보
- 자료 유형
- 편집복원
- 검수 상태
- 내용 검수 완료
- 최종 검수
- 2026-08-21