最下位共通先祖問題と MF 木 ＊＊ ここで理解すべき内容 ＊＊ 抽象データ型 データ構造 計算量評価方法 　 ＊＊　ここで理解すべき内容　＊＊ 抽象データ型 Merge-Find 集合　（Union-Find 集合） データ構造 Merge-Find 木　（Merge-Find tree） 計算量評価方法 均し計算量　（amortized complexity）

例として考える問題 オフライン 　　最下位共通先祖 　　　　　　　　　　問題

オフライン最下位共通先祖問題 Off-line Lowest Common Ancestors Problem 入力： 出力： 　入力： 根付き木 T = (V,E) 点対の集合 P = { p=(v,w) | v, w は T の点 } 　出力： 各点対 p=(v,w)∈P に対する 　　　（木 T 上での）最下位共通先祖 anc(p)

最下位共通先祖 木 T 上の質問点対 p=(v,w) に対する 最下位共通先祖 anc(p) = a 木 T の点 a で，以下の性質を持つもの v と w の共通の先祖であり， a の真の子孫には v と w の共通の先祖が無い

オフライン最下位共通先祖問題 質問点対の集合 P P = { (c,h), (e,f), (f,g), (g,h) } 最下位共通先祖 木 T b d c e 最下位共通先祖 anc( (c,h) ) = b anc( (e,f) ) = e anc( (f,g) ) = b anc( (g,h) ) = d f a h g

オフライン（off-line）問題 オフライン（off-line）問題 オンライン（on-line）問題 全ての質問を予め知った上で 　 各質問に対する答えを求めるもの オンライン（on-line）問題 全質問を予め知ることができず， 　 質問毎に答えを出すもの

オフライン最下位共通先祖問題に対するアルゴリズム

アルゴリズム r v c c' 木 T を深さ優先探索（DFS）して求める． void DFS( v, T ) { 行きがけの処理 ; 　 行きがけの処理 ; c := lm_child(v) ; /* c を v の長男に */ while ( 子 c が存在する ) { 　　DFS( c, T ) ; 　　子 c の情報を利用する処理 ; 　　c := r_sibling( c ) ; /* c を次弟に */ 　 } 帰りがけの処理 ; } /* end DFS */ 帰りがけに，最下位共通先祖が求められる ? r v c c'

点 v からの帰りがけ時の検査 (v,w)∈P なる質問点対が存在し w は既に探索済みか？ もし，そうならば， 　　もし，そうならば， w の先祖で探索中の点の内， 最下位にある点 a は， v と w の最下位共通先祖 anc( (v,w) ) b d a e w v

必要な操作 1. 点 v を含む質問点対 (v,w) ∈P が存在するか否かの検査 2. もう一方の点 w は既に探索済みか否かの検査 これらを効率良く実行したい b d a e w v

必要な操作 1 点 v を含む質問点対 (v,w)∈P が存在するか否かの検査に対しては， 木 T の各点 v に対して， v を含む質問点対 p=(v,w) ∈ P の集合 P(v) = { p | p=(v,w)∈ P } 　　を覚えておく w w' v

必要な操作 2 b 点 v を含む質問点対 (v,w)∈P のもう一方の点 w が， 既に探索済みか否かの検査は d 点に a e w v 　 未探索 　 探索中 　 探索済み の印を付けておけば良い d a e w v

必要な操作 3 b d a e w v 点 w の探索中の先祖で， 最下位のもの a を求めるには， “探索中” の各点 a に対して， 　　集合 U(a) = { a }  { w, ・・・ } 　w は a の子孫で探策済み， 　w の先祖で a より下に探索中の点は無い 　　を覚える w ∈U(a) と現在探索中の点 v との 最下位共通先祖は a = anc( (v,w) ) U(a) の初期値は， U(a) = { a } とする d a e w v

アルゴリズムの例 集合 U(・) に対する操作

木 T と集合 U(・) および P(・) 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

木 T の深さ優先探索 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } 探索中 C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T 探索中 b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

木 T の深さ優先探索 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T 探索中 b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

木 T の深さ優先探索 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

木 T の深さ優先探索 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 g の探索終了： P(g) の検査 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g f, h は未探索 ⇒　何もしない 探索済

点 g から戻る： A と G の併合 木 T b d c e f a h g A = U(a) = { a } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T A = U(a) = { a, g } b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 a に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 a の探索終了： P(a) は空 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 a から戻る ： A と D を併合 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { d } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T D = U(d) = { a, d, g } b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 d に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 h を深さ優先探索 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 h の探索終了： P(h) の検査 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g g は探索済み ⇒　anc((g,h)) は?

点 g を含む集合 U(・) の探索 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g g ∈ U(d) ⇒　anc((g,h)) = d

