Y高速トライ

コンピュータサイエンスにおいて、y-高速トライは、境界付きドメインの整数を格納するためのデータ構造です。これは、 O ( n )のスペースを使用して、 O (log log  M )の時間で正確なクエリと先行クエリまたは後続クエリをサポートします。ここで、 nは格納された値の数、Mはドメイン内の最大値です。この構造は、x-高速トライで使用されるO ( nlogM ) の スペースを削減するために、1982年にDan Willardによって提案されました^[1]。

y-高速トライは 2 つのデータ構造から構成されます。上半分は x-高速トライで、下半分は多数のバランスのとれた二分木で構成されています。キーはO (log  M ) 個の連続する要素のグループに分割され、各グループに対してバランスのとれた二分探索木が作成されます。挿入と削除を効率的に行うために、各グループには少なくとも (log  M )/4、最大で 2 log  M個の要素が含まれます。^[2]各バランスの二分探索木に対して、代表rが選択されます。これらの代表は x-高速トライに格納されます。代表rは、それに関連付けられた木の要素である必要はありませんが、 rの後続要素およびその後続要素に関連付けられた木の最小要素よりも小さい整数であり、 rの前続要素およびその後続要素に関連付けられた木の最大要素よりも大きい整数である必要があります。最初、木の代表は、その木の最小要素と最大要素の間の整数になります。

x-高速トライはO ( n  / log  M ) 個の代表を格納し、各代表はO ( log  M ) 個のハッシュ テーブルに出現するため、y-高速トライのこの部分はO ( n ) 個のスペースを使用します。バランスのとれた二分探索木は合計でn個の要素を格納し、 O ( n ) 個のスペースを使用します。したがって、y-高速トライは合計でO ( n ) 個のスペースを使用します。

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

• Find ( 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 )時間かかります。^[1]

キーk自体と同様に、その後継キーは、 kより大きい最小の代表rのツリーか、 rの先行キーのツリーに格納できます。したがって、キーkの後継キーを見つけるには、まず x-fast トライでkより大きい最小の代表キーを検索します。次に、この代表キーを使用して、x-fast トライで先行キーを取得します。これら 2 つの代表キーは、 kの後継キーを検索する 2 つのバランスのとれた二分探索木を指します。^[3]

x-fastトライでkより大きい最小の代表rを見つけるにはO (log log  M )時間がかかり、rを使用してその前任者を見つけるには定数時間がかかります。O (log  M )要素を含む2つのバランスのとれたバイナリ検索ツリーを検索するには、それぞれO (log log  M )時間がかかります。したがって、キーkの後継者はO (log log  M )時間で見つかり、その値を取得できます。^[1]

キーkの先行キーの検索は、その後続キーの検索と非常によく似ています。 x 高速トライでkより小さい最大の代表r を検索し、 r を使用してx 高速トライで先行キーを取得します。最後に、これら 2 つの代表の 2 つのバランスのとれた二分探索木でkの先行キーを検索します。これにはO (log log  M ) の時間がかかります。

新しいキー/値ペア ( k、v ) を挿入するには、まずどのバランスのとれた二分探索木にk を挿入するかを決定する必要があります。このために、kの後継を含む木T を見つけます。次に、k をTに挿入します。すべてのバランスのとれた二分探索木にO (log  M ) 個の要素が含まれるようにするには、T を2 つのバランスのとれた二分探索木に分割し、その代表が 2 log M個を超える要素を含む場合は、その代表を x 高速トライから削除します 。2つの新しいバランスのとれた二分探索木には、それぞれ最大で log  M  + 1 個の要素が含まれます。各木の代表を選び、これを x 高速トライに挿入します。

kの後継者を見つけるのにはO ( log log  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 ) の償却時間がかかります。 ^[3]

削除は挿入と非常によく似ています。まず、バランスのとれた二分探索木の 1 つでキーk を見つけ、この木Tからそれを削除します。すべてのバランスのとれた二分探索木にO (log  M ) 個の要素が含まれるようにするには、 Tに含まれる要素が (log M )/4 個未満の場合は、後続または先行のバランスのとれた二分探索木と T をマージします。マージされた木の代表は x 高速トライから削除されます。マージされた木に 2 log  M個を超える要素が含まれる可能性があります。この場合、新しく形成された木はほぼ同じサイズの 2 つの木に分割されます。次に、新しい木ごとに新しい代表を選択し、これを x 高速トライに挿入します。

キー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 ) の償却時間がかかります。^[3]

削除したい要素がX高速トライの葉である場合、この番号は2つの二分探索木を分離するためだけのものであり、この番号は返されないという注意書きを付けることに注意してください。この場合、番号は実際には削除されません。これにはO (1)時間がかかり、キーkの検索にはO (log log  M )時間がかかります。したがって、時間計算量はO (log log  M )です。^[4]

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