سوال ۷۷ کنکور ارشد علوم کامپیوتر ۱۴۰۴

فرض کنید نتیجه یک ماتریس ریشه $R$ از درخت جستجوی دودویی بهینه به‌صورت جدول زیر حاصل شده است و $I_۱ < I_۲ < I_۳ < I_۴$ کلیدها و $p_۱ = p_۳ = \frac{۳}{۸}$ و $p_۲ = p_۴ = \frac{۱}{۸}$ احتمال جستجوی این درخت دودویی هستند. کدام گزینه شکل نهایی درخت مزبور است؟ ($R$ مشخص‌کننده فرزندان دورشده است.)

$R=\begin{array}{c|cccc} & ۱ & ۲ & ۳ & ۴ \\\hline ۱ & ۱ & ۱ & ۲ & ۲ \\ ۲ & & ۰ & ۲ & ۲ \\ ۳ & & & ۰ & ۳ \\ ۴ & & & & ۰ \\ ۵ & & & & ۰ \end{array}$