点 h から戻る ： H と D を併合 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T D = U(d) = { a, d, g, h } b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 d に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 d から戻る 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { b } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g P(d) は空 ⇒　B と D を併合

点 b に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 c を深さ優先探索 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 c の探索終了： P(c) の検査 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T h を含む U(・) は? ⇒　anc((c,h)) = b b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g h は探索済み ⇒　anc((c,h)) は?

点 c から戻る ： C と B を併合 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 b に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 e, f へ深さ優先探索 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 f の探索終了 ： P(f) の検査 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T g を含む U(・) は? ⇒　anc((f,g)) = b b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g g は探索済み ⇒　anc((f,g)) は?

点 f から戻る ： F と E の併合 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 e に戻った 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e, f } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

点 e の探索終了 木 T b d c e f a h g A = U(a) = { a, g } f を含む U(・) は? B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e, f } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T f を含む U(・) は? ⇒　anc((e,f)) = e b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g f は探索済み ⇒　anc((e,f)) は?

点 e から戻る ： E と B の併合 木 T b d c e f a h g A = U(a) = { a, g } B = U(b) = { a, b, c, d, g, h } C = U(c) = { c } D = U(d) = { a, d, g, h } E = U(e) = { e, f } F = U(f) = { f } G = U(g) = { g } H = U(h) = { h } 木 T b d c e f a h P(c) = { (c,h) } P(e) = { (e,f) } P(f) = { (e,f), (f,g) } P(g) = { (f,g), (g,h) } P(h) = { (c,h), (g,h) } g

根 b に戻り 全探索終了 木 T b b d c e f a h g B = U(b) = { a, b, c, d, e, f, g, h } b b d c e f a h 全探索終了 g

アルゴリズムの記述と 計算量 深さ優先探索の再帰的記述

アルゴリズムの概要 void DFS( v, T ) /* 再帰的関数 */ 入力： v : NODE（値呼び） T : 木 　　 P(v) ：　v を含む質問点対の集合 　　出力： anc(p) : 各質問点対 p に対する 最下位共通先祖 　　NODE 　 c /* 局所変数 */ 　　各点 v に対して，未探索の印しを付けておき， 　　 集合 U(v) の初期化 U(v) = { v } を行って， 　　 関数 DFS( 木 T の根，T ) を呼ぶ．

アルゴリズムの概要 実は不要 Merge( ) Find( ) void DFS( v, T ) { v に探索中の印を付ける ; c := lm_child(v) ; while ( 子 c が存在する ) { 　　DFS( c, T ) ; 　　U(c) を U(v) に併合する ; 　 　　c := r_sibling( c ) ;　　　 　　 } for ( 各 p=(v,w)∈P(v) ) { 　　if ( 点 w は探索済み ) { 点 w を含む U(a) を求める ; 　　 }　　 } v に探索済みの印を付ける ; } /* end DFS */ 実は不要 Merge( ) Find( )

集合 U(・) に対する操作 指定された点 w を含む集合 U(a) を見出す Find( w ) 計算量を O(TF) と書く 点 a は点 v と w の最下位共通先祖 集合 U(v) と U(c) を併合し，U(v) とする Merge( U(c), U(v), U(v) ) 計算量を O(TM) と書く

アルゴリズムの計算量 どの点も高々 1 回しか訪問しない 各点における操作 全 Merge 回数： n-1 回 （n ： 点の個数） 点 v に関する下記の操作は 1 回しか実行しない 各点における操作 Merge の操作 質問点対があれば，Find の操作 子を順に探索するための操作 全 Merge 回数：　n-1 回　（n ： 点の個数） 全 Find 回数：　　 m 回　（m ： 質問点対の個数） 全計算量 O( 全 Merge の計算量 + 全 Find の計算量 + その他 ) = O( (n-1)・TM + m・TF + n )

Merge-Find 集合とMerge-Find 木 効率的なデータ構造

Merge-Find 集合 （MF set） 以下の操作を持った抽象データ型 Merge( A, B, C ) Find( x ) C := A∪B とする手続き． 　A∩B=φなる集合 A, B に対する Union( A, B, C ) と同じ． Find( x ) 要素 x を含む集合を返す関数． Initialize( A, a ) 要素 a だけから成る集合 A を作る手続き

Merge-Find 木 MF 木 U a c e f g h b MF 木 U ・ 各集合を根付き木で表現 ・ 根には集合名を覚える B = { a, b, d, g, h } C = { c } E = { e } F = { f } B C E F a c e f g h b MF 木 U 　・ 各集合を根付き木で表現 　・ 根には集合名を覚える 　・ 各点は親へのポインタを持つ d ＊ ： 集合名 ＊ ： 要素

