@ledsun blog

Hのキーがhellで、Sのキーがslaveだ、と彼は思った。そしてYのキーがyouだ。

アルゴリズムとデータ構造をたどるWebサーフィン

#rustfestの発表

yoshが #rustfest の発表が、すごい面白かったとツイートしているのを見ました。

B木の論文

リンクを貼ってある先が RRB-Trees: Efficient Immutable Vectors いきなりこれを読むのは辛いので、一番古い引用文献*1

[2] R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta informatica, 1(3):173–189, 1972.

をググります。2300引用されている神文献のようです。

Organization and Maintenance of Large Ordered Indexes

どうやらB木の論文のようです。

AVL木の論文

ついでに更に最古引用文献

  1. Adelson-Velskii, G.M., Landis, E. M. : An information organization algorithm. DANSSSR, 146, 263-266 (1962).

をあさります。

G. M. Adel'son-Vel'skii, E. M. Landis, “An algorithm for organization of information”, Dokl. Akad. Nauk SSSR, 1962, Volume 146, Number 2,Pages 263–266

タイトルは違うのですが、著者と発表年を見るとこれのようです。 中身はロシア語なので読めませんでした。 ていうかSSSRって、何かと思ったら旧ソ連のことでした。驚きました。

AVL tree - Wikipediaを見るとAVL木の論文のようです。 AVLって何かと思ったら、Adel'son-Vel'skiiとLandisの頭文字でした。RSA的なネーミングですね。

この辺のことが話題になるということは、Rustは、新しいシステムプログラミング言語なので、まだデータ構造のライブラリが少なく、自分で実装するチャンスがあるのかもしれません。

素振るには?

アルゴリズムの解説はAVL木 - Wikipediaにありますが、理解するには実装するのが手っ取り早いです。 C言語やRustのような低レイヤーの言語で実装しないと理解できないのでしょうか? 使い慣れたJavaScriptで実装しても理解できるものなのでしょうか? と、悩んでいたら

AVL Treeの実装も含まれていました。 これを参考にすると良さそうです。

*1:古典なので既知の情報である確率が高い上に、わざわざ引用しているので読む価値が高いと仮定