最適二分探索木

コンピュータサイエンスにおいて、最適二分探索木（最適BST）は、重みバランス二分木とも呼ばれ、^[1]与えられたアクセスシーケンス（またはアクセス確率）に対して可能な限り最短の検索時間（または期待検索時間）を提供する二分探索木です。最適BSTは一般に、静的と動的の2種類に分けられます。

静的最適性問題では、ツリーは構築後に変更できません。この場合、ツリーのノードの特定のレイアウトが存在し、与えられたアクセス確率に対して最小の予想検索時間を提供します。要素のアクセス確率に関する情報に基づいて、静的に最適なツリーを構築または近似するさまざまなアルゴリズムが存在します。

動的最適性問題では、ツリーはいつでも変更でき、通常はツリーの回転を許可します。ツリーにはルートから始まるカーソルがあり、これを移動したり変更に使用したりできます。この場合、これらの操作の最小コスト シーケンスが存在し、カーソルがターゲット アクセス シーケンスのすべてのノードを順番に訪問します。スプレー ツリーは、動的最適ツリーと比較して、すべてのケースで一定の競合比を持つと推測されますが、これはまだ証明されていません。

Knuthによって定義された静的最適性問題^[2]では、n 個の順序付けられた要素の集合と確率の集合が与えられます。要素を から で表し、確率を から、確率をまで表します。は要素の検索（または検索 の成功）が行われる確率です。^[3]の場合、は から までの要素の検索（または検索 の失敗）が行われる確率、[3] は より厳密に小さい要素の検索 （または検索の失敗）^が行われる確率です。 は より厳密に大きい要素の検索 （または検索 の失敗）が行われる確率です。これらの確率はすべての可能な検索をカバーするため、合計は 1 になります。 ${\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}}$${\displaystyle 1\leq i<n}$${\displaystyle B_{i}}$${\displaystyle a_{i}}$${\displaystyle a_{i+1}}$ ${\displaystyle B_{0}}$${\displaystyle a_{1}}$${\displaystyle B_{n}}$${\displaystyle a_{n}}$${\displaystyle 2n+1}$

静的最適性問題とは、確率が与えられた場合に、予想される探索時間を最小にする二分探索木を見つける最適化問題である。n要素の集合上の可能な木の数はであり、^[2]はnの指数関数的であるため、通常、総当たり探索は実行可能な解決策ではない。 ${\displaystyle 2n+1}$${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$

1971 年、Knuth は、静的に最適な木をわずかO ( n ² ) 時間で構築できる比較的簡単な動的計画法アルゴリズムを発表しました。 ^[2]この研究で、Knuth は、 1958 年にEdgar GilbertとEdward F. Mooreによって導入された動的計画法アルゴリズムを拡張し、改良しました。 ^[4] Gilbert と Moore のアルゴリズムは時間と空間を必要とし、失敗した検索の確率のみを考慮する最適な二分探索木構築 (最適アルファベット木問題^[5]として知られる) の特定のケース向けに設計されました。つまり、Knuth の研究は、次の洞察に依存していました。静的最適性問題は最適なサブ構造を示します。つまり、特定の木が与えられた確率分布に対して静的に最適である場合、その左と右のサブツリーも分布の適切なサブセットに対して静的に最適でなければなりません (根の単調性として知られる)。 ${\displaystyle O(n^{3})}$${\displaystyle O(n^{2})}$${\textstyle \sum _{i=1}^{n}A_{i}=0}$

これを理解するには、Knuth がツリーの「重み付きパス長」と呼ぶものを考えてみましょう。n 要素のツリーの重み付きパス長は、すべての可能な検索パスの長さをそれぞれの確率で重み付けした合計です。重み付きパス長が最小のツリーは、定義により、静的に最適です。 ${\displaystyle 2n+1}$

しかし、重み付きパス長には興味深い特性があります。E をバイナリ ツリーの重み付きパス長、E _{L を}その左サブツリーの重み付きパス長、E _{R を}その右サブツリーの重み付きパス長とします。また、W をツリー内のすべての確率の合計とします。いずれかのサブツリーがルートに付加されると、その各要素 (つまり各検索パス) の深さが 1 ずつ増加します。また、ルート自体の深さは 1 です。つまり、ツリーとその 2 つのサブツリー間の重み付きパス長の差は、ツリー内のすべての確率の合計とまったく同じであり、次の繰り返しが導かれます。

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

この再帰により、自然な動的プログラミングの解が得られます。 は、 a _iとa _jの間のすべての値に対する静的に最適な検索ツリーの重み付きパス長、 はそのツリーの合計重み、 はそのルートのインデックスとします。アルゴリズムは、次の式を使用して構築できます。 ${\displaystyle E_{ij}}$${\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 ^{3 ) 時間がかかりますが、Knuth の論文には、} O ( n ² ) 時間しかかからない修正されたアルゴリズムを作成するために使用できる追加の観察が含まれています。

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

クヌースのルールは次のようになります。

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

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

Knuth のアルゴリズムにかかるO ( n ² ) 時間は、総当たり検索に必要な指数時間よりも大幅に優れていますが、ツリー内の要素数が非常に多い場合は、まだ実用的であるには遅すぎます。

1975 年、カート・メルホーンはクヌースのルールに関する重要な特性を証明する論文を発表しました。メルホーンの主な結果によると、クヌースのヒューリスティックのうち 1 つ(ルール 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}}}$

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

