Link-Cut Treeの実装メモ

Link-Cut Tree(Link-Cut 木)を実装したのでそのメモみたいなもの

以下のスライドを主に参考にして実装している

プログラミングコンテストでのデータ構造 2　～動的木編～ from Takuya Akiba

www.slideshare.net

今回はとりあえず理解した(はずの)Link-Cut Treeの振る舞いのメモを書いておく。(クエリ処理まわりの話は含まない)

Link-Cut Treeとは

動的木の１つ。頂点、木の追加削除を行いながらクエリ処理を行うことができる。

HL分解(Heavy-Light Decomposition)のように、パスで木を分割して管理し、必要に応じてパスの変形を行う。そして、木に対する更新処理やクエリ処理をsplay-treeを使うことで 計算量 で行えるデータ構造である。

例えば、以下の頂点1が根頂点である根付き木を考える。今回はこの木を用いて説明する。(今回は左に90度回転させたほうが分かりやすそうなので回転させてる)

まず、この木をパスで分割する(これはHL分解っぽい)。

この中の各パスをLink-Cut Treeでは平衡二分探索木(Balanced BST)を用いて管理する。
BST上では、各頂点は根頂点からのパスの順番(= 根頂点からの距離)で順序が管理される。

例えば、今回の根付き木は下の図のように、いくつかのBSTに分けた構造で管理される。

分解後のパスに含まれない辺(上図の破線)は切断されており、構造的には子頂点が親頂点へのリンクを持つだけになる。
例えば、上のLink-Cut Treeの頂点5は、頂点3と頂点8へのリンクを持つが、頂点10へのリンクは持たない。逆に、頂点10は親頂点5へのリンクを持つ。

前提知識: splay-tree

平衡２分探索木の１つ。参照した要素に対してsplay操作(特定の木の要素を、回転することでrootに持ってくる処理)を行うことで平衡を保つ。要素の追加・参照・削除の計算量はならし になる。

要素6を参照し、splay操作を行う例

Link-Cut Tree上の操作

Link-Cut Treeでは、以下の操作が行える。

• expose(v): 根頂点から頂点のパス上の辺を全て繋げる
• link(v, w): 頂点と頂点の間に辺を追加
• cut(v): 頂点と頂点の親頂点の間の辺を除去
• evert(v): 木を頂点を親とする根付き木に変更

splay操作

expose操作内では、splay操作が使われる。
Link-Cut Treeにおけるsplay操作は、splay-treeにおけるsplayと基本同じである。
splay-treeとの違いは、Link-Cut Tree上のsplay操作は、木のパスとして繋がっている頂点のみを対象とする点である。 (パスの間で切れていれば、それ以降の頂点は対象にしない)。
(例えば、今回の例のLink-Cut Treeで頂点9に対しsplay操作を行う場合、このsplay操作に関係する頂点は4,9,14のみになる)

expose操作

expose(v)は根頂点から頂点のパス上の辺を全て繋げる操作である。
例えば、根頂点1から頂点15まで繋がっている状態で、頂点9に対してexpose操作を行う図が以下である。

元の根付き木において頂点9に対してexpose操作を行う前と後の図

# 頂点i (1-indexed)に対してexpose操作を適用
def expose(i):
    p = 0   # 一つ前のBSTの親頂点 (p = 0はNULL)
    cur = i # 現在のBSTの中でsplay操作で根頂点とする頂点cur

    while cur:
        splay(cur)      # (操作a) 頂点curに対しsplay操作
        right[cur] = p  # (操作b) 頂点curに頂点pを繋ぐ
        p = cur         # 現在の頂点curを次の頂点pとする
        cur = prt[cur]  # 次の頂点curは頂点curの親頂点

    splay(i) # (操作c) 最後に頂点iに対してsplay操作
    return i

例えば、例のLink-Cut Treeの状態から頂点12に対してexpose操作を行い、根頂点1と頂点12間をパスで繋いだ状態にする例を図でステップごとに示す。

expose操作を行う前のLink-Cut Tree (根頂点1から頂点15のパスまで繋がっている図)

はじめは頂点12に対しsplay操作を行い(操作a)、頂点12とNULLを繋ぐ(操作b)ことで、元の根付き木で頂点12が持つ子頂点との辺を切る処理を行うが、今回はそのような頂点が存在しないため、この例では省略。

(操作a) 頂点12の親頂点である頂点9に対しsplay操作を行う

(操作b) 頂点9と頂点12を繋ぐ (同時に頂点14が切れる)

(操作a) 頂点9の親頂点である頂点3に対しsplay操作を行う

(操作b) 頂点3と頂点9を繋ぐ (同時に頂点15が切れる)

(操作c) 最後に頂点1に対しsplay操作を行い、完了

link操作

元の根付き木の頂点pの子として新たな木を追加したい場合、頂点pと、繋ぐ木に含まれる1つの頂点iに対してexpose操作を行い、BST上で頂点iの右部分木として頂点pを接続すればよい。

# 頂点pを親頂点として頂点pと頂点iを繋ぐ
def link(i, p):
    expose(i) # 頂点iに対してexpose操作
    expose(p) # 頂点pに対してexpose操作
    prt[i] = p   # 頂点iの親頂点を頂点pに
    right[p] = i # 頂点pの右の子頂点として頂点iを接続

頂点12の下にパス16-17-18を接続する例 (上の説明におけるi = 12, p = 17)

cut操作

元の根付き木において、頂点iとその親の頂点pの間の辺を切って２つの木にしたい場合、頂点iに対してexpose操作を行い(これにより、BSTの頂点iの左部分木に、根頂点と頂点iの間のパス上にある頂点が集まる)、BSTの頂点iの左の子頂点とのリンクを切ればよい。

def cut(i):
    expose(i)
    p = left[i]
    left[i] = prt[p] = 0
    return p

以下の図は、はじめのLink-Cut Treeに対して頂点4とその親の頂点3の間の辺を切る例である。

頂点4に対してexpose操作を行う

頂点4とその親の頂点の間の辺を切る

evert操作

元の木上で、頂点iを新たに根頂点にしたい場合、頂点iに対してevert操作を行う。

頂点5に対してevert操作を行う例

def evert(i):
    # 頂点iに対してexpose操作
    expose(i)
    # 頂点iの子頂点をswap
    swap(i)
    # swapが遅延されていればswapを伝搬する
    rev[i] and prop(i)

以下の例は頂点3に対してevert操作を行った場合の例である。一度頂点3に対してexpose操作を行った上でswap(ここでは分かりやすさのために一括swap)を行う。

頂点3に対してexpose操作

頂点3を含むBST (= 根頂点1から頂点3までのパス)をswap

swapする対象の頂点は、根頂点からのパス上の頂点数分になるため、一括でやるのは難しい。そこで、各頂点にswapを遅延させている状態の値を持たせ、splay操作する際に遅延状態であればswapするようにする。

Link-Cut Treeの実装

• ライブラリ実装

Python3実装: Link-Cut Tree - yaketake08's 実装メモ
C++実装: Link-Cut Tree - yaketake08's 実装メモ

• AOJ: "GRL_5_D: Tree - Range Query on a Tree"

Python3: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3227821#1
C++14: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3227998#1