Merge( C, E, C ) MF 木 U c e a c e f C = { c, e } g h b d B = { a, b, d, g, h } C = { c } E = { e } F = { f } c e C B C E F a c e f C = { c, e } g h b d Merge の計算量 ：　TM = O(1)

Find( d ) MF 木 U a a e f g g h b c MF 木 U の点 d から， 親を辿り，根まで到達すれば， B = { a, b, d, g, h } C = { c, e } F = { f } B B C F a a e f g g h b c MF 木 U の点 d から， 親を辿り，根まで到達すれば， そこには集合名が書かれている d d Find の計算量 ：　TM = O( 木の高さ h(・) )

? Merge( C, F, F ) c e f e f c F = { c, e, f } c f e F C F B = { a, b, d, g, h } C = { c, e } F = { f } e f c ? F = { c, e, f } c f e F Find の手間が小さくなるので， 好ましい

Merge 操作の改良 木の高さを抑える Find の効率化になる

Merge( A, B, C ) |A| > |B| a a b b C A B 要素数の少ない木の根を， もう一方の木の根の子にする 要素数が n の木の 高さは，常に O(logn) 各木の点の個数を覚えていれば，Merge の計算量　TM = O(1)

命題 点の個数の少ない方の木の根を， 個数が大きい方の木の根の子にするように Merge を行うと， 木の点の個数を n とすると， 　　できた木の高さ h(・) は高々

数学的帰納法で証明 ， n = 1 のとき，木の高さ h(・) は 0 であり， であるから， n = 1 のとき成立する． n < n’ のとき成立を仮定し，n = n’ の時を考える． n = n’ の木が，Merge( A, B, C ) でできたとすると， |A| < n, |B| < n であるから，帰納法の仮定より， A, B の高さ h(A), h(B) は ，

数学的帰納法で証明 一方，木 C の高さ h(C) は， h(C) = max[ h(A), h(B)+1 ] であるから， a b 一般性を失うことなく， |A|  |B| と仮定できる． C a h(A) b A h(B) B Q.E.D.

木の高さを抑える 後の Find の効率化になる 均し計算量

Find の改良 最下位共通先祖のアルゴリズムの計算量 全 Find の計算量 O( m・logn ) の削減 　 O( (n-1)・TM + m・TF + n ) 　 = O( (n-1) + m・logn + n ) = O( m・logn + n ) 全 Find の計算量 O( m・logn ) の削減 道の圧縮（path compression）

Find の改良 （道の圧縮） Find の操作において辿った点を 全て木の根の子にする操作 c g x a b e f d a a g g Find(x) d x x

Find の改良 （道の圧縮） Find の最悪計算量 TF のオーダは変化なし a a a g g b c x g b c c e f d Find(x) d e f d x x

Find の改良 （道の圧縮） しかし，全 Find 操作に要する総計算量 O(m・TF) は O(m・logn) から O(m・α(n) ) になる ここで， α(n) はアッカーマン（Ackerman）　　関数の逆関数

Ackermann’s Function アッカーマン関数

アッカーマン関数の逆関数 pseudo-inverse function of Ackermann’s function

アッカーマン関数の逆関数 アッカーマン（Ackerman）関数の逆関数 α(n) は n < 216 なる n に対して， α(n) ≦ 3 216 ≦ n <　265,536　　　なる n に対して， α(n) = 4　なので 実用上，定数 O(1) と考えても良い．

均し計算量 均し計算量（amortized time complexity） ある操作 A の均し計算量とは， A が何回か繰返された時，

均し計算量 MF 木の Find 操作に関しては， Merge と Find がどのような順序で行われても， m 回の Find に要する総計算量は，高々 O( m・α(n) ) なので， Find １回当たりの計算量（均し計算量）は O(α(n) )

均し計算量 最下位共通先祖を求めるアルゴリズムを 効率化するには， Find の最悪計算量を小さくするのではなく 最下位共通先祖を求めるアルゴリズムを　　効率化するには， Find の最悪計算量を小さくするのではなく 全 Find に要する総計算量を 小さくしなければならない すなわち，Find の均し計算量を小さくすれば良い

均し計算量 最悪計算量を小さくするデータ構造は， しばしば，複雑で，実際の計算時間が長い 最悪計算量を小さくするデータ構造は，　　しばしば，複雑で，実際の計算時間が長い 均し計算量を小さくするデータ構造は，　　単純で，実際の計算時間も小さくなる 　ことが多い 　このため，均し計算量は，　 データ構造を考える上での重要な概念

最下位共通先祖問題に対するアルゴリズム実現用 データ構造の詳細 最下位共通先祖問題に対するアルゴリズム実現用

