Splay Treeの可視化Webページを簡易的に作った - 日々ｄｒｄｒする人のメモ

この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。

adventar.org

今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。

はじめに
Splay Treeとは?
- bottom-up
- top-down
visualizationの実装
参考

はじめに

最近、Splay Treeがぬるぬる動く様子を眺めて癒やされたい(?)、という気持ちになり自作したくなったのでさくっと作りました。
作成期間はこのアドベントカレンダー記事を書こうとしてからの直近1週間です。

Splay Treeとは?

スプレー木 - Wikipedia
Splay tree - Wikipedia

平衝二分探索木の1つであり、参照したノードを回転しながらrootに持ってくるsplay操作によって平衝を保つ。
splay操作では zig, zig-zig, zig-zag の操作を組み合わせて行う。

Splay Tree上の操作はならし計算量で1回あたり $O(\log N)$ になる。

Splay Treeの操作実現方法としてbottom-up方式とtop-down方式がある。

bottom-up

目的のノードまで探索してからrootに向かってsplay操作を行う。
各操作は以下のイメージのように行う。

zig step

下図のノードyがrootの場合の操作

f:id:smijake3:20191204214713p:plain:w320 — zig stepのイメージ

zig-zig step

f:id:smijake3:20191204214859p:plain:w320 — zig-zig stepのイメージ

zig-zag step

f:id:smijake3:20191204214802p:plain:w320 — zig-zag stepのイメージ

top-down

rootから目的のノードまで探索するのに合わせ、splay操作も行う。
splay操作中は3つの木を持ち、現在探索している木(middle tree)の他に探索対象のkey $X$ より小さいノードを含む木(left tree)と大きいノードを含む木(right tree)を管理する。
そして、木に含まれるノードをkey $X$ との大小の関係から2つの木(left tree, right tree)に移動させ、最後に3つの木をマージして完了させる。

各操作と最後のマージは以下のイメージのように行う。

zig step

子ノード(下図のy)が参照するノードの場合の操作

f:id:smijake3:20191204205900p:plain:w480 — zig stepのイメージ

zig-zig step

f:id:smijake3:20191204210119p:plain:w480 — zig-zig stepのイメージ

zig-zag step

f:id:smijake3:20191204210200p:plain:w480 — zig-zag stepのイメージ

最後のマージ

middle treeの根ノードと左右ノードの間にleft tree, right treeを差し込む感じでマージする。

f:id:smijake3:20191205001608p:plain:w480 — 3つの木のマージのイメージ

visualizationの実装

ぬるぬる動くようにしたいのですが自前で動きをつけるのはめっちゃ面倒なので、アニメーションを実現できるJavaScriptライブラリを使うことにしました。

今回は anime.js を使いました。
animejs.com

各アニメーションは、移動後の座標と移動時間を設定するだけで動いてくれるので記述が楽でした。
また、Timelineを用いて連続したアニメーションを簡単に記述できたのもよさげでした。

// tl = anime.timeline()
function translate_obj(result, tl) {
  tl.add({ // 各ノードのアニメーション設定 (svgのgタグ)
    targets: ['g.node'],
    translateX: (el) => {
      // 移動後のX座標を返す
    },
    translateY: (el) => {
      // 移動後のY座標を返す
    },
    duration: 1000, // 移動にかける時間
    easing: 'linear',
  }).add({ // 各辺のアニメーション設定 (svgのpathタグ)
    targets: ['path.edge-l', 'path.edge-r'],
    d: [{value: function(el) {
      // 辺の始点(A, B)と終点(C, D)を "M<A>,<B>L<C>,<D>" という形式で返す
    }}],
    offset: '-=1000', // 直前のノードのアニメーションの開始時刻と合わせる
    duration: 1000,
    easing: 'linear',
  });
}