Design-and-analysis-of-algorithms-optimal-cost-binary-search-trees

DAA-最適コストバイナリ検索ツリー

バイナリ検索ツリー（BST）は、キー値が内部ノードに保存されるツリーです。 外部ノードはヌルノードです。 キーは辞書順、つまり 内部ノードごとに、左側のサブツリーのすべてのキーはノードのキーよりも小さく、右側のサブツリーのすべてのキーは大きくなります。

各キーを検索する頻度がわかっている場合、ツリー内の各ノードにアクセスするための予想コストを計算するのは非常に簡単です。 最適なバイナリ検索ツリーはBSTであり、各ノードを見つけるための予想コストは最小限です。

BSTの要素の検索時間は O（n） ですが、Balanced-BSTの検索時間は O（log n） です。 この場合も、最適コストバイナリ検索ツリーで検索時間を改善することができ、最も頻繁に使用されるデータをルートおよびルート要素により近く配置し、最も頻繁に使用されないデータをリーフおよびリーフに配置します。

ここでは、最適なバイナリ検索ツリーアルゴリズムを示します。 まず、提供された n 個の異なるキーのセットからBSTを構築します _ <k〜1〜、k〜2〜、k〜3〜、…​ k〜n〜> ' 。 ここで、キー _K〜i〜' にアクセスする確率は p〜i〜 です。 いくつかのダミーキー（* d〜0〜、d〜1〜、d〜2〜、…​ キーセット _K に存在しない値に対していくつかの検索が実行される可能性があるため、d〜n〜_ ）が追加されます。 各ダミーキー *d〜i〜 に対するアクセスの確率は q〜i〜 です。

Optimal-Binary-Search-Tree(p, q, n)
e[1…n + 1, 0…n],
w[1…n + 1, 0…n],
root[1…n + 1, 0…n]
for i = 1 to n + 1 do
   e[i, i - 1] := qi - 1
   w[i, i - 1] := qi - 1
for l = 1 to n do
   for i = 1 to n – l + 1 do
      j = i + l – 1 e[i, j] := ∞
      w[i, i] := w[i, i -1] + pj + qj
      for r = i to j do
         t := e[i, r - 1] + e[r + 1, j] + w[i, j]
         if t < e[i, j]
            e[i, j] := t
            root[i, j] := r
return e and root

分析

3つのネストされた for ループが使用されるため、アルゴリズムには* O（n ^ 3 ^）時間が必要です。 これらの各ループは、最大で *n の値を取ります。

例

次のツリーを考慮すると、コストは2.80ですが、これは最適な結果ではありません。

ツリー

Node	Depth	Probability	Contribution
k1	1	0.15	0.30
k2	0	0.10	0.10
k3	2	0.05	0.15
k4	1	0.10	0.20
k5	2	0.20	0.60
d0	2	0.05	0.15
d1	2	0.10	0.30
d2	3	0.05	0.20
d3	3	0.05	0.20
d4	3	0.05	0.20
d5	3	0.10	0.40
Total			2.80

この章で説明するアルゴリズムを使用して最適なソリューションを得るために、次の表が生成されます。

次の表では、列インデックスは i 、行インデックスは j です。

e	1	2	3	4	5	6
5	2.75	2.00	1.30	0.90	0.50	0.10
4	1.75	1.20	0.60	0.30	0.05
3	1.25	0.70	0.25	0.05
2	0.90	0.40	0.05
1	0.45	0.10
0	0.05

w	1	2	3	4	5	6
5	1.00	0.80	0.60	0.50	0.35	0.10
4	0.70	0.50	0.30	0.20	0.05
3	0.55	0.35	0.15	0.05
2	0.45	0.25	0.05
1	0.30	0.10
0	0.05

root	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

これらのテーブルから、最適なツリーを形成できます。