デカルト木

コンピュータ サイエンスでは、カルテシアン ツリーは、異なる数のシーケンスから派生した二分木です。カルテシアン ツリーを構築するには、そのルートをシーケンス内の最小の数に設定し、この数の前後の部分シーケンスから左と右の部分ツリーを再帰的に構築します。これは、対称 (順序どおり) なトラバーサルによって元のシーケンスが返される 最小ヒープとして一意に定義されます。

デカルト木は、幾何学的範囲検索データ構造のコンテキストで Vuillemin (1980) によって導入されました。また、二分探索問題用のtreapおよびランダム二分探索木データ構造の定義、ほぼソートされた入力に対して効率的に実行される比較ソートアルゴリズム、およびパターン マッチングアルゴリズムの基礎としても使用されています。シーケンスのデカルト木は線形時間で構築できます。

デカルト木は、根付き木の一種である二分木を使用して定義されます。与えられた異なる数のシーケンスに対してデカルト木を構築するには、そのルートをシーケンス内の最小の数に設定し、[ ^{1]この数の前後の部分シーケンスからそれぞれ左と右の部分木を}再帰的に構築します。基本ケースとして、これらの部分シーケンスの 1 つが空の場合、左または右の子は存在しません。^[2]

また、順序付けプロパティを使用して、再帰的ではなく直接的にカルテシアン ツリーを特徴付けることもできます。どのツリーでも、任意のノードをルートとするサブツリーは、親ポインタを繰り返したどることで到達できる他のすべてのノードで構成されます。異なる数値のシーケンスのカルテシアン ツリーは、次のプロパティによって定義されます。

1. シーケンスのカルテシアン ツリーは、シーケンス内の各数値ごとに 1 つのノードを持つバイナリ ツリーです。
2. ツリーを対称的に（順番に）トラバースすると、元のシーケンスになります。同様に、各ノードについて、左のサブツリーの数字はシーケンス内でそのノードより前になり、右のサブツリーの数字は後になります。
3. ツリーには最小ヒープ特性があり、ルート以外のノードの親の値はノード自体の値よりも小さくなります。^[1]

これら 2 つの定義は同等です。上記のように再帰的に定義されたツリーは、上記の特性を持つ唯一のツリーです。数値のシーケンスに繰り返しが含まれている場合は、上記の構成を適用する前に一貫したタイブレークルールに従うことで、その数値のカルティシアンツリーを決定できます。たとえば、2 つの等しい要素の最初の要素は、2 つのうちの小さい方として扱うことができます。^[2]

デカルト木は、ヴィユミン (1980) によって導入され、命名されました。彼は、デカルト木を、幾何学的組合せ論とデータ構造の設計および分析との相互作用の例として使用しました。特に、ヴィユミンは、これらの構造を使用して、バイナリ検索木での連結および分割操作の平均的なケースの複雑さを分析しました。名前は、平面のデカルト座標系に由来しています。この構造の 1 つのバージョンでは、以下で説明する 2 次元範囲検索アプリケーションのように、点集合のデカルト木は、対称的なトラバーサル順序として、点の -座標によるソート順序を持ち、点の -座標に従ってヒープ特性を持ちます。ヴィユミンは、この構造の幾何学的バージョンと、ここでのデカルト木がシーケンスから定義される定義の両方について説明しました。点座標の代わりにシーケンスを使用すると、より一般的な設定が提供され、デカルト木を非幾何学的問題にも適用できます。^[2]${\displaystyle x}$${\displaystyle y}$

