アルゴリズムとデータ構造 5月27日分 情報知能学科 白井英俊 木構造 根つき木、もしくは木構造 (1) 頂点と辺とから作られる 頂点： vertex, node, ノード、節点、… 辺： edge, arc, アーク、枝、… 木はグラフの一種。 頂点は 、辺は や で表す (2) 根(root) という特別な頂点がただ一つある 木とグラフの違い 木： v0 が根。根からはど の頂点へも枝をたどってい ける。同じ頂点への複数の パスはない。 グラフ： 『根』のような特殊な 頂点はない。v0 からv4へは、 v1を通っても、v2を通ってもい ける(複数のパスがある）。 v0 v1 v3 v2 v4 v5 v7 v1 v6 v8 v0 v2 v3 v4 v5 v6 木の用語 v0 • 親と子 (例： v1とv4) v1 2つの頂点が結ばれていると v2 き、上の頂点を親(parent)、 下の頂点を子(son)、という v4 v5 • 兄弟(例：v4とv5) 同じ親を持つ子頂点同士を 兄 弟(brother)、という v7 v3 v6 v8 •最も左の子を、第一子(first child)という ( 例： v1の第一子は v4、v5の第一子はv7 ) •右隣の兄弟を、次の兄弟(next brother)、という( 例： v1の次 の兄弟はv2、v2の次の兄弟はv3 ) •葉（leaf): 子を持たない頂点(例： v2, v3, v4, v7, …) 木の用語の確認 • 試験の頻出問題 v0 右の木の(1)根, (2)v5の兄弟の頂点 すべて、(3)v6の先祖の頂点すべて、 v1 v2 (4)v2の子孫の頂点すべて、(5)葉の v4 頂点すべて、を答えよ v5 v6 定義：頂点xの「先祖」とは、xの親頂 点すべて、およびxの親頂点の先 v9 祖すべて(再帰的な定義） 定義：頂点xの「子孫」とは、xの子頂 点すべて、およびxの子頂点の子 孫すべて(再帰的な定義） v3 v7 v8 v10 木の表現 • 線形リスト構造を、セル(の集まり）で表したよ うに、木構造を次のようなデータ構造（ノード と呼ぶ）で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end end @parent self @nextBrother @firstChild 木の表現(続) クラスNodeを図示すると、次のようになる 頂点 一個一個が以下の構造をもつ @parent 親頂点 label (ラベル） parent (親） self @nextBrother firstChild(第一子） nextBrother(次の兄弟） @firstChild 子頂点 兄弟頂点 前回の練習：木の表現 ラベル v0 v0 nil 親頂点 v1 第一子 nil 次の兄弟 ラベル v1 親頂点 第一子 次の兄弟 ラベル v4 親頂点 第一子 次の兄弟 nil v4 v2 v5 ラベル 親頂点 第一子 次の兄弟 v2 ラベル 親頂点 第一子 次の兄弟 v5 nil nil v3 v6 ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v3 v6 解答：木の表現 ラベル v0 v0 nil 親頂点 v1 第一子 nil 次の兄弟 ラベル v1 親頂点 第一子 次の兄弟 ラベル v4 親頂点 第一子 次の兄弟 nil v4 v2 v5 ラベル 親頂点 第一子 次の兄弟 v2 ラベル 親頂点 第一子 次の兄弟 v5 nil nil v3 v6 ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v3 nil nil v6 nil nil 練習:木の表現 ラベル v0 v0 nil 親頂点 v1 第一子 ラベル v1 親頂点 第一子 次の兄弟 ラベル v4 親頂点 第一子 次の兄弟 v4 nil 次の兄弟 nil nil ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v2 v5 v2 v5 nil v3 v6 ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v3 nil nil v6 nil nil 完成：木の表現 ラベル v0 v0 nil 親頂点 v1 第一子 ラベル v1 親頂点 第一子 次の兄弟 ラベル v4 親頂点 第一子 次の兄弟 v4 nil 次の兄弟 nil nil ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v2 v5 v2 v5 nil v3 v6 ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v3 nil nil v6 nil nil 木（ノード）のクラスの拡張 その前に前提知識：関数とメソッドの違い ユークリッドの互除法、配列に対するflat, depth、qsort, mergeなどの「関数」 は、たとえば def qsort(x) … end という形式で定義し、 ans = qsort([3,6,9,1,2]) という形式で使ってきた。 この時、仮引数xに実引数の値が渡され、計算が行われる それに対し、クラス定義の「メソッド」の使用の形式は ans = list.insert(2,newCell) のように 「オブジェクト.メソッド(…)」 という形式で使われる。 定義の形式は関数に似ているが、「インスタンス変数」とselfが中で使 える。この時、selfはオブジェクトの値、インスタンス変数はオブジェクト のインスタンス変数の値になる 木（ノード）のクラスの拡張 以下の「ノード」クラスにメソッドを付け加える (1)所与の頂点の祖先を列挙する、(2)所与の頂点の孫を列挙 する、(3) 所与の頂点に別な頂点を第１子として付け加える、 (4)所与の頂点の末っ子の頂点を返す,(5)所与の頂点の第１子 とその子孫を削除する class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end end @parent self @nextBrother @firstChild 木のクラスの拡張:children • 準備体操 所与の頂点の子頂点を列挙するメソッド children 考え方： 再帰？ 頂点vが持っている情報: 親, 次の兄弟, … すぐ見つかる子頂点は 第１子、つまり @firstChild 他の頂点は？ 木のクラスの拡張:children • 準備体操 所与の頂点の子頂点を列挙するメソッド children 考え方： 再帰？ 頂点vが持っている情報: 親, 次の兄弟, … すぐ見つかる子頂点は 第１子、つまり @firstChild 他の頂点は？ 第１子の兄弟たち これはchildrenとは無関係 だから「children」は(単純な)再帰ではない 木のクラスの拡張:children • それなら「兄弟たち」を返すメソッドを作ってみよう： brothers @parent • これを使えば 子どもたち(children)は、 self 第１子＋その兄弟たち @nextBrother でできる(もし第１子があれば) つまり、 @firstChild [@firstChild][email protected] 第１子から見 たnextBrother 木のクラスの拡張:brothers • 兄弟たち：brothers すぐ見つかる兄弟頂点は 次の兄弟、つまり @nextBrother もしも @nextBrother が存在し ない、つまり nil ならば 兄弟たちとして [ ]を返す @parent self @nextBrother @firstChild もしも @nextBrother が存在するなら… 再帰！ 兄弟たちとして @nextBrother.brothers を返す brothersとchildren class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end def children if @firstChild == nil return [ ] else return [@firstChild] + @firstChild.brothers end # if end # def of children def brothers if @nextBrother == nil return [ ] else return [@nextBrother] + @nextBrother.brothers end # if end # def 補助関数 nodeLabels • 頂点の配列を表示させると、以下のように表示 されて、ワケがわからなくなる [#<Node:0x808e6b8 @firstChild=#<Node:0x808e5f0 @firstChild=nil, @parent=#<Node:0x808e6b8 ...>, @label="d", @nextBrother=#<Node:0x808e5c8 @firstChild=nil, @parent=#<Node:0x808e6b8 ...>, @label="e", @nextBrother=nil>>, ... そこで、頂点の配列を入力とし、頂点のラベルの 配列を返す関数, nodeLabelsを用意した 上記を引数にすると、その結果は： [“x”, “y”] 作業課題 (5)までのヒントが教科書にある 以下のそれぞれをメソッドとして実現せよ (1)所与の頂点の祖先を列挙する ancestors (2)所与の頂点の孫を列挙する grandChildren (3) 所与の頂点に別な頂点を第１子として付け加 える adoptFirstChild (4)所与の頂点の末っ子の頂点を返す theYoungestChild (5)所与の頂点の第１子とその子孫を削除する removeFirstChild (6) 所与の頂点の子孫を列挙する descendants 作業課題をやるときの注意 • いきなりプログラムを書こうとしない！ • まずは問題を分析すること 最小の問題は何か？（頂点が与えられた時、すぐ に見つかる答えはどうやって得られるか？） 他の解をどうやって得るか？－－再帰が使えるか 、それとも繰り返しか？ ancestors の場合 theYoungestChild の場合
© Copyright 2024 ExpyDoc
