호프만 트리 만들기와 마찬가지로 최적의 이진 검색 트리 만들기?

Question

여기에서 곧 마지막으로 공부하고, 아래 질문에서 최적의 이진 검색 트리를 만드는 것이 기호와 주파수가 주어진 허프만 트리를 만드는 것과 같은지 궁금합니다.

계산 키 K1 확률 대 < K2 < K3 < K4와 최적 이진 탐색 트리 : 그래서 여기

p1 = .1 p2 = .2 p3 = .3 p4 = .1 
q0 = .15 q1 = .05 q2 = 0 q3 = .1 

우리는 낮은 두 확률 쌍 확률 = N1 +의 N2의 내부 노드를 만들 것 그 다음으로 가장 낮은 두 개의 확률을 짝 지어주는 식으로 진행 되는가?

Answer 1

실제로 두 가지 문제가 있습니다. 허프 먼 트리 생성은 키 순서를 유지할 필요가 없지만 BST 생성은 유지합니다. 게다가 허프만 트리를 생성하려면 다른 노드를 "조인"하기 위해 여분의 노드가 필요합니다. BST에서는 그렇지 않습니다 (기존 노드가있는 노드에 참여).

"최적의"BST 생성을 위해 모든 노드 깊이의 가중치 합을 최소화해야합니다 (가중치는 노드의 빈도 임). 이 경우 p3은 p2와 p4의 부모이어야하고 p2는 p1의 부모이어야합니다. 그것은 당신이 q3에 q0으로 무엇을 의미하는지 불분명하지만, 사람들은라면도 원하는 BST에 노드

Node Probability Depth Product Parent 
K1 .1   2  .2  K2 
K2 .2   1  .2  K3 
K3 .3   0  0  None (root) 
K4 .1   1  .1  K3 
         .5 (total, smaller than all other configurations) 

, 당신은 여전히 ​​깊이의 가중 합을 최적화하려고 할 것이다 : 이것은의 "가중 합계"를 생성합니다.