안녕하세요! 최적 이진검색트리에서 궁금한점이 있어서 질문 남깁니다.
<img src="https://cdn.inflearn.com/public/files/posts/238a4ab0-5e05-4383-9205-98c23557536a/blob" alt="" />
위 식에서
<img src="https://cdn.inflearn.com/public/files/posts/acf2dea6-d1a2-4fc9-a3d3-50c35f07d529/blob" alt="" /> 이 부분이
<img src="https://cdn.inflearn.com/public/files/posts/ee5165db-ac8a-4cd2-8310-31c133485c66/blob" alt="" />
위에서&nbsp;<img src="https://cdn.inflearn.com/public/files/posts/695e43f8-35b2-4946-a829-08d0a751cb67/blob" alt="" />를 탐색하는 비용이라고 하셨는데,
제 생각에는&nbsp;<img src="https://cdn.inflearn.com/public/files/posts/695e43f8-35b2-4946-a829-08d0a751cb67/blob" alt="" />를 탐색하는 비용은 P_k가 되야 될거 같은데 왜&nbsp;<img src="https://cdn.inflearn.com/public/files/posts/acf2dea6-d1a2-4fc9-a3d3-50c35f07d529/blob" alt="" />가 되는지 궁금합니다.
<img src="https://cdn.inflearn.com/public/files/posts/ee5165db-ac8a-4cd2-8310-31c133485c66/blob" alt="" />여기에서 어떤 임의의 K_i를 탐색하게 되더라도 탐색 깊이가 1인 (비교횟수가 1인)&nbsp;<img src="https://cdn.inflearn.com/public/files/posts/695e43f8-35b2-4946-a829-08d0a751cb67/blob" alt="" />를 무조건 지나가게 되니 비교횟수 1 * (모든 K_i의 확률)이 되서 <img src="https://cdn.inflearn.com/public/files/posts/acf2dea6-d1a2-4fc9-a3d3-50c35f07d529/blob" alt="" />가 된것인가요??

꼼꼼하게 강의를 듣고 계시는 군요!
질문 속에 이미 답이 나와 있습니다.
어떤 K1... Kn의 키를 검색하려면 Kk는 반드시 지나가야 하므로,
sigma(Pk)가 Kk 노드에서의 Kk키에 대한 탐색 비용이 되는 것이지요.

인프런 커뮤니티 질문&답변

최적 이진검색트리 관계식