← 회차 전체 문제편집복원내용 검수 완료2025년 정보처리기사 3회 필기 · 소프트웨어 개발 · 36번
키가 정렬된 순서로 계속 삽입될 때 회전이나 분할로 균형을 복원하지 않아 높이가 n까지 증가할 수 있는 탐색 트리는?
- 1
일반 이진 탐색 트리
정답 근거일반 이진 탐색 트리는 입력 순서에 따라 편향되어 최악 높이가 노드 수와 같아질 수 있다. - 2
AVL 트리
오답 이유AVL 트리는 서브트리 높이 차를 제한하고 회전해 검색 높이를 로그 수준으로 유지한다. - 3
2-3 트리
오답 이유2-3 트리는 노드 분할과 병합으로 모든 리프의 깊이를 같게 유지한다. - 4
레드-블랙 트리
오답 이유레드-블랙 트리는 색 규칙을 이용해 가장 긴 경로가 과도하게 늘어나는 것을 제한한다.
정답·상세해설정답 1번
일반 이진 탐색 트리는 균형 규칙이 없어 정렬 순서 삽입 시 한쪽으로만 연결될 수 있다. 이때 높이와 최악 검색 시간이 O(n)이 된다. 나머지는 균형 규칙으로 높이를 O(log n) 범위에 둔다.
콘텐츠 기록콘텐츠 정보
- 자료 유형
- 편집복원
- 검수 상태
- 내용 검수 완료
- 최종 검수
- 2026-08-21