指数木

指数木
タイプ	木
発明された	1995
発明者	アルネ・アンダーソン
ビッグO記法による時間計算量 手術 平均 最悪の場合 検索 O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) 入れる O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) 消去 O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) O(min( √log n  ,log  n / log  w +log log  n ,log  wlog log  n )) 空間複雑性 空間 の上） の上）

指数木は、深さが増すにつれてノードの子の数が二重指数関数的に減少するタイプの探索木です。値はリーフノードにのみ格納されます。各ノードにはスプリッター（枝分かれ）が含まれます。スプリッターは、探索時に使用されるサブツリー内のすべての値以下の値です。指数木では、子からのスプリッターを含む内部ノードに別のデータ構造を使用することで、高速な探索を可能にします。

指数木は、いくつかの演算において最適な漸近複雑性を実現します。主に理論的な重要性を持ちます。

ツリー構造

指数木は、すべてのノードに分岐子が含まれ、すべての葉ノードに値が含まれる根付き木です。値は分岐子と異なる場合があります。値を含む指数木は再帰的に定義されます。 ${\displaystyle n}$

• 根には子がある ${\displaystyle \Theta (n^{1/k})}$
• ルートのスプリッターは左端の子のスプリッターと同じである
• すべての子のスプリッターはローカルデータ構造に格納されます
• サブツリーは値を持つ指数ツリーです ${\displaystyle \Theta (n^{1-1/k})}$

追加の条件として、スプリッタを使用して値を検索すると、正しいノード（つまり、値を含むノード）が返される必要があります。したがって、サブツリーのルートにスプリッタが含まれ、その右兄弟にスプリッタが含まれる場合、このサブツリーには範囲 のキーのみが含まれます。 ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle [s,s')}$

ローカルデータ構造

ツリーは、値の高速な検索を可能にするために、すべての内部ノードで静的データ構造を使用しています。この構造は、時間 で値を使用して構築可能でなければなりません。この構造における検索時間は と表記されます。 ${\displaystyle d}$ ${\displaystyle O(d^{k-1})}$ ${\displaystyle S(d)}$

このデータ構造としてFusion ツリーを使用できます。

オペレーション

検索

指数木は通常の探索木と同じように探索できます。各ノードでは、ローカルデータ構造を利用して次の子ノードを素早く見つけることができます。

探索の時間計算量を とすると、以下の再帰式が成り立ちます。 ${\displaystyle T(n)}$

${\displaystyle T(n)\leq T(n^{1-1/k})+O(S(n))}$

入れる

消去

参考文献

• アンダーソン、アーネ（1996年10月）「線形空間におけるより高速な決定論的ソートと検索」第37回コンピュータサイエンス基礎会議議事録、pp.  135– 141. doi : 10.1109/SFCS.1996.548472 . ISBN 0-8186-7594-2. S2CID  13603426 .
• Andersson, Arne; Thorup, Mikkel (2007-06-01). 「指数探索木を用いた動的順序集合」 . Journal of the ACM . 54 (3): 13–es. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 . ISSN  0004-5411 . S2CID  8175703 .

「 https://en.wikipedia.org/w/index.php?title=Exponential_tree&oldid=1307789046」より取得