木 T に必要なデータ構造 集合 U(・) ： MF 木で実現する 木 T = (V,E) の各点 v∈V に対して Merge :　　集合名を指定する Find ：　　　要素名を指定する 木 T = (V,E) の各点 v∈V に対して lm_child(v) ： 　v の長男 r_sibling(v) ： 　v の次弟 mark(v) ：　　　　　　 未探索，探索中，探索済みの印 集合 P(v) ：　　　　　　v を含む質問点対の集合 集合 U(v) ：　　　　　　集合名 U(v) を持つ MF 木の根 MF点 MFnode(v) ：　 v を示す MF 木内の点

MF 木のデータ構造 MF 木の根が持つべきデータ MF 木の点が持つべきデータ set_name : その木が表す集合の名称 U(・) size ：　　　　その木に含まれる要素の個数 MF 木の点が持つべきデータ parent　:　その点の親（根まで辿れるように） set_name size parent MF 木の点用のセル

Merge-Find 木 MF 木 U a e f g h b c d U(b) U(c) U(f) U(b) U(c) U(f) ・ ・ 5 c 2 f 5 g h b c d 根には，集合名 U(v) の v だけを書いておく

木 T のデータ構造 各点 v∈V に対して lm_child(v) ： 長男のセルへのポインタ r_sibling(v) ： 次弟のセルへのポインタ mark(v) ： 未探索，探索中，探索済みの印 集合 P(v) ： 連結リストへのポインタ 集合 U(v) ： MF 木の根のセルへのポインタ MF点 MFnode(v) ：　MF 木内の点のセルへのポインタ mark U(・) lm_child 木 T の点用のセル r_sibling Mfnode(・) P(・)

木 T のデータ構造 木 T b d c e f a h g mark U LmC RSb Mfn P(・) c h ・ e f g

木 T と MF 木との関連 b d d c e f a h g g M U Mfn M U Mfn ・ ・ ・ ・ MF 木 g 1 a

木 T と MF 木との関連 点 a に戻った時点 b b a d d c e g f a h g ・ 2 a 1 MF 木 ・ ・ g 1 U Mfn ・ 点 a に戻った時点 M U Mfn ・ M U Mfn ・ M U Mfn ・ b b a M U Mfn ・ M U Mfn ・ M U Mfn ・ d d c e g M U Mfn ・ f a h ・ 2 a 1 MF 木 g ・ ・ g 1 d 1 f 1

木 T と MF 木との関連 点 a に戻った時点 d b b a d d c e g f a h g ・ 2 a 1 MF 木 ・ ・ g U Mfn ・ 点 a に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b b a M U Mfn ・ M U Mfn ・ M U Mfn ・ d d c e g M U Mfn ・ f a h ・ 2 a 1 MF 木 g ・ ・ g 1 d 1 f 1

木 T と MF 木との関連 点 d に戻った時点 d b a d c e g f a h g ・ d 3 a 2 MF 木 ・ ・ g 1 U Mfn ・ 点 d に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 3 a 2 MF 木 g ・ ・ g 1 d 1 f 1

木 T と MF 木との関連 点 d に戻った時点 d b a d c e g f a h g ・ d 3 a 1 MF 木 ・ ・ g 1 U Mfn ・ 点 d に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 3 a 1 MF 木 g ・ ・ g 1 d 1 f 1

木 T と MF 木との関連 点 d に戻った時点 d b a d c e g f a h g ・ d 3 a 1 MF 木 ・ ・ g 1 U Mfn ・ 点 d に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 3 a 1 MF 木 g ・ ・ g 1 d 1 f 1

木 T と MF 木との関連 点 h を深さ優先探索 d b a h d c e g f a h g ・ d 3 MF 木 ・ ・ g 1 U Mfn ・ 点 h を深さ優先探索 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ h M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 3 MF 木 g ・ ・ g 1 h 1 f 1

木 T と MF 木との関連 点 d に戻った時点 d b a h d c e g f a h g ・ d 4 3 MF 木 ・ ・ g 1 U Mfn ・ 点 d に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ h M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 4 3 MF 木 g ・ ・ g 1 h 1 f 1

木 T と MF 木との関連 点 d に戻った時点 d b a h d c e g f a h g ・ d 4 MF 木 ・ g 1 f 1 U Mfn ・ 点 d に戻った時点 d M U Mfn ・ M U Mfn ・ M U Mfn ・ b a M U Mfn ・ M U Mfn ・ h M U Mfn ・ d c e g M U Mfn ・ f a h ・ d 4 MF 木 g ・ g 1 f 1

まとめ オフライン最下位共通先祖問題を例に， MF 木と均し計算量の説明をした． また，アルゴリズムの解析と実現についても触れた． アルゴリズムが与えられたとき，ここで述べたような手順でデータ構造を構築できれば，単位を修得！！