二分探索木の幾何学

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

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

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

二分探索木を維持するための特定のアルゴリズム（例えば、スプレー木アルゴリズムやイアコノのワーキングセット構造など）は、各アクセスシーケンスごとにコストを持ちます。これは、アクセスシーケンス内の各キーを順番に検索するために構造を使用するのにかかる時間をモデル化します。検索コストは、探索木アルゴリズムが二分探索木への単一のポインタを持ち、各検索の開始時にそのポインタが木の根を指すと仮定してモデル化されます。その後、アルゴリズムは以下の操作の任意のシーケンスを実行します。

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

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

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

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

動的最適性予想は、スプレー木の競争比率が一定であると述べているが、これは未だ証明されていない。二分探索木を幾何学的に捉えることで、この問題を理解する新たな方法が提示され、同様に（推測的に）競争比率が一定となる可能性のある代替アルゴリズムの開発につながった。

幾何学的点集合への変換

オンライン二分探索木問題の幾何学的観点から見ると、アクセスシーケンス （キーセットを持つ二分探索木 (BST) 上で実行される探索のシーケンス）は点の集合にマッピングされ、X 軸はキー空間を表し、Y 軸は時間を表します。これに、タッチされたノードの集合が追加されます。タッチされたノードとは、次のものを指します。木内のノードを指す 1 つのポインタを持つ 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$ において、の点集合を樹状的に満たす最小数の点を配置します。この最小の点集合は一意に定義されます。つまり、の一方の角にで形成される満たされない長方形に対して、もう一方の角をに追加します。 $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). 「動的最適性予想の追求」.空間効率の高いデータ構造、ストリーム、アルゴリズム. コンピュータサイエンス講義ノート. 第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). 「動的最適性予想の追求」.空間効率の高いデータ構造、ストリーム、アルゴリズム. コンピュータサイエンス講義ノート. 第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。