Skewed Binary Search Trees

平衡しない二分探索木は、平衡した二分探索木より平均深さが深くて、
そのために平均の枝をたどる数が多く、
探索により長い時間がかかる、というのが伝統的な見解。

この論文は、右の子の数と左の子の数を一定比率にした、”一般化平衡二分探索木”のようなものを定義し、
右をたどる時間と左をたどる時間が異なっているとしたときに、最適な子の数の比率が与えられることを示した。

「右にいくのと左にいくのに時間が違うようなことがあるのか」というのが疑問に思われるけれど、
キャッシュミスの比率が違うという説をだし、それを実験的・理論的に示している。

実験設定は、二分探索木を深さ優先探索で線形化（配列化）してやり、
そこにランダムな検索をかける、というもの。

「なんでそれで速くなるんだろうね」「この辺が割と(シーケンシャルな|繰り返しの多い)アクセスをやってるので、キャッシュが効いてるんだと思う」

という議論なら割と自明にキャッシュが効くことが分かるけれど、
このような設定でキャッシュが有効になるのはあまり自明ではない（と思う）し、
標準的な計算モデルにのっとった形で理論的に示し、実験的にも確かめたという点が素晴らしいのではないかと。

線形化することのメリットは、今までは、
・平衡していれば、左・右ポインタが不要で必要な領域は1/3
ということだけだったけれど、
これからは、
・平衡から少し偏らせることで、少しだけ速くなるかも
ただし、左と右が整数比にとれなければ、領域は減らない