Splay Tree

スプレー木についてのメモ

(1)普通のrotr, rotlを実装する

(2)
zig->そのまま
zigzig->親を回転,自分を回転
zigzag->自分を回転*2
でSplayを実装

(3)
merge->左の木のMaxをSplay,左の木のRootの右に右の木のRoot
split->k番目をSplay,そのまま分ける