スキップリスト

スキップリストのファイルを置いておいた。
.netのLinkedListNodeと違って属するListへの参照をNodeに持たせていないからほとんどの操作は局所的に可能。つまりheaderやfooterを持たずとも一つのNodeさえあればあらゆる事が可能(O(log N)でheader, footerにたどり着けるので保持しているのと大して変わらない)。

という実装にしておいたにも関わらずSkipListクラスは作ってheader, footerを保持させ、検索メソッドなどはNodeクラスにstaticメソッドとして実装するのではなくSkipListクラスに持たせるという折衷様式。
実装は歪だが、SkipListクラスがheader, footerを持っているために一部の処理が簡単にかけるし、その上で例えば複数のSkipListをマージしたいなどという時にも高速に実行できる。ちょっとコードを書く気になれないが。

こういう記事があるくらいなので、メソッドをオーバーライドする事で区間の和に関して加法的に合成される量(区間における要素の個数というのは最も単純な例にすぎず、可換半群の総和計算なら何でもOK)を効率的に計算できるという汎用性を持ったスキップリストのコードというのはネットで入手しやすいものとしては珍しいのではないだろうか。そのくせLINQのおかげで実装は意外と単純明快だった。

それにしても、こうしてみると、balanced treeに関する小難しいあれこれは一体なんだったのだろうという気になる。シーケンシャルでないケースではピボットをランダムに選ぶツリーを使えばいいだけだし

スキップリストのすごいのは大局的な操作によってbalancingを保つのとは間逆の、独立試行のその独立性によって全く局所的にbalancingが満たされる事。だから、局所的にremoveなんかをしても``おおよそ''二分木であるという性質は全くの不変。まあ、一応headerとfooterの高さを下げられるなら下げるという処理はいれたけどさ。

そういえばこのグラフィックインタフェース
は本来SkipListのライブラリに含めていて呼び出しをしない限りはUIコンポネートはnew()さえされないのでちょっと使わない参照が増えるだけどいう形だったのだが、それにしてもデータ構造のコードの配布に含めるのは気が引けたので外しておいた。もともと.csファイルとしては分離されていたし。