비어있는 이진 탐색 트리(binary search tree)에 다음 키… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
비어있는 이진 탐색 트리(binary search tree)에 다음 키 값들을 차례로 삽입하여 동적으로 이진 탐색 트리를 구성하였을 때, 5를 탐색하는데 필요한 비교 횟수는?
23, 18, 2, 16, 4, 10, 5, 39, 26, 15
1
3
2
5
3
7
4
9
해설

5를 찾으려면 23 → 18 → 2 → 16 → 4 → 10 → 5 순으로 7회 비교가 필요하다.

삽입 결과 23의 왼쪽 18, 18의 왼쪽 2, 2의 오른쪽 16, 16의 왼쪽 4, 4의 오른쪽 10, 10의 왼쪽 5가 연결되어 한쪽으로 길게 늘어진 편향된 경로가 생긴다.

  • 비교 3회는 2까지만 내려간 경우이다.
  • 비교 5회는 4까지만 내려간 경우이다.
  • 비교 9회는 루트에서 5까지의 경로 길이보다 많아 성립하지 않는다.

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

이어서 풀어보기

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