スキップリスト
出典: フリー百科事典『ウィキペディア(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 実装
Weblioに収録されているすべての辞書からスキップリストを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からスキップリスト を検索
- スキップリストのページへのリンク