← 회차 전체 문제공개 기출자동 검사 완료2023년 지방직 기출 · 컴퓨터일반 · 자료구조·알고리즘 · 20번
공백 상태인 이진 탐색 트리(binary search tree)에 1부터 5까지의 정수를 삽입하고자 한다. 삽입 결과, 이진 탐색 트리의 높이가 가장 높은 삽입 순서는?
- 1
1, 2, 3, 4, 5
정답 근거1부터 5까지 오름차순으로 넣으면 모든 새 키가 오른쪽 자식이 되어 높이가 최대인 편향 트리가 되므로 정답이다. - 2
1, 4, 2, 5, 3
오답 이유1,4,2,5,3은 4의 왼쪽과 오른쪽에 노드가 분산되어 단일 사슬보다 높이가 낮다. - 3
3, 1, 4, 2, 5
오답 이유3을 루트로 두면 작은 키와 큰 키가 양쪽에 나뉘어 비교적 균형 잡힌다. - 4
5, 3, 4, 1, 2
오답 이유5,3,4,1,2도 3의 양쪽과 1의 오른쪽에 분기되어 다섯 노드가 한 경로에 놓이지 않는다.
정답·상세해설정답 1번
이진 탐색 트리에서 높이가 가장 높아지려면 트리가 한쪽으로 치우친 편향 트리(Skewed Tree)가 되어야 합니다. 정수가 오름 차순인 1, 2, 3, 4, 5 순서로 삽입되면 모든 노드가 오른쪽 자식으로만 연결되어 최대 높이인 5가 됩니다.
콘텐츠 기록콘텐츠 정보
- 자료 유형
- 공개 기출
- 검수 상태
- 자동 검사 완료
- 최종 검수
- 자동 검사 완료