treeに触れる機会があったので、自身の理解のためにまとめをば。findを行うときにsplayと呼ばれる操作を行うことが特徴。zig-zagという操作を繰り返し、指定したキーを持つノードをrootに持ってくる。splayにより左右の木のバランスを自動で(自己的に)改善することができる。deleteといった操作は簡単に実装できる。Treeの実装こちらがとてもわかりやすい。splay操作の実装として’bottom-up’と’top-down’方式があるよう。splayを理解するには’bottom-up’の方がわかりやすく、実際の実装では’top-down’の方が書きやすいかなという印象。二分木としての操作はsplayを使用して以下のように行う。searchsplay操作を行い、指定したキーを持つノードをrootに持ってくる。指定したキーを持つノードが無い場合も最後にアクセスしたノードをrootに持ってくる。insertinsert対象のキーを持つノードが二分木に存在するかをsearchで確認する(つまりsplayする)。存在しなければrootとして追加する。removeremove対象のキーを持つノードが二分木に存在するかをsearchで確認する(つまりsplayする)。存在すればrootのノードを削除する(search後には目的のノードがrootに来ている)。存在する子ノードをrootにする。左の子に対してremove対象のキーでsplayし、そのrootを木全体のrootにする。remove対象のキーが左の子をrootとする部分木のどのノードよりも大きいことを利用している。zig-zag周りの動きがコードからだけではうまくイメージできなかったので実際に動かして確認をしてみることにする。splayの実装としてこちらのbottom-upを想定しており、途中の変数名等もここから引用している。0を対象にsplayした場合を考える。0をrootに持ってくる。zig-zigを行うノードの順番に注意。4実際に以下のPythonコードを用意して上の動作を確認する。")出力結果は以下の通りで想定した動きになっている。2を対象にsplayした場合を考える。1、node3の順にzig-zagの動作を行う。7zig-zag分の出力コードは以下の通り。")実際の出力は以下の通りで動きが確認できている。tree実装を用意し、splayの効果を確認してみる。treeの実行時間の評価に関しては既に何度も参考にしているこちらで評価されているので、ここでは木の左右のバランス具合を見てみることにする。二分木のバランスを見るのにベストな指標はわからないけれど、木の最大深度を確認するのが少なくとも一番手っ取り早いと考え、上記二分木にノード個数を数えるcountメソッド、最大深度を測定するmax_levelメソッドを実装し比較してみる。measure_nd()上で使用しているrandint_nd関数の実装は以下の通り。nums.tolist()出力結果は以下の通り。30結果としてあまり思ったような結果が出ていない。treeの実装に誤りがある使用しているデータが不適切かなと。treeの実装をそのまま試しても同様な結果だったのでとりあえず可能性として除外する。2.に関してはそもそも使用するデータがランダムであれば二分木は何もしなくてもバランスが取れるよね、ということ。順序の整ったデータを渡せばそりゃ差はできる(measure_ordered関数の例)けど、それも比較としてはね...という感じ。苦し紛れに擬似的に正規分布状の分布をとるような整数値を与えるランダム関数(randint_nd)を定義し、使用してみたけれど結果は変わらず。Wikipediaの「スプレー木」項目には一様なアクセスが発生するような場合、スプレー木は単純な平衡2分探索木よりもずっと性能が悪くなる。いう記述があるので、スプレー木は「キャッシュ化して効果を発揮するようなデータ」に対して構築するのがベターということだけど、そういったデータが手元にないので試してみることはできない...splayの最大のメリットは頻繁にアクセスするノードが木の上部に集まりやすいということであり、木の左右のバランスが調整されるのは副次的な効果という感じに捉えるのがいいのかもしれない。