直交木は、入力シーケンスから線形時間で構築できます。1 つの方法は、シーケンス値を左から右の順序で処理し、ツリーの上方向と下方向の両方のトラバースが可能な構造で、これまでに処理されたノードの直交木を維持することです。新しい各値 を処理するには、シーケンス内の の前の値を表すノードから開始し、このノードからツリーのルートへのパスをたどり、より小さい値が見つかるまで続けます。ノードはの右の子になり、 の前の右の子はの新しい左の子になります。この手順の合計時間は線形です。これは、各新しいノードの親の検索に費やされた時間が、ツリーの右端のパスから削除されたノードの数に対して課せられるためです。^[3]${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$

代替の線形時間構築アルゴリズムは、最も近い小さい値問題に基づいています。入力シーケンスで、値の左隣を、より前に発生し、 より小さく、他のどの小さい値よりも位置が に近い値として定義します。右隣は対称的に定義されます。左隣のシーケンスは、入力のサブシーケンスを含むスタックを維持するアルゴリズムによって見つけることができます。新しいシーケンス値ごとに、スタックが空になるか、その先頭要素が より小さくなるまでポップされ、その後スタックにプッシュされます。 の左隣は、がプッシュされた時点での先頭要素です。右隣は、同じスタックアルゴリズムをシーケンスの逆に適用することで見つけることができます。デカルトツリーの の親は、 の左隣または の右隣のいずれかで、存在し、値が大きい方です。左隣と右隣は、並列アルゴリズムによって効率的に構築することもできるため、この定式化は、デカルトツリー構築の効率的な並列アルゴリズムで役立ちます。^[4]${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$${\displaystyle a}$

デカルト木構築のためのもう 1 つの線形時間アルゴリズムは、分割統治法に基づいています。このアルゴリズムは、入力の各半分に対して再帰的に木を構築し、2 つの木をマージします。マージ プロセスには、これらの木の左スパインと右スパイン上のノードのみが関係します。左スパインとは、ルートから左子エッジをたどって左子のないノードに到達するパスであり、右スパインはその対称的に定義されます。最小ヒープ内のどのパスでもそうですが、両方のスパインには、ルートの最小値からパスの末尾の最大値まで、ソートされた順序で値が設定されています。2 つの木をマージするには、左木の右スパインと右木の左スパインにマージ アルゴリズムを適用し、2 つの木のこれら 2 つのパスを、同じノードを含む単一のパスに置き換えます。マージされたパスでは、左ツリーの各ノードのソート順における後続ノードは右の子に配置され、右ツリーの各ノードの後続ノードは左の子に配置されます。これは、スパイン内の後続ノードに以前使用されていた位置と同じです。左ツリーのノードの左の子と右ツリーのノードの右の子は変更されません。このアルゴリズムは並列化可能で、再帰の各レベルで 2 つのサブ問題のそれぞれを並列に計算でき、マージ操作も効率的に並列化できます。^[5]

要素の挿入と要素の遅延削除を条件として、動的入力のカルテシアン ツリーを操作ごとに対数償却時間で維持することが可能です。ここで、遅延削除とは、ツリー内の要素を削除済み要素としてマークすることによって削除操作が実行されることを意味しますが、実際にはツリーから削除されるわけではありません。マークされた要素の数がツリー全体のサイズの一定の割合に達すると、マークされていない要素のみを保持してツリーが再構築されます。^[6]

デカルト木は、範囲最小化クエリのための効率的なデータ構造の一部を形成します。この種のクエリへの入力は、元のシーケンスの連続したサブシーケンスを指定します。クエリ出力はこのサブシーケンスの最小値である必要があります。^[7]デカルト木では、この最小値は、サブシーケンスの左端と右端の値の最小共通祖先で見つけることができます。たとえば、例のシーケンスのサブシーケンス (12,10,20,15,18) では、サブシーケンス (10) の最小値は、左端と右端の値 (12 と 18) の最小共通祖先を形成します。最小共通祖先は、格納に線形スペースを必要とし、線形時間で構築できるデータ構造を使用して、クエリごとに定数時間で見つけることができるため、範囲最小化問題にも同じ境界が当てはまります。^[8]

Bender と Farach-Colton (2000) は、範囲最小化のデータ構造が最小共通祖先を見つけるのにも使用できることを示して、2 つのデータ構造の問題の関係を逆転させました。彼らのデータ構造は、ツリーの各ノードをルートからの距離に関連付け、これらの距離のシーケンスを(エッジが 2 倍になった) ツリーのオイラー ツアーの順序で構築します。次に、結果のシーケンスの範囲最小化データ構造を構築します。特定のツリー内の任意の 2 つの頂点の最小共通祖先は、シーケンス内のこれらの 2 つの頂点の初期位置間の間隔に現れる最小距離として見つけることができます。Bender と Farach-Colton は、この変換から得られるシーケンスに使用できる範囲最小化の方法も提供しています。これらのシーケンスは、隣接するシーケンス値が 1 つ異なるという特別なプロパティを持っています。彼らが説明しているように、この形式を持たない配列における範囲最小化では、カルテシアンツリーを使用して範囲最小化問題を最小共通祖先に縮小し、次にオイラーツアーを使用して最小共通祖先をこの特別な形式の範囲最小化問題に縮小することが可能です。^[9]

同じ範囲最小化問題は、2 次元の範囲検索という別の解釈も与えられます。直交平面上の有限個の点の集合は、点を -座標でソートし、この順序で -座標をこのツリーが形成される値のシーケンスとして使用することにより、直交ツリーを形成するために使用できます。が不等式 によって定義されるある垂直スラブ内の入力点のサブセットであり、が 内の最も左の点( -座標が最小の点) であり、 が内の最も右の点( -座標が最大)である場合、直交ツリー内のとの最下位の共通祖先は、スラブ内の最も下の点になります。 3辺の範囲クエリは、3つの不等式とで囲まれた領域内のすべての点をリストするタスクであり、この最下点を見つけ、その-座標を と比較し、（点が3辺領域内にある場合）と の間、およびと の間に囲まれた2つのスラブで再帰的に続行することで回答できます。このようにして、スラブ内の左端と右端の点が特定された後、3辺領域内のすべての点を点ごとに定数時間でリストできます。^[3]${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle L\leq x\leq R}$${\displaystyle p}$${\displaystyle S}$${\displaystyle x}$${\displaystyle q}$${\displaystyle S}$${\displaystyle x}$${\displaystyle p}$${\displaystyle q}$${\displaystyle L\leq x\leq R}$${\displaystyle y\leq T}$${\displaystyle b}$${\displaystyle y}$${\displaystyle T}$${\displaystyle p}$${\displaystyle b}$${\displaystyle b}$${\displaystyle q}$

直交木の最低共通祖先という同じ構成により、任意の超距離空間内の点のペア間の距離をクエリごとに一定時間でクエリできる線形空間を持つデータ構造を構築できます。超距離内の距離は、メトリックの最小全域木におけるミニマックスパスの重みと同じです。 ^[10]最小全域木から、最小全域木の最も重いエッジを表すルートノードを持つ直交木を構築できます。このエッジを削除すると、最小全域木は 2 つのサブツリーに分割され、これらの 2 つのサブツリーに対して再帰的に構築された直交木は、直交木のルートノードの子になります。直交木の葉はメトリック空間の点を表し、直交木の 2 つの葉の最低共通祖先は、最小全域木で 2 つの点間の最も重いエッジであり、その重みは 2 つの点間の距離に等しくなります。最小全域木が見つかり、その辺の重みがソートされると、カルテシアン木は線形時間で構築できます。^[11]

ソートされたシーケンスのデカルト木は、左端の端点をルートとするパスグラフです。このツリーでのバイナリ検索は、パスでのシーケンシャル検索に退化します。ただし、別の構成では、デカルト木を使用して、ソートされた値のシーケンスから対数深さのバイナリ検索木を生成します。これは、各値の優先順位番号を生成し、優先順位のシーケンスを使用してデカルト木を生成することで実行できます。この構成は、上記の幾何学的フレームワークで同等に考えることができます。このフレームワークでは、点の集合の -座標がソートされたシーケンスの値であり、-座標がそれらの優先順位です。^[12]${\displaystyle x}$${\displaystyle y}$

このアイデアは、優先順位として乱数を使用することを提案した Seidel & Aragon (1996) によって適用されました。このランダムな選択から得られる自己バランス型二分探索木は、二分探索木と最小ヒープ機能の組み合わせから、 treapと呼ばれます。treap への挿入は、新しいキーを既存の木の葉として挿入し、その優先順位を選択し、次に、この挿入によって生じたヒープ特性の違反を修復するために、ノードから木のルートまでのパスに沿って木の回転操作を実行することによって実行できます。削除も同様に、木に一定量の変更を加えた後、木内の単一のパスに沿って一連の回転を実行することによって実行できます。^[12]このデータ構造のバリエーションである zip 木は、同じランダムな優先順位のアイデアを使用しますが、優先順位のランダム生成を簡素化し、挿入と削除を別の方法で実行します。つまり、シーケンスとそれに関連するデカルト木を 2 つのサブシーケンスと 2 つの木に分割し、それらを再結合します。^[13]

キーがツリーに挿入されるたびに、各キーの優先順位がランダムかつ独立に 1 回選択される場合、結果として得られるカルテシアン ツリーは、ランダム バイナリ サーチ ツリーと同じ特性を持つことになります。ランダム バイナリ サーチ ツリーは、空のツリーから始めて、ランダムに選択された順列でキーを挿入することによって計算されるツリーで、挿入のたびに、以前のツリー構造は変更されず、新しいノードがツリーのリーフとして挿入されます。ランダム バイナリ サーチ ツリーは、treap よりもはるかに長い間研究されており、検索ツリーとして適切に動作することがわかっています。任意の値に対する検索パスの期待長さは最大で であり、ツリー全体の深さ (ルートからリーフまでの最大距離)は、高い確率で対数的になります。より正式には、ノードの数が無限大に近づくにつれて、深さが確率で 1 に近づくような定数が存在します。同じ良好な動作は treap にも引き継がれます。また、アラゴンとザイデルが示唆しているように、頻繁にアクセスされるノードの優先順位を変更して、それらのノードをツリーのルートに向かって移動させ、同じキーへの将来のアクセスを高速化することも可能です。^[12]${\displaystyle 2\ln n}$${\displaystyle C}$${\displaystyle \leq C\ln n}$

Levcopoulos & Petersson (1989) は、カルテシアン ツリーに基づくソート アルゴリズムについて説明しています。彼らは、このアルゴリズムを最大値がルートにあるツリーに基づくものとして説明していますが、^[14]最小値がルートにあるという規則に従ってカルテシアン ツリーをサポートするように簡単に変更できます。一貫性を保つために、以下ではこのアルゴリズムの修正バージョンについて説明します。

レヴコプロス・ピーターソンアルゴリズムは、候補となる最小値の優先キューを維持し、各ステップでこのキュー内の最小値を見つけて削除し、この値を出力シーケンスの末尾に移動する選択ソートまたはヒープソートのバージョンと見なすことができます。彼らのアルゴリズムでは、優先キューは、デカルトツリー内の親がすでに見つかり削除されている要素のみで構成されます。したがって、アルゴリズムは次の手順で構成されます。^[14]

1. 入力シーケンスのカルテシアンツリーを構築する
2. 優先キューを初期化し、最初はツリールートのみを含む
3. 優先キューが空でない間:
   • 優先キュー内の最小値を見つけて削除する
   • この値を出力シーケンスに追加する
   • 削除された値のカルテシアンツリーの子を優先キューに追加します。

Levcopoulos と Petersson が示すように、入力シーケンスが既にほぼソートされている場合、優先キューのサイズは小さいままなので、この方法はほぼソートされた入力を利用してより速く実行できます。具体的には、このアルゴリズムの最悪ケースの実行時間は です。ここで、はシーケンスの長さ、はシーケンス内のすべての値について、指定された値を囲むシーケンス値の連続ペアの数の平均です (つまり、指定された値は 2 つのシーケンス値の間にあります)。彼らはまた、任意のおよび (非定数)に対して、比較ベースのソートアルゴリズムはいくつかの入力に対して比較を使用する必要があるという下限を証明しています。^[14]${\displaystyle O(n\log k)}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle \Omega (n\log k)}$

デカルト木マッチングの問題は、与えられたパターンと同じ形のデカルト木を持つ、与えられた文字列の部分文字列（または場合によっては部分列）を探すという文字列マッチングの一般化された形式として定義されています。単一パターンまたは複数パターンの問題のバリエーションに対する高速アルゴリズムが開発されており、サフィックス木やその他のテキスト索引構造に類似したデータ構造も開発されています。^[15]