6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리(bina… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 09년 1회차
6개의 데이터를 비어있는 트리에 차례로 삽입하여 이진 탐색트리(binary search tree)를 만들 때, 만들어진 이진 탐색트리의 높이가 가장 낮은 것은?
1
1, 2, 3, 5, 4, 6
2
4, 2, 5, 6, 1, 3
3
3, 1, 4, 2, 6, 5
4
2, 1, 3, 4, 6, 5
해설

높이가 가장 낮은 것은 4, 2, 5, 6, 1, 3 순서의 삽입이다.

루트 4의 왼쪽에 2, 오른쪽에 5가 오고, 1과 3은 2의 양쪽 자식, 6은 5의 오른쪽 자식이 되어 높이 3(레벨 수 기준)이다. 이는 노드 6개인 이진트리가 가질 수 있는 최소 높이이다.

  • 1, 2, 3, 5, 4, 6: 1→2→3→5로 오른쪽으로만 이어지고 4가 5의 왼쪽에 붙어 높이 5이다.
  • 3, 1, 4, 2, 6, 5: 3→4→6→5 경로가 생겨 높이 4이다.
  • 2, 1, 3, 4, 6, 5: 2→3→4→6→5 경로가 생겨 높이 5이다.

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

이어서 풀어보기

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