Y-fast_trie
でコンピュータサイエンス、Y-速いトライは、あるデータ構造格納するための整数を有界ドメインから。これは、O（n）スペースを使用して、時間O（log log M）での正確な先行クエリまたは後続クエリをサポートします 。ここで、nは格納された値の数、Mはドメイン内の最大値です。この構造は、1982年にDan Willardによって提案され、x-fastトライによって使用されるO（n log M）スペースを減らします 。
Y-ファストトライ
タイプ トライ
発明された 1982年
によって発明された ダンウィラード
大きなO表記における漸近的な複雑さ
スペース O（n）
検索 O（両対数M）
入れる O（両対数M）償却 平均
消去 O（両対数M）償却平均
コンテンツ
1 構造
2 オペレーション
2.1 探す 2.2 後継者および前任者 2.3 入れる 2.4 消去
3 参考文献
4 外部リンク
構造
y-fastトライの例。x-fastトライに示されているノードは、 O（ n / log M）平衡二分探索木の代表です。
y-fastトライは2つのデータ構造で構成されます。上半分はx-fastトライで、下半分はいくつかのバランスの取れた二分木で構成されます。キーはO（log M）の連続する要素のグループに分割され、グループごとに平衡二分探索木が作成されます。効率的な挿入及び欠失を容易にするために、各グループが少なくとも含まれている（ログ Mを）/ 4であり、最も2ログにおける M個の要素。平衡二分探索木ごとに、代表的なrが選択されます。これらの代表はx-fastトライに保存されます。代表的なrは、それに関連付けられたツリーの要素である必要はありませんが、rの後続要素よりも小さく、その後続要素に関連付けられたツリーの最小要素であり、rの先行要素および最大要素よりも大きい整数である必要がその前任者に関連付けられたツリーの。最初、ツリーの代表は、ツリー内の最小要素と最大要素の間の整数になります。
x-fastトライはO（n / log M）の代表を格納し、各代表はO（log M）ハッシュテーブルで発生するため、y-fastトライのこの部分はO（n）スペースを使用します。平衡二分探索木は、O（n）空間を使用する合計n個の要素を格納します。したがって、合計でy-fastトライはO（n）スペースを使用します。
オペレーション
van Emde Boasツリーやx-fast試行と同様に、y-fast試行は順序付けられた連想配列の操作をサポートします。これには、通常の連想配列操作と、さらに2つの順序操作、SuccessorとPredecessorが含まれます。
検索（k）：指定されたキーに関連付けられた値を検索します
後続（k）：指定されたキー以上の最小のキーを持つキー/値のペアを見つけます
先行（k）：指定されたキー以下の最大のキーを持つキー/値のペアを見つけます
挿入（k、v）：指定されたキー/値のペアを挿入します
削除（k）：指定されたキーを持つキー/値のペアを削除します
探す
キーkは、kより大きい最小の代表rのツリー、またはrの先行ツリーのいずれかに格納できます。これは、二分探索木の代表がそのツリーに格納されている要素である必要がないためです。したがって、最初に、x-fastトライでkより大きい最小の代表rを見つけます。この代表を使用して、rの前身を取得します。これらの2つの代表は、2つの平衡二分探索木を指しています。どちらもkを検索します。
x-fastトライでkより大きい最小の代表rを見つけるには、O（log log M）が必要です。rを使用すると、その前身を見つけるのに一定の時間がかかります。O（log M）要素を含む2つの平衡二分探索木を検索するには、それぞれO（log log M）時間がかかります。したがって、キーkは、O（log log M）時間で検出され、その値が取得されます。
後継者および前任者
キーk自体と同様に、その後続は、kより大きい最小の代表rのツリー、またはrの先行のツリーのいずれかに格納できます。したがって、キーkの後継を見つけるには、最初にx-fastトライを検索して、kより大きい最小の代表を探します。次に、この代表を使用して、x-fastトライで前任者を取得します。これらの2つの代表は、2つの平衡二分探索木を指しています。1つはkの後継を検索します。
x-fastトライでkより大きい最小の代表rを見つけるには、O（log log M）時間がかかり、rを使用してその前身を見つけるには一定の時間がかかります。O（log M）要素を含む2つの平衡二分探索木を検索するには、それぞれO（log log M）時間がかかります。したがって、キーkの後続を見つけ、その値をO（log log M）時間で取得できます。
キーkの先行を検索することは、後続を検索することと非常に似ています。1つはkよりも小さい最大の代表rをx-fastトライで検索し、もう1つはrを使用してx-fastトライの前身を取得します。最後に、これら2つの代表の2つの平衡二分探索木でkの前身を検索します。これにはO（log log M）時間がかかります 。
入れる
新しいキー/値のペア（k、v）を挿入するには、最初に、どの平衡二分探索木にkを挿入する必要があるかを判断する必要がこの目的のために、kの後継を含むツリーTを見つけます。次に、kをTに挿入します。全て平衡二分探索木が含まれていることを保証するために、O（ログ Mの）要素を、一つは分割Tを2本の平衡二分木にして、2つの以上のログが含まれている場合、X高速トライからその代表を削除する M個の要素。2つの新しい平衡二分探索木のそれぞれには、最大でlog M +1要素が含まれます 。各ツリーの代表を選び、これらをx-fastトライに挿入します。
後継見つけるKはかかるO（ログログ M）の時間を。O（log M）要素を含む平衡二分探索木にkを挿入すると、O（log log M）時間もかかります 。O（log M）要素を含むバイナリ検索ツリーの分割は、O（log log M）時間で実行できます。最後に、3つの代表の挿入と削除には、O（log M）時間がかかります 。ただし、O（log M）の挿入と削除ごとに最大で1回ツリーを分割するため、これには一定の償却時間がかかります。したがって、新しいキーと値のペアを挿入するには、O（log log M）の償却時間がかかります。
消去
削除は挿入と非常によく似ています。最初に、平衡二分探索木の1つでキーkを見つけ、それをこのツリーTから削除します。すべての平衡二分探索木にO（log M）要素が含まれるようにするには、Tを（log M）/ 4未満の要素が含まれる場合、Tを後続または先行の平衡二分探索木 とマージします。マージされたツリーの代表は、x-fastトライから削除されます。マージされたツリーに3つ以上のlogM要素が含まれる可能性があります 。この場合、新しく形成されたツリーは、ほぼ同じサイズの2つのツリーに分割されます。次に、新しいツリーごとに新しい代表を選択し、これらをx-fastトライに挿入します。
キーkを見つけるには、O（log log M）時間がかかります。O（log M）要素を含む平衡二分探索木からkを削除すると、O（log log M）時間もかかります 。平衡二分探索木のマージと場合によっては分割には、O（log log M）時間がかかります。最後に、古い代表を削除し、新しい代表をx-fastトライに挿入するには、O（log M）時間がかかります 。ただし、平衡二分探索木のマージと場合によっては分割は、O（log M）の挿入と削除ごとに最大で1回実行されます。したがって、一定の償却時間がかかります。したがって、キーと値のペアを削除するには、O（log log M）の償却時間がかかります。
参考文献
^ ウィラード、ダンE.（1983）。「対数対数の最悪の場合の範囲クエリは、空間Θ（N）で可能です」。情報処理レター。エルゼビア。17（2）：81–84。土井：10.1016 / 0020-0190（83）90075-3。ISSN 0020から0190まで。 ^ ボーズ、プロセンジット; Douïeb、Karim; ドゥイモビッチ、ビーダ; ハワット、ジョン; Morin、Pat（2010）、境界のある宇宙での高速ローカル検索と更新（PDF）、計算幾何学に関する第22回カナダ会議の議事録（CCCG2010）、pp。261–264
^ Schulz、André; クリスチアーノ、ポール（2010-03-04）。「高度なデータ構造の講義9からの講義ノート（Spring ’10、6.851）」（PDF）。
外部リンク
オープンデータ構造-第13章-整数のデータ構造”