Splay tree
Program
Overview
Splay treeは直近にアクセスした要素に素早く再アクセスできるという特徴がある平衡二分探索木である。
その特徴から、キャッシュ機構やシンボルテーブル等、参照の局所性があるものと相性がよい。また、AVL等の平衡二分探索木に比べて実装が容易である。
各操作の度に、対象データが根に移動しつつ平衡する様子が観察できる。
Notes
このデータ構造は師が作ったプログラミング言語のシンボルテーブルで採用されているのを読んではじめて知った。
最初期のParenでも、シンボルテーブルの実装に採用したことがある。ハッシュテーブルの方がよい性能がでたため現在は使用されていない。
当時は時間の半分程度をシンボルテーブルの探索に費やしており、「シンボルを探索するプログラムかい？」などと笑われていた。
現在は関数内のマクロをインラインに展開するなどして多少は改善されている。
こういう訳で、思い入れのあるデータ構造である。