<보기>와 같이 입력키와 각각의 검색확률이 주어질 때, 최적… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
<보기>와 같이 입력키와 각각의 검색확률이 주어질 때, 최적의 이진 검색 트리(optimal binary search tree)로 가장 옳은 것은? (단, 최상단 노드가 루트 노드이다.)<보기>
입력키 A B C D 검색확률 0.3 0.4 0.1 0.2
1
2
3
4
해설
최적 이진 검색 트리는 루트 B, 왼쪽 자식 A, 오른쪽 자식 D, D의 왼쪽 자식 C인 트리이다.
평균 비교 횟수는 각 키의 (깊이×검색확률) 합이며, 이 트리는 로 가능한 트리 중 최소이다. 확률이 큰 B·A를 위에, 가장 작은 C를 가장 아래에 둔 결과이다.
- 루트 C, B·D가 자식이고 A가 B 아래인 트리:
- 루트 B, A·C가 자식이고 D가 C 아래인 트리: 로, 확률이 더 큰 D가 더 깊어 손해이다.
- 루트 C, A·D가 자식이고 B가 A 아래인 트리: 으로 확률이 가장 큰 B가 가장 깊다.
오류나 개정된 내용이 보이면 알려주세요



