공백 상태인 이진 탐색 트리(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레벨이 된다.
오류나 개정된 내용이 보이면 알려주세요