最適な二分探索木

Knuth [ ^{2 ]}によって定義された静的最適性問題では、n個^の順序付き要素の集合と、${\displaystyle 2n+1}$確率。要素を次のように表します。${\displaystyle a_{1}}$を通して${\displaystyle a_{n}}$そして確率${\displaystyle A_{1}}$を通して${\displaystyle A_{n}}$そして${\displaystyle B_{0}}$を通して${\displaystyle B_{n}}$。${\displaystyle A_{i}}$要素の検索が行われる確率は${\displaystyle a_{i}}$（または検索成功）。^{[ 3 ]}${\displaystyle 1\leq i<n}$、${\displaystyle B_{i}}$要素の検索が行われる確率は${\displaystyle a_{i}}$そして${\displaystyle a_{i+1}}$（または検索失敗）、^{[ 3 ]}${\displaystyle B_{0}}$要素の検索が行われる確率は、${\displaystyle a_{1}}$、 そして${\displaystyle B_{n}}$要素の検索が行われる確率は、${\displaystyle a_{n}}$。 これら${\displaystyle 2n+1}$確率は考えられるすべての検索を網羅しているため、合計すると1になります。

静的最適性問題は、与えられた条件の下で期待探索時間を最小化する二分探索木を見つける最適化問題です。${\displaystyle 2n+1}$確率。n個の要素の集合上の可能な木の数は${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$[ ^{2 ]}これはnに対して指数関数的であるため^、総当たり探索は通常実行可能な解決策ではありません。

1971年、クヌースは、静的に最適な木をわずかO ( n² ⁾の時間で構築できる比較的単純な動的計画法アルゴリズムを発表した。 ^{[ 2 ]}この研究において、クヌースは1958年にエドガー・ギルバートとエドワード・F・ムーアによって導入された動的計画法アルゴリズムを拡張および改良した。^{[ 4 ]}ギルバートとムーアのアルゴリズムは、${\displaystyle O(n^{3})}$時間と${\displaystyle O(n^{2})}$空間があり、検索の失敗確率のみを考慮する最適な二分探索木の構築（最適なアルファベット木問題^{[ 5 ]}として知られる）の特定のケース用に設計されています。${\textstyle \sum _{i=1}^{n}A_{i}=0}$クヌースの研究は、次の洞察に基づいていた。静的最適性問題は最適部分構造を示す。つまり、ある木が与えられた確率分布に対して静的に最適であれば、その左部分木と右部分木も、それぞれの分布の適切な部分集合に対して静的に最適でなければならない（根の単調性として知られている）。

これを理解するには、クヌースが「重み付きパス長」と呼ぶ木のものを考えてみましょう。n個の要素を持つ木の重み付きパス長は、すべての要素の長さの合計です。${\displaystyle 2n+1}$考えられる探索経路を、それぞれの確率で重み付けしたグラフ。重み付けされた経路長が最小となる木が、定義上、静的に最適である。

しかし、重み付きパス長には興味深い性質があります。二分木の重み付きパス長を E、左部分木の重み付きパス長をE _L 、右部分木の重み付きパス長をE _Rとします。また、W を木内のすべての確率の合計とします。いずれかの部分木が根に接続されると、その各要素（したがって各探索パス）の深さが 1 増加することに注意してください。また、根自体の深さは 1 であることにも注意してください。これは、木とその 2 つの部分木の間の重み付きパス長の差が、木内のすべての確率の合計と正確に一致することを意味し、次の漸化式につながります。

${\displaystyle E=E_{L}+E_{R}+W}$

この反復により、自然な動的計画法による解が得られます。${\displaystyle E_{ij}}$a _iとa _jの間のすべての値に対する静的に最適な探索木の重み付きパス長を とします。${\displaystyle W_{ij}}$その木の総重量をとし、${\displaystyle R_{ij}}$はルートのインデックスとする。アルゴリズムは以下の式を用いて構築できる。

${\displaystyle {\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {for} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {for} 1\leq i\leq j\leq n\end{aligned}}}$

このアルゴリズムの単純な実装では実際にはO ( n³ ^{)の時間が必要ですが、Knuthの論文には、} O ( n² )の時間しかかからない修正アルゴリズムを作成するために使用できる追加の観察が含まれてい^ます。

クヌースは、動的計画法アルゴリズムに加えて、ほぼ最適な二分探索木を生成するための2つのヒューリスティック（またはルール）を提案した。ほぼ最適な二分探索木を研究する必要があったのは、クヌースのアルゴリズムの時間計算量と空間計算量が、${\displaystyle n}$かなり大きい。^{[ 6 ]}

クヌースの法則は、以下のように解釈できる。

• ルール I (ルート最大):最も頻繁に出現する名前をツリーのルートに配置し、サブツリーでも同様に処理します。
• ルールII（二分法）：左部分木と右部分木の合計重みが可能な限り均等になるようにルートを選択し、その後、部分木に対して同様の手順を実行します。

クヌースのヒューリスティクスは、ほぼ最適な二分探索木を実装しています。${\displaystyle O(n\log n)}$時間と${\displaystyle O(n)}$空間。クヌースのヒューリスティクスが最適値からどれだけ離れているかについての分析は、カート・メルホルンによってさらに提案された。^{[ 6 ]}

Knuthのアルゴリズムが要するO ( n² ⁾の時間は、総当たり探索に必要な指数関数的な時間よりも大幅に優れているものの、ツリー内の要素数が非常に多い場合には、実用的とは言えないほど遅い。

1975年、クルト・メルホルンはクヌースのルールに関する重要な性質を証明する論文を発表した。メルホルンの主な結果は、クヌースのヒューリスティックのうち、ほぼ最適な二分探索木を生成するのはルールIIのみであるというものである。一方、ルート最大ルールは、次の単純な議論に基づいて、非常に「悪い」探索木につながることが多い。^{[ 6 ]}

させて

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {with} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$

そして

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$

重み付き経路長を考慮すると${\displaystyle P}$前述の定義に基づいて構築されたツリーについては、以下のようになります。

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$

したがって、ルート最大ルールによって得られるツリーは、右側のみで成長するツリー（ツリーの最深レベルを除く）となり、左側には常に終端ノードが存在する。このツリーのパス長は、${\textstyle \Omega ({\frac {n}{2}})}$また、バランスのとれた探索木（パスが制限されている）と比較すると、${\textstyle O(2\log n)}$）は、同じ周波数分布に対して著しく劣ったパフォーマンスを示すだろう。^{[ 6 ]}

さらに、メーホルンはクヌースの研究を改良し、ルールIIを使用するはるかに単純なアルゴリズムを導入し、静的に最適なツリーのパフォーマンスをわずかでほぼ近似した。${\displaystyle O(n)}$時間。 ^{[ 6 ]}このアルゴリズムは、左と右のサブツリーの合計重みを（確率的に）最もバランスのとれるように木のルートを選択することで、二分ルールと同じ考え方に従います。そして、この戦略は各サブツリーに再帰的に適用されます。

この戦略が優れた近似値を生成することは、任意のパスに沿った部分木の重みが幾何級数的に減少する数列に非常に近いものを形成することに注目すれば直感的に理解できる。実際、この戦略によって生成される重み付きパスの長さは最大で

${\displaystyle 2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}}$

ここで、H は確率分布のエントロピーです。最適な二分探索木は重み付きパス長よりも優れた結果を出すことは決してないため、

${\displaystyle (1/\log 3)H={\frac {H}{\log 3}}}$

この近似は非常に正確である。^{[ 6 ]}

すべての${\displaystyle A_{i}}$値がゼロの場合、最適な木は時間内に見つけることができます${\displaystyle O(n\log n)}$これは、1971 年にTC HuとAlan Tuckerが発表した論文で最初に証明されました。後に Garsia と Wachs によって簡略化されたGarsia–Wachs アルゴリズムは、同じ比較を同じ順序で実行します。このアルゴリズムは、各葉の最適な高さを持つ木を構築するために貪欲アルゴリズムを使用し、順序がバラバラになっているため、同じ高さの別の二分探索木を構築することで機能します。^{[ 7 ]}

動的最適性にはいくつかの異なる定義があり、実行時間に関しては定数係数を除いて実質的にすべて同等です。^{[ 8 ]}この問題は、スレーターとタージャンがスプレッドツリーに関する論文で暗黙的に最初に導入しましたが、^{[ 9 ]}デメインらはそれを非常に優れた形式的な形で記述しています。^{[ 8 ]}

動的最適性問題では、キー 1, ..., n に対するアクセスのシーケンス x ₁ , ..., x _{mが与えられます。各アクセスに対して、BST のルートへの}ポインタが与えられ、そのポインタを使用して以下のいずれかの操作を実行できます。

1. ポインタを現在のノードの左の子に移動します。
2. ポインタを現在のノードの右の子ノードに移動します。
3. ポインタを現在のノードの親ノードに移動します。
4. 現在のノードとその親ノードに対して、1回の回転操作を実行します。

（アクセス中にツリーを再配置する4番目の操作が存在するため、これは動的最適性問題となる。）

_{各アクセスにおいて、ポインタが最終的に目的値 x i}を含むノードに到達する限り、BST アルゴリズムは上記の操作の任意のシーケンスを実行できます。特定の動的 BST アルゴリズムが一連のアクセスを実行するのにかかる時間は、そのシーケンス中に実行される操作の総数に等しくなります。任意の要素セットに対する任意のアクセスシーケンスが与えられた場合、それらのアクセスを実行するために必要な操作の総数は最小値となります。私たちはこの最小値に近づけたいと考えています。

アクセスシーケンスが正確に何であるかを事前に知らなければ、この「神のアルゴリズム」を実装することは不可能ですが、アクセスシーケンス X に対して実行する操作の数として OPT(X) を定義することができ、任意の X に対して、アルゴリズムが時間O (OPT(X))で X を実行する場合（つまり、一定の競争比を持つ場合）、アルゴリズムは動的に最適であると言えます。^{[ 8 ]}

この性質を持つと推測されるデータ構造はいくつか存在するが、いずれも証明されていない。このモデルにおいて動的に最適なデータ構造が存在するかどうかは未解決の問題である。

スプレッドツリーは、1985年にダニエル・スレーターとロバート・タージャンによって考案されたバイナリサーチツリーの一種で、標準的なサーチツリー操作が実行されます。${\displaystyle O(\log(n))}$償却時間。^{[ 10 ]}必要な意味で動的に最適であると推測されている。つまり、スプレーツリーは、十分に長いアクセスシーケンス X を O(OPT(X)) の時間で実行すると考えられている。^{[ 9 ]}

タンゴツリーは、2004年にErik D. Demaine、Dion Harmon、John Iacono、およびMihai Pătrașcuによって提案されたデータ構造であり、十分長いアクセスシーケンスXを時間内に実行できることが証明されています。${\displaystyle O(\log \log n\operatorname {OPT} (X))}$これは動的に最適ではないが、競争比率は${\displaystyle \log \log n}$n の妥当な値に対しては、依然として非常に小さい。^{[ 8 ]}

2013年、ジョン・イアコノは、バイナリサーチツリーの幾何学を利用して、バイナリサーチツリーアルゴリズムが動的に最適であれば動的に最適となるアルゴリズムを提供する論文を発表しました。 ^{[ 11 ]}ノードは2次元の点として解釈され、最適なアクセスシーケンスは、それらの点の最小の樹状充足スーパーセットです。スプレーツリーやタンゴツリーとは異なり、イアコノのデータ構造は、アクセスシーケンスステップごとに定数時間で実装できることが知られていないため、動的に最適であっても、他のサーチツリーデータ構造よりも非定数係数で遅くなる可能性があります。

インターリーブ下限は、動的最適性の漸近的な下限である。