http://www.cepis.org/upgrade/files/full-2004-V.pdf
Dominique A. Heger. A Disquisition on The Performance Behaviour of Binary Search Tree Data Structures. UPGRADE, 5(5):67-75, 2004.
「Treapは遅いけど実装が容易」という話をいろいろなところで読んだのでそういうものかと思っていたが、この報告だとむしろいちばん速いように見える。
でも、赤黒木より速いならなぜ各種言語の標準ライブラリで使われないのかという話にもなるし、どう考えればいいのかわからない。乱択アルゴリズムは基本的に避けられがち、とかなんだろうか。
