最下位共通先祖問題と MF 木＊＊ここで理解すべき内容＊＊抽象データ型データ構造計算量評価方法

最下位共通先祖問題と 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

点 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 }

点 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 に戻った木 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 }

点 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 }

点 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 木との関連点 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 木と均し計算量の説明をした．また，アルゴリズムの解析と実現についても触れた．
アルゴリズムが与えられたとき，ここで述べたような手順でデータ構造を構築できれば，単位を修得！！

最下位共通先祖問題と MF 木＊＊ここで理解すべき内容＊＊抽象データ型データ構造計算量評価方法

Similar presentations

Presentation on theme: "最下位共通先祖問題と MF 木＊＊ここで理解すべき内容＊＊抽象データ型データ構造計算量評価方法"— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

最下位共通先祖問題と MF 木 ＊＊ ここで理解すべき内容 ＊＊ 抽象データ型 データ構造 計算量評価方法

Similar presentations

Presentation on theme: "最下位共通先祖問題と MF 木 ＊＊ ここで理解すべき内容 ＊＊ 抽象データ型 データ構造 計算量評価方法"— Presentation transcript:

Similar presentations

About project

フィードバック

最下位共通先祖問題と MF 木＊＊ここで理解すべき内容＊＊抽象データ型データ構造計算量評価方法

Presentation on theme: "最下位共通先祖問題と MF 木＊＊ここで理解すべき内容＊＊抽象データ型データ構造計算量評価方法"— Presentation transcript: