[7급 국가직 자료구조론 2018년 9번]

키(key) 집합에 속하는 각 키에 대해 탐색이 일어날 확률이 알려져 있을 때, 최적 이진 탐색 트리(optimal binary search tree)를 구성함으로써 한 번의 탐색에 대한 평균 비교 횟수를 최소화할 수 있다. p(x)를 키 x에 대한 탐색 확률이라고 할 때, 키 집합 {1, 2, 3}에 속하는 각 키에 대한 탐색 확률은 다음과 같다. 키 값이 각각 1, 2, 3인 3개의 데이터를 사용하여 구성한 최적 이진 탐색 트리에서 탐색 1회당 평균 비교 횟수는? (단, p(1) + p(2) + p(3) = 1이므로, 1, 2, 3 외의 키를 탐색하는 경우는 없다)

p(1) = 0.6, p(2) = 0.3, p(3) = 0.1