指数木

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

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

指数木は、すべてのノードにスプリッタが含まれ、すべてのリーフ ノードに値が含まれるルート付き木です。値はスプリッタと異なる場合があります。値を持つ指数木は再帰的に定義されます。 ${\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))}$

• Andersson, Arne (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.