さらに、メルホーンはクヌースの研究を改良し、ルール 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]

すべての値がゼロという特殊なケースでは、最適なツリーは時間 で見つかります。これは、 1971 年にTC HuとAlan Tuckerが発表した論文で初めて証明されました。その後 Garsia と Wachs によって簡略化されたGarsia–Wachs アルゴリズムは、同じ比較を同じ順序で実行します。このアルゴリズムは、貪欲アルゴリズムを使用して各葉の最適な高さを持つツリーを構築しますが、順序は不規則です。次に、同じ高さの別のバイナリ検索ツリーを構築します。^[7]${\displaystyle A_{i}}$${\displaystyle O(n\log n)}$

次のコード スニペットは、一連のキーとそのキーが検索キーである確率値が与えられた場合に最適なバイナリ検索ツリーを決定します。

パブリック静的フロート calculateOptimalSearchTree(int numNodes, float[] probabilities, int[][] roots) {
       float[][] costMatrix = 新しい float[numNodes + 2][numNodes + 1];
       (int i = 1; i <= numNodes; i++) の場合 {
           コストマトリックス[i][i - 1] = 0;
           コストマトリックス[i][i] = 確率[i];
           ルート[i][i] = i;
           根[i][i - 1] = 0;
       }
       (int 対角線 = 1; 対角線 <= numNodes; 対角線++) {
           (int i = 1; i <= numNodes - 対角; i++) {
               int j = i + 対角線;
               コストマトリックス[i][j] = findMinCost(コストマトリックス、i、j) + sumProbabilities(確率、i、j);
               // 注意: roots[i][j] の割り当てが欠落しています。
               // ツリーを再構築します。
           }
       }
       costMatrix[1][numNodes]を返します。
}

動的最適性にはいくつかの異なる定義がありますが、それらはすべて実行時間に関して定数倍以内と実質的に同等です。^{[8]この問題は、} SleatorとTarjanがスプレー木に関する論文で暗黙的に初めて導入しましたが、^[9] Demaineらはそれを非常にうまく形式的に説明しています。^[8]

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

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

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

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

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

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

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

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

2013 年に、ジョン・イアコノは、二分探索木の幾何学を使用して、任意の二分探索木アルゴリズムが動的に最適である場合に動的に最適なアルゴリズムを提供する論文を発表しました。 ^[11]ノードは 2 次元の点として解釈され、最適なアクセス シーケンスはそれらの点の最小の樹形的に満たされたスーパーセットです。スプレー木やタンゴ木とは異なり、イアコノのデータ構造はアクセス シーケンス ステップごとに一定時間で実装可能であるとは知られていないため、動的に最適であっても、他の探索木データ構造よりも一定でない係数で遅くなる可能性があります。

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

• 木々
• スプレイツリー
• タンゴの木
• 二分探索木の幾何学
• インターリーブ下限