2

ここでもうすぐ最終試験に向けて勉強しますが、以下の質問で尋ねられるように最適な二分探索木を作成することは、記号と頻度が与えられたハフマン木を作成することと同じかどうか疑問に思っていました.

キー K1 < K2 < K3 < K4 の確率で最適な二分探索木を計算します。

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

ここでは、最も低い 2 つの確率をペアにして、確率 = n1 + n2 の内部ノードを作成し、次に低い 2 つの確率をペアにする、というようにしますか?

4

1 に答える 1

4

それらは実際には2つの異なる問題です。ハフマン ツリーの生成では、キーの順序を保持する必要はありませんが、BST の生成では保持する必要があります。さらに、ハフマン ツリーの生成には、他のノードを「結合」するための追加のノードが必要ですが、これは BST の場合とは異なります (ノードを既存のノードと結合します)。

「最適な」BST 生成では、すべてのノードの深さの加重合計を最小化する必要があります (加重はノードの頻度です)。この場合、p3 は p2 と p4 の親であり、p2 は p1 の親である必要があります。これにより、次の「加重合計」が生成されます。

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)

q0toで何を意味するのかは不明ですq3が、それらが目的の BST のノードでもあった場合でも、深さの加重合計を最適化しようとします。

于 2012-11-27T22:29:56.140 に答える