二分探索木の幾何学

コンピュータサイエンスにおいて、二分探索木のオンラインアルゴリズムにおける動的最適性問題に対する1つのアプローチは、境界上に2つの点しかない長方形を避けるために、平面上の点の集合をできるだけ少ない追加点で拡張するという観点から、問題を幾何学的に再定式化することです。^[1]

アクセスシーケンスと競争比率

一般的に定式化されるように、オンライン二分探索木問題には、固定キーセット上で定義された探索木が含まれます。アクセスシーケンスは、各アクセスがキーセットに属するシーケンスです。 $\{1,2,...,n\}$ $x_{1},x_{2},$ $x_{i}$

バイナリ検索ツリーを維持するための特定のアルゴリズム (スプレイツリーアルゴリズムやIacono のワーキングセット構造など)には、アクセスシーケンスごとにコストがあり、アクセスシーケンス内の各キーを順番に検索するために構造を使用するのにかかる時間をモデル化します。検索のコストは、検索ツリーアルゴリズムがバイナリ検索ツリーへの単一のポインターを持ち、各検索の開始時にツリーのルートを指すと仮定してモデル化されます。その後、アルゴリズムは、次の操作の任意のシーケンスを実行します。

ポインタを左の子に移動します。
ポインタを右の子に移動します。
ポインタをその親に移動します。
ポインタとその親に対して単一のツリー回転を実行します。

この一連の操作のどこかの時点で、キーを含むノードにポインターを移動するために検索が必要であり、検索のコストはシーケンスで実行される操作の数です。アクセスシーケンスXでのアルゴリズムAの合計コスト cost _A ( X )は、シーケンス内の連続する各キーの検索コストの合計です。

競争分析の標準として、アルゴリズムAの競争比率は、すべてのアクセスシーケンスにおける、アルゴリズムAのコストと、任意のアルゴリズムが達成できる最良コストの比率の最大値として定義されます。

\rho _{A}=\sup _{X}{\frac {\mathrm {cost} _{A}(X)}{\mathrm {cost} _{\mathrm {opt} }(X)}}.

動的最適性仮説では、スプレーツリーの競争比率は一定であるとされていますが、これはまだ証明されていません。バイナリ検索ツリーの幾何学的視点は、問題を理解する別の方法を提供し、(推測的に) 競争比率が一定である可能性のある代替アルゴリズムの開発につながりました。

幾何学的点集合への変換

オンライン二分探索木問題の幾何学的観点では、アクセスシーケンス （キーセットを持つ二分探索木（BST）上で実行される検索のシーケンス）は、点の集合にマッピングされます。ここで、X軸はキー空間を表し、Y軸は時間を表します。これに、タッチされたノードの集合が追加されます。タッチされたノードとは、次のものを指します。木内のノードを指す単一のポインターを持つBSTアクセスアルゴリズムを考えてみましょう。特定のキーへのアクセスの開始時に、このポインターは木のルートに初期化されます。ポインターがノードに移動するか、ノードに初期化されるたびに、ノードがタッチされていると言います。^[2] 特定の入力シーケンスに対するBSTアルゴリズムは、タッチされる各項目に対して点を描くことで表します。 $x_{1},...,x_{m}$ ${1,2,...,n}$ ${(x_{i},i)}$ $x_{i}$

たとえば、4 つのノードに次の BST が指定されているとします。キーセットは{1, 2, 3, 4}です。

アクセスシーケンスを 3、1、4、2 とします。

最初のアクセスでは、ノード 3 のみがタッチされます。
2 回目のアクセスでは、ノード 3 と 1 がタッチされます。
3 回目のアクセスでは、3 と 4 がタッチされます。
4 回目のアクセスでは、3 をタッチし、次に 1 をタッチし、その後 2 をタッチします。

タッチは幾何学的に表現されます。i番目のアクセスの操作でアイテムxがタッチされると、点 ( x , i ) がプロットされます。

樹木的に満足なポイントセット

点集合が樹状的に満たされているとは、次の特性が成り立つ場合です。同じ水平線または垂直線上にない任意の点のペアに対して、最初の 2 つの点によって張られる長方形内 (境界内または境界上) にある 3 番目の点が存在する。

定理

点を含む点集合は、入力シーケンスの有効な BST に対応する場合にのみ、樹状的に満たされます。 $(x_{i},i)$ $x_{1},x_{2},...,x_{m}$

証拠

まず、有効な BST アルゴリズムの点集合が樹状的に満たされていることを証明します。点およびを考えます。ここで、 $x は時間$ $i$ に触れられ、 $y は時間$ $j$ に触れられます。対称性により、およびであると仮定します。長方形内に、角がおよびである 3 番目の点が存在することを示す必要があります。また、は、時間 $t の$ 直前のノード $a$ と $bの$ 最小共通祖先を表します。いくつかのケースがあります。 $(x,i)$ $(y,j)$ $x<y$ $i<j$ $(x,i)$ $(y,j)$ $\mathrm {LCA} _{t}(a,b)$

の場合、点を使用します。これは、 $x が$ タッチされていた場合、点がタッチされていたに違いないからです。 $\mathrm {LCA} _{i}(x,y)\neq x$ $(\mathrm {LCA} _{i}(x,y),i)$ $\mathrm {LCA} _{i}(x,y)$
の場合、ポイントを使用できます。 $\mathrm {LCA} _{j}(x,y)\neq y$ $(\mathrm {LCA} _{j}(x,y),j)$
上記の 2 つのケースのどちらも当てはまらない場合は、 $x は時間$ $i の$ 直前に $y$ の祖先であり、 $y は時間$ $j の$ 直前に $x$ の祖先である必要があります。その後、ある時間 $k$ で、 $y は$ $x$ より上に回転しているはずなので、その点を使用できます。 $(i\leq k<j)$ $(y,k)$

