X-高速トライ

コンピュータサイエンスにおいて、x-fast trie は、境界付きドメインの整数を格納するためのデータ構造です。x-fast trie は、O (n log M) のスペースを使用して、O (log log M) の時間で正確なクエリと先行クエリまたは後続クエリをサポートします。ここで、n は格納された値の数、M はドメイン内の最大値です。この構造は、O ( log log  M ) のクエリ時間を維持しながら、ファン・エムデ・  ボアズ 木のスペース使用を改善する方法として、より複雑なy-fast trieとともに 1982 年に Dan Willard によって提案されました [ 1 ^]。

x-fast トライはビット単位のトライです。つまり、各サブツリーが共通のプレフィックスで始まるバイナリ表現を持つ値を格納するバイナリ ツリーです。各内部ノードはサブツリー内の値の共通プレフィックスでラベル付けされ、通常、左の子はプレフィックスの末尾に 0 を追加し、右の子は 1 を追加します。0 からM  − 1 までの整数のバイナリ表現には ⌈log ₂ M ⌉ ビットが使用されるため、トライの高さはO (log  M ) です。  

x-fast トライのすべての値は、リーフに格納されます。内部ノードは、サブツリーにリーフがある場合にのみ格納されます。内部ノードに左の子がない場合、代わりに右のサブツリーの最小のリーフへのポインタ (子孫ポインタと呼ばれる) が格納されます。同様に、右の子がない場合、左のサブツリーの最大のリーフへのポインタが格納されます。各リーフには、その前のリーフと次のリーフへのポインタが格納され、二重リンク リストが形成されます。最後に、各レベルに、そのレベルのすべてのノードを含むハッシュ テーブルがあります。これらのハッシュ テーブルを合わせて、レベル検索構造 (LSS) を形成します。最悪の場合のクエリ時間を保証するには、これらのハッシュ テーブルで動的完全ハッシュまたはカッコウ ハッシュを使用する必要があります。

各要素のルートからリーフへのパスの長さはO (log  M ) なので、合計のスペース使用量はO ( n  log  M ) になります。

ファン・エムデ・ボアズ木と同様に、x-fast トライは順序付き連想配列の操作をサポートします。これには、通常の連想配列操作に加えて、 SuccessorとPredecessor という2 つの順序操作が含まれます。

• Find ( k ): 指定されたキーに関連付けられた値を見つける
• 後継者（k）：指定されたキー以上の最小のキーを持つキー/値のペアを見つける
• 先行キー（k）：指定されたキー以下の最大のキーを持つキー/値のペアを検索します。
• 挿入( k , v ): 指定されたキー/値のペアを挿入する
• 削除( k ): 指定されたキーのキー/値のペアを削除します。

データ構造内のキーkに関連付けられた値を見つけることは、すべてのリーフのハッシュテーブルであるLSS [0]でkを検索することによって定数時間で行うことができます。 ^[2]

たとえば、上のグラフで 4 を探している場合は、次の手順を実装します。

• ステップ 1: 10 進数の 4 を 2 進数の 100 に変換します。
• ステップ 2: ルートから始めて、各レベルへのパスをたどってみます。100 の最初の数字は 1 なので、ルートの右パス (1) をたどってノード「1」まで進みます。
• ステップ 3: ステップ 2 を繰り返します。100 の 2 番目の数字は 0 なので、ノード「1」の左のパス (0) をたどってノード「10」まで進みます。
• ステップ 4: ステップ 3 を繰り返します。100 の 3 番目の数字は 0 なので、ノード「10」の左のパス (0) をたどってノード「100」まで進みます。

キーkの後継または先行を検索するには、まずkの最下位の祖先であるA _{k を}検索します。これは、 kと最も長い共通プレフィックスを持つトライ内のノードです。A _{k を}検索するには、レベルでバイナリ検索を実行します。レベルh /2 から開始します。ここで、h はトライの高さです。各レベルで、レベル検索構造内の対応するハッシュ テーブルを、適切な長さのkのプレフィックスを使用して照会します。そのプレフィックスを持つノードが存在しない場合は、A _{k が}上位レベルにあるはずなので、検索をそれらのレベルに制限します。そのプレフィックスを持つノードが存在する場合は、A _{k が}上位レベルにあるはずがないので、検索を現在のレベルとそれより低いレベルに制限します。

kの最下位の祖先が見つかると、そのサブツリーの 1 つに葉があり (そうでなければトライには含まれません)、k は他のサブツリーにあるはずです。したがって、子孫ポインターはkの後継または先行を指します。どちらを探しているかによって、リンク リスト内で次の葉または前の葉まで 1 ステップ進む必要がある場合があります。

トライの高さはO (log  M )なので、最も低い祖先を探すバイナリ検索にはO (log log  M )の時間がかかります。その後、後続または先行は定数時間で見つかるため、合計クエリ時間はO (log log  M )です。^[1]

たとえば、上のグラフで 3 の前身を探す場合は、次の手順を実行します。

• ステップ 1: 10 進数の 4 を 2 進数の 011 に変換します。
• ステップ 2: ルートから開始し、各レベルへのパスをたどってみます。011 の最初の数字は 0 なので、ルートの左のパス (0) をたどってノード「0」まで進みます。
• ステップ 3: ステップ 2 を繰り返します。011 の 2 番目の数字は 1 なので、正しいパス (1) をたどってみます。ただし、ノード "0" には正しいパスがないため、ポインターに従ってノード "001" に進みます。
• ステップ 4: 001 は 011 より小さいため、011 の前の数字を表します。したがって、3 の前数字は 1 (001) です。

キーと値のペア ( k、v ) を挿入するには、まずkの先行と後続を見つけます。次に、 kの新しいリーフを作成し、後続と先行の間のリーフのリンク リストに挿入して、 vへのポインターを指定します。次に、ルートから新しいリーフまで移動し、途中で必要なノードを作成し、それらをそれぞれのハッシュ テーブルに挿入して、必要に応じて子孫ポインターを更新します。

トライの高さ全体を歩いていく必要があるため、このプロセスにはO（log  M）の時間がかかります。^[3]

キーk を削除するには、リーフのハッシュ テーブルを使用してそのリーフを見つけます。リンク リストからそれを削除しますが、後続と先行がどれであったかを覚えておいてください。次に、リーフからトライのルートまで移動し、サブツリーにkのみが含まれるすべてのノードを削除し、必要に応じて子孫ポインタを更新します。 kを指していた子孫ポインタは、どのサブツリーが欠落しているかに応じて、 kの後続または先行のいずれかを指すようになります。

挿入と同様に、トライのすべてのレベルを通過する必要があるため、O（log  M ）の時間がかかります。 ^[3]

ウィラードは、主にy高速トライの導入としてx高速トライを導入しました。y高速トライは、 O ( n )のスペースのみを使用し、O (loglogM  )の時間で挿入と削除を可能にしながら、同じクエリ時間を提供します。^[1]

パトリシアトライに似た圧縮技術は、実際にはx-fastトライのスペース使用量を大幅に削減するために使用できます。^[4]

レベル間の二分探索の前に指数探索を使用し、現在のプレフィックスxだけでなくその後続のプレフィックスx  + 1も照会することにより、x高速試行は先行クエリと後続クエリに時間O (log log  Δ )で応答できます。ここで、Δはクエリ値とその先行または後続の差です。^[2]

• オープンデータ構造 - 第 13 章 - 整数のデータ構造