탐색할 키 k_i와 탐색할 확률 p_i가 (가)와 같이 주어질 때 이진… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
탐색할 키 와 탐색할 확률 가 (가)와 같이 주어질 때 이진 탐색 트리(binary search tree)를 (나)와 같이 구현하였다. 이진 탐색 트리의 총비용을 이라고 할 때, 이진 탐색 트리 (나)의 총비용은? (단, 실패한 비용은 없다고 가정하며, 루트(root) 노드의 단계(level)는 1이다)
(가)
| 1 | 2 | 3 | 4 | 5 | |
| 0.2 | 0.45 | 0.05 | 0.1 | 0.2 |

1
1.65
2
1.75
3
1.85
4
1.95
해설
이진 탐색 트리 (나)의 총비용은 1.75이다.
(나)에서 루트는 (단계 1), 그 자식은 (단계 2), 의 왼쪽 자식 는 단계 3, 의 왼쪽 자식 은 단계 4이다.
- 1.65는 각 키의 단계를 하나라도 낮게 잡았을 때 나오는 값이다.
- 1.85나 1.95는 깊은 노드의 단계를 실제보다 높게 계산한 값이다.
오류나 개정된 내용이 보이면 알려주세요