次に、他の方向を示します。樹状的に満たされた点集合が与えられれば、その点集合に対応する有効な BST を構築できます。BST を、次のタッチ時間によってヒープ順序に編成された treap に編成します。次のタッチ時間は同点があり一意に定義されないことに注意してください。ただし、同点を解消する方法がある限り、これは問題にはなりません。時間 $i$ に到達すると、ヒープ順序プロパティにより、タッチされたノードは上部に接続されたサブツリーを形成します。次に、このサブツリーに新しい次のタッチ時間を割り当て、新しいローカル treap に再配置します。ノードのペア $x$ と $y が$ treap のタッチされた部分とタッチされていない部分の境界にまたがっている場合、 $y が$ $x$ よりも早くタッチされると、左端のポイントは $yではなく$ $x$ の右の子になるため、満たされない長方形になります。 $(x,now)\to (y,next-touch(y))$

帰結

入力シーケンスに対する最適な BST 実行を見つけることは、樹状的に満たされるポイントの最小基数スーパーセット (幾何学的表現で入力を含む) を見つけることと同等です。一般的な入力ポイントセット ( $y$ 座標ごとに 1 つの入力ポイントに限定されない) の樹状的に満たされる最小基数スーパーセットを見つけるというより一般的な問題は、NP 完全であることが知られています。^[1] $x_{1},x_{2},...,x_{m}$

貪欲アルゴリズム

次の貪欲アルゴリズムは、樹形的に満足可能な集合を構築します。

$y$ 座標を増やして、ポイントセットを水平線でスイープします。
時刻 $i$ において、の点の最小数をに配置して、までの点の設定が樹状的に満たされるようにします。この最小の点の集合は一意に定義されます。つまり、の 1 つの角で形成される満たされない長方形ごとに、のもう一方の角を追加します。 $y=i$ $y\geq i$ $(x_{i},i)$ $y=i$

このアルゴリズムは加法項内で最適であると推測されている。^[3]

その他の結果

二分探索木の幾何学は、任意の二分探索木アルゴリズムが動的に最適である場合に、動的に最適なアルゴリズムを提供するために使用されてきました。^[4]

参照

参考文献

^ ab Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Kane, Daniel ; Pătraşcu, Mihai (2009)、「バイナリ検索ツリーの幾何学」、第 20 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA 2009) の議事録、ニューヨーク: 496–505、doi : 10.1137/1.9781611973068.55、ISBN 978-0-89871-680-1
^ Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Pătraşcu, Mihai (2007)、「動的最適性—ほぼ」、SIAM Journal on Computing、37 (1): 240–251、CiteSeerX 10.1.1.99.4964、doi :10.1137/S0097539705447347、MR 2306291、S2CID 1480961
^ Fox, Kyle (2011 年 8 月 15 ～ 17 日)。最大貪欲二分探索木の上限(PDF) 。アルゴリズムとデータ構造: 第 12 回国際シンポジウム、WADS 2011。コンピュータサイエンスの講義ノート。第 6844 巻。ニューヨーク: Springer。pp. 411 ～ 422。arXiv : 1102.4884。doi : 10.1007 /978-3-642-22300-6_35。
^ Iacono, John (2013). 「動的最適性予想の追求」。スペース効率の良いデータ構造、ストリーム、アルゴリズム。コンピュータサイエンスの講義ノート。 Vol. 8066。 pp. 236–250。arXiv : 1306.0207。Bibcode :2013arXiv1306.0207I。doi :10.1007/978-3-642-40273-9_16。ISBN 978-3-642-40272-2.S2CID 14729858 。

[DHIKP09-1] Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Kane, Daniel ; Pătraşcu, Mihai (2009)、「バイナリ検索ツリーの幾何学」、第 20 回 ACM-SIAM 離散アルゴリズムシンポジウム (SODA 2009) の議事録、ニューヨーク: 496–505、doi : 10.1137/1.9781611973068.55、ISBN 978-0-89871-680-1

[2] Demaine, Erik D. ; Harmon, Dion; Iacono, John ; Pătraşcu, Mihai (2007)、「動的最適性—ほぼ」、SIAM Journal on Computing、37 (1): 240–251、CiteSeerX 10.1.1.99.4964、doi :10.1137/S0097539705447347、MR 2306291、S2CID 1480961

[3] Fox, Kyle (2011 年 8 月 15 ～ 17 日)。最大貪欲二分探索木の上限(PDF) 。アルゴリズムとデータ構造: 第 12 回国際シンポジウム、WADS 2011。コンピュータサイエンスの講義ノート。第 6844 巻。ニューヨーク: Springer。pp. 411 ～ 422。arXiv : 1102.4884。doi : 10.1007 /978-3-642-22300-6_35。

[Iacono2013-4] Iacono, John (2013). 「動的最適性予想の追求」。スペース効率の良いデータ構造、ストリーム、アルゴリズム。コンピュータサイエンスの講義ノート。 Vol. 8066。 pp. 236–250。arXiv : 1306.0207。Bibcode :2013arXiv1306.0207I。doi :10.1007/978-3-642-40273-9_16。ISBN 978-3-642-40272-2.S2CID 14729858 。