スキップ四分木
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/12 19:08 UTC 版)
スキップリストはリストのため1次元だが、これを2次元やそれ以上に拡張した物をスキップ四分木（英: skip quadtree）・スキップ八分木（英: skip octree）という。一番下の階層は連結リストに相当する部分に圧縮四分木を使い、要素にランダムに高さをふり、各高さで圧縮四分木を作る。四分木の同じ分割点に当たる部分は隣の高さの四分木の分割点同士でリンクを張りたどれるようにする。探索・挿入・削除の計算量はスキップリスト同様に平均 O(log n)。圧縮四分木を使った事により空間計算量は平均 O(n)。2005年に David Eppstein らが発表した。 なお、kd木でも類似の事が出来る。
※この「スキップ四分木」の解説は、「スキップリスト」の解説の一部です。
「スキップ四分木」を含む「スキップリスト」の記事については、「スキップリスト」の概要を参照ください。
ウィキペディア小見出し辞書の「スキップ四分木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- スキップ四分木のページへのリンク
