공백 상태인 이진 탐색 트리(binary search tree)에 1부… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
공백 상태인 이진 탐색 트리(binary search tree)에 1부터 5까지의 정수를 삽입하고자 한다. 삽입 결과, 이진 탐색 트리의 높이가 가장 낮은 삽입 순서는?
1
1, 2, 3, 4, 5
2
1, 3, 2, 4, 5
3
3, 1, 2, 4, 5
4
4, 3, 5, 2, 1
해설

3, 1, 2, 4, 5 순서로 삽입할 때 트리 높이가 가장 낮다(3레벨).

이진 탐색 트리의 높이는 삽입 순서에 따라 달라지며, 루트가 중앙값에 가까울수록 좌우가 고르게 나뉜다. 3을 루트로 하면 왼쪽에 1-2, 오른쪽에 4-5가 각각 두 레벨로 달려 전체 3레벨이 된다.

  • 1, 2, 3, 4, 5는 계속 오른쪽 자식으로만 이어져 5레벨의 편향 트리가 된다.
  • 1, 3, 2, 4, 5는 1 → 3 → 4 → 5 경로가 생겨 4레벨이 된다.
  • 4, 3, 5, 2, 1은 4 → 3 → 2 → 1 경로가 왼쪽으로 이어져 4레벨이 된다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 16년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기