スキップリスト
スキップリストはリストのため1次元だが、これを2次元やそれ以上に拡張した物をスキップ四分木(英: skip quadtree)・スキップ八分木(英: skip octree)という。一番下の階層は連結リストに相当する部分に圧縮四分木を使い、要素にランダムに高さをふり、各高さで圧縮四分木を作る。四分木の同じ分割点に当たる部分は隣の高さの四分木の分割点同士でリンクを張りたどれるようにする。探索・挿入・削除の計算量はスキップリスト同様に平均 O(log n)。圧縮四分木を使った事により空間計算量は平均 O(n)。2005年に David Eppstein らが発表した。
なお、kd木でも類似の事が出来る。
スキップリストはWillam Pughによって発明され、下記の参照に示される論文に詳細が記載されている。下記の外部リンクを辿って原著論文を読むこともできる。
著者の言を引用すればこうである。
Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.
しかし、速度と使用メモリの利点についてはその後に議論があるようだ。