Link-Cut Treeについてのメモです。
回転操作を行っても、左右の位置関係の情報は失われない
最初は、回転操作を行うと左右の位置関係の情報は失われると思っていました。Link-Cut Treeの仕組みの理解を妨げていた最大の誤解です。平衡二分探索木で回転操作を行っても、左右の位置関係の情報は失われません。図で表すと以下のような感じです。
このように、3を根とするように回転操作を行っても「3の左側の子孫は必ず3より小さく右側の子孫は必ず3より大きい」という状態は保たれます。以下のような状態になることはありません。
この誤解がなくなることで、回転やスプレー操作のコードがすんなりと理解できるようになりました。
スプレー木の根が、Light-edgeの親の情報を持つ
たとえば元の木と分解後の木が以下の図であったとします。
このとき、元の木の頂点2の子は頂点3ですが、分解後に頂点2への参照を持っているのは、頂点3が属するスプレー木の根である頂点5です。
感覚的には、頂点3が頂点2への参照を持たないことに違和感を覚えます。しかし、スプレー木には「最も左にある頂点（今回の場合は頂点3）が元の木の根もしくはLight-edgeの子」というルールがあるため、頂点3は頂点2への参照を持つ必要がないのです。
スプレー木の根がLight-edgeの親への参照を持つことで実装が楽になるという利点も得られます。このあたりの実装はexposeという名前の関数に書かれていると思います。解説を参考にしながらexposeのコードを読むと本当に面白いです。Heavy-edgeの追加と削除がスムーズに行われます。
パスの途中がLight-edgeになることもあり得る
たとえば以下の図を考えたとき、頂点3と頂点5の間の辺は中途半端な位置にありますが、この辺がLight-edgeになることも十分ありえます。HL分解を学んだ後とかだと、この点を勘違いしてしまうかもしれません。
expose(3)といったことをすると、上図のように頂点3と頂点5の間の辺がLight-edgeになります。極端にいうと、以下の状態もありえます。
Heavy-edgeが1本もありません。こういった状態は、根から遠い順にexposeを呼び出すことで作れます（嘘書いてるかもしれないです）。
一旦終わり
まだ書きたいことがあるような気がしますが、疲れたので一旦ここで終わります。明日また何か追記するかもしれません。「実際に問題を解くときにLink-Cut Treeを使う」という視点ではまだ考えられていないので、明日はその辺りのことを考察してみようと思います。気付いたことがあれば追記します。
参考
どのページも丁寧に作られていて凄いです。
