スプレー木 - Wikipedia

http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%97%E3%83%AC%E3%83%BC%E6%9C%A8
http://en.wikipedia.org/wiki/Splay_tree

スプレー木（スプレーき、英: Splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。

Chapter 22 Splay Trees

http://digital.cs.usu.edu/~allan/DS/Notes/Ch22.pdf

The Basic Bottom-Up Splay Tree
Top-Down Splay Trees

[プログラミング] Google Sparsehashを使うときの注意点 - tsubosakaの日記

http://d.hatena.ne.jp/tsubosaka/20100302/1267541850

持橋さんの書かれたgoogle-sparsehashと自作のsplay-treeとの速度比較をした結果の記事を読んで、さすがに速度に200倍近くの差がでるのはおかしいだろうということで原因を探ってみた。