Skewed Binary Search Trees

Gerth S. Brodal and Gabriel Moruz
Proc. ESA 2006, pp. 708-719
doi:10.1007/11841036_63

今日の勉強会で紹介したら好評だったので，ここでも紹介．

二分探索木は左側と右側がバランスするように構成すると探索時間が短くなる，と思ったら，実はそうでもなかった，という話．
ある程度アンバランスにした方が探索時間が実際短くなり，その理由として，左部分木をたどるコストと右部分木をたどるコストが違うというモデルを提案している．コストが異なるようになる理由は分岐予測ミスやキャッシュミス，命令数の違いというものが挙げられている．
言われてみれば当たり前のような気もするが，言われなければ全然気づかないことで，とても面白いと感じた．