[OSASK 1830] [FYI]Skip Lists

[Koyanagi Masaaki <Koyanagi.Masaaki !Atmark! nifty.ne.jp>]

小柳です。

"Skip Lists" というおもしろいデータ構造を見つけましたので紹介します。
1990年にWilliam Pugh によって平衡木の代替として開発されたかなり新しい
データ構造で、検索にかかる平均計算量が O(log n) であり、かつ実装が非常
に簡単です。

オリジナルの論文は
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
にあります。図とアルゴリズム表記を見れば、英語が詳しく分からなくても
内容はつかめると思います。

日本語の情報は
http://www.dd.iij4u.or.jp/~okuyamak/Information/SkipLists.html
やUNIX MAGAZINE 1999年1月号 P.70〜
が参考になります。

OSASK の開発に役立つといいですね。

-- 
小柳 雅明(Koyanagi.Masaaki !Atmark! nifty.ne.jp)
「人の足を止めるのは"絶望"ではなく"諦観"
  人の足を進めるのは"希望"ではなく"意志"」
　　　　　　　　　　　　　　　　　　-- ARMS