Skip Lists

Skip Lists は 1990年に William Pugh によって開発されたリスト構造体の一種である。 オリジナルの論文は William Pugh, "Skip Lists: A Probablistic Alternative to Balanced Trees", Communications of the ACM, June 1990 となっている。 この論文は ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf からコピーを入手可能である。 また、Unix Magazine 1999年 1月号 を入手できれば、 そこには日本語で書かれた解説があるが、 これはほとんど論文丸写しに近いので、きっと重宝するだろう。 数多くの、要素が増減しなおかつ入れ替わるようなデータ構造で、 さらにランダムアクセスが

[ono_matope]

スキップリストとマルチリスト

[hiromark]

スキップリストの詳細な説明。/"AVL Tree は 『tcsh と実習でしか使わない』 " ｗｗｗ ← でも、勉強する価値は大きいと思います。

[nelnal]

Skip Lists（とMulti List）のアルゴリズム解説

[sshi]

頻繁に更新するソート済み集合のリンクデータ構造。上位のリンクの作成を乱数で決め、構造全体を確率的に「良い状態」に保つ。変化に強いところは「スモールワールドネットワーク」に似てない？