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

n개의 식별자 (a₁, a₂, …, a_n)로 구성된 이진탐색트리에 n ＋ 1개의 외부 노드를 추가하여 확장 이진트리를 만들 수 있다. 각 a_i의 탐색 확률이 p_i이고, 각 외부 노드에 속하는 식별자, 즉 내부 노드에 있지 않은 식별자의 탐색 확률이 q_i일 때 주어진 이진탐색트리 T의 전체비용은 다음 식과 같다.

$\begin{array}{rl}\mathrm{cost}(T)=& \sum _{1\le i\le n}{p}_i\mathrm{level}(a_i)\\ & +\sum _{0\le i\le n}{q}_i(\mathrm{level}(\text{external node }i)-1)\end{array}$

전체 비용이 최소인 이진탐색트리를 최적 이진탐색트리라 한다. 3개의 식별자가 (a₁, a₂, a₃) ＝ (do, if, while)이고, (p₁, p₂, p₃) ＝ (0.1, 0.2, 0.5), (q₀, q₁, q₂, q₃) ＝ (0.05, 0.05, 0.05, 0.05)일 때, 최적 이진탐색트리는?