スキップリスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/12 19:08 UTC 版)
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にWilliam Pughが発表した[1][2][3][4]。
| ||||||||||||||||||||||||||||||||||||
- ^ Pugh, William (August 1989). “Skip lists: a probabilistic alternative to balanced trees”. Proceedings of the Workshop on Algorithms and Data Structures, Ottawa Canada.
- ^ Pugh, William (June 1990). “Skip lists: a probabilistic alternative to balanced trees”. Communications of the ACM 33: 668-676.
- ^ Pugh, William (1990). “Concurrent Maintenance of Skip Lists”. Univ. of Maryland Institute for Advanced Computer Studies Report No. UMIACS-TR-90-80 (University of Maryland at College Park).
- ^ a b Pugh, William (1990). “A Skip List Cookbook”. Univ. of Maryland Institute for Advanced Computer Studies Report No. UMIACS-TR-89-72.1 (University of Maryland at College Park).
- ^ Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). “Data Structures with Unpredictable Timing”. ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 3-642-04443-3
- ^ J. R. Woodwark (1984). “Compressed Quad Trees”. Computer journal 27 (3): 225-229.
- ^ David Eppstein; Michael T. Goodrich; Jonathan Z. Sun (2005). “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data”. SCG '05 Proceedings of the twenty-first annual symposium on Computational geometry: 296-305. doi:10.1145/1064092.1064138.
- ^ James Aspnes; Gauri Shah (2003). “Skip graphs”. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms: 384–393.
- ^ ConcurrentSkipListSet (Java Platform SE 8 )
- ^ ConcurrentSkipListMap (Java Platform SE 8 )
[続きの解説]
「スキップリスト」の続きの解説一覧
- 1 スキップリストとは
- 2 スキップリストの概要
- 3 説明
- 4 歴史
- 5 実装
- スキップリストのページへのリンク
