n개의 식별자 (a1, a2, …, an)로 구성된 이진탐색트리에 n … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
n개의 식별자 (a1, a2, …, an)로 구성된 이진탐색트리에 n + 1개의 외부 노드를 추가하여 확장 이진트리를 만들 수 있다. 각 ai의 탐색 확률이 pi이고, 각 외부 노드에 속하는 식별자, 즉 내부 노드에 있지 않은 식별자의 탐색 확률이 qi일 때 주어진 이진탐색트리 T의 전체비용은 다음 식과 같다.전체 비용이 최소인 이진탐색트리를 최적 이진탐색트리라 한다. 3개의 식별자가 (a1, a2, a3) = (do, if, while)이고, (p1, p2, p3) = (0.1, 0.2, 0.5), (q0, q1, q2, q3) = (0.05, 0.05, 0.05, 0.05)일 때, 최적 이진탐색트리는?
1
2
3
4
해설
최적 이진탐색트리는 while을 루트로 하고 왼쪽 자식 if, 그 왼쪽 자식 do로 이어지는 트리이며 비용은 1.65이다.
탐색 확률이 가장 큰 while(0.5)을 루트에 두어야 가중 레벨 합이 작아진다. 내부 노드 비용은 이다.
외부 노드의 (레벨-1) 합은 3+3+2+1=9이므로 , 전체 비용은 이다.
- do를 루트로 하고 오른쪽으로 if, while이 이어지는 트리: 로 더 크다.
- if를 루트로 하고 do와 while을 양쪽 자식으로 둔 균형 트리: 으로 더 크다.
- do를 루트로 하고 오른쪽 자식 while, 그 왼쪽 자식 if를 둔 트리: 로 더 크다.
오류나 개정된 내용이 보이면 알려주세요



