アルゴリズムとデータ構造

アルゴリズムとデータ構造

第6週 木の構造、木の走査、二分木、決定木

2014年10月30日 金岡 晃

授業計画

第1週 (9/25)

データ構造とアルゴリズムの基 礎

第2週 (10/2)

アルゴリズムの効率、線型構造、

スタックと待ち行列 第3週

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列 第4週

(10/16)

文字列照合（KMP法、BM法）

＋＜演習＞

第5週 (10/23)

休講 第6週

(10/30)

木の構造、木の走査、二分木、

決定木 第7週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木

第9週 (11/27)

休講 第10週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第11週 (12/11)

データ整列：ヒープソート 法、クイックソート法

第12週 (12/18)

＜演習＞データ整列：ヒー プソート法、クイックソー ト法

第13週 (1/8)

データ探索：ハッシュ法、

木構造探索法 第14週

(1/15)

＜演習＞データ探索：ハッ シュ法、木構造探索法

1/21-2/6 期末試験

第 2 回課題の解説

2014/10/30 アルゴリズムとデータ構造

2

演習（その

）

ハノイの塔を解く ハノイの塔を解く

演習：ハノイの塔を解くプログラムを実装してみよう

入力：積木の数, 最初のピンの位置（1, 2, 3のいずれか）, 最後のピンの位 置（1, 2, 3のいずれか）

出力：目的の状態に至るまでの状態と動作（move）の内容の列挙

演習（その

）

2014/10/30 アルゴリズムとデータ構造

4

フィボナッチ数列 フィボナッチ数列

演習：フィボナッチ数列を表示するプログラムを実装してみよう 入力：数列の長さ

出力：数列の長さまでのフィボナッチ数列の表示

第 4 週【復習】

文字列照合（ KMP 法）

アルゴリズムとデータ構造

文字列照合問題

2014/10/30 アルゴリズムとデータ構造

6

…… …… ……

1 s s+m-1 n

文字列 text

パターン pat ……

入力済みの文章（文字列、テキスト）から、照合した い単語（パターン）を探し出す処理

文字列照合（文字列パターンマッチング）

文字列照合（文字列パターンマッチング）

文字列中の各文字を text[1], text[2],…,text[n]

パターン中の各文字をpat[1], pat[2],…,pat[m]と表す

1 m

単純照合法

text pat

１．テキストの先頭にパターンの先頭を合わせる ２．パターンの先頭から文字を比較していく

４．パターンの先頭から文字を比較していく

３．異なる文字が現れた場合、パターンを1文 字文後ろへシフトする

KMP

法

2014/10/30 アルゴリズムとデータ構造

8

Knuth-Morris-Pratt法（KMP法）

Knuth-Morris-Pratt法（KMP法）

先頭から照合をしていく場合、照合失敗後のシフト量と 照合開始位置をあらかじめパターンから計算をしておき、

照合を行っていく

アルゴリズムの流れ

パターンpat[1..n]より

シフト量と照合開始位置を決める量 であるfail[1..n]を計算

failの計算

単純照合法と同様にパターンの先頭 から照合していくが、シフト量と照 合開始位置はfail[1..n]に従う

照合

注意

教科書P.83 のfail[i]の定 義式は見ないこと。記載 に矛盾があり混乱を招く。

パターンの先頭 i 文字を見て ここが照合失敗した場合に

何文字シフトするべきかを数える

KMP

法：

の導出と利用

failの導出（図解）

failの導出（図解）

パターンを用いて、パターン同士の照合を行い、シフト量を求める

pat A B B C B

fail[1] A ^1文字

iからシフト量を引いた数がfail[i]

fail[1]=1-1=0

fail[2] A B 1文字 fail[2]=2-1=1 fail[3] A B B 2文字 fail[3]=3-2=1 fail[4] A B B C 3文字 fail[4]=4-3=1 fail[5] A B B C B 4文字 fail[5]=5-4=1

• i番目で照合が失敗した場合、i-fail[i]だけ右にシフト

• 照合はpat[fail[i]]から開始する

KMP

法：

の導出と利用

2014/10/30 アルゴリズムとデータ構造

10

failの導出

（アルゴリズム）

failの導出

（アルゴリズム）

failの利用 failの利用

演習（その

）

KMP法による文字列照合 KMP法による文字列照合

演習：KMP法によるfailの導出を行うプログラムを作成してみよう 入力：文字列

出力：文字列の長さに応じたfail

締切は本日16:10 締切は本日16:10

第

週

文字列照合（

法）

木の構造、木の走査、二分木、決定木

アルゴリズムとデータ構造

12 ^2014/10/30 アルゴリズムとデータ構造

本日の到達目標と概要

•

到達目標

–

文字列照合のアルゴリズムを理解する

木の定義と様々な木を理解する

•

概要

–

文字列照合：

法

木の定義

–

多進木

木の走査

–

決定木（偽コインの問題）

BM

法

2014/10/30 アルゴリズムとデータ構造

14

Boyer-Moore法（BM法）

Boyer-Moore法（BM法）

末尾から照合をしていく場合の照合失敗後のシフト量を

あらかじめパターンから計算をしておき、照合を行っていく

アルゴリズムの流れ

パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算

shiftの計算

パターンの末尾から照合して いくが、照合失敗後のシフト 量はshift[1..m]とλ[1..Σ]に従う

照合

各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算

λの計算

BM

法：

の導出

shiftの導出（図解）

shiftの導出（図解）

パターンを用いて、パターン同士の照合を 行い、シフト量を求める

pat B A B B A B

パターンの末尾 i 文字目を見て ここが照合失敗した場合に

何文字シフトするべきかを数える shift[6] 1文字 shift[6]=1

shift[5] 2文字 shift[5]=2 shift[4] 5文字 shift[4]=5 shift[3] 3文字 shift[3]=3 shift[2] 3文字 shift[2]=3

B A B B A B B A B B A B B A B B A B B A B B A B B A B B A B

BM

法：

の導出

2014/10/30 アルゴリズムとデータ構造

16

shiftの導出

（アルゴリズム）

shiftの導出

（アルゴリズム）

BM

法：

と

の利用

アルゴリズムの流れ

パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算

shiftの計算

パターンの末尾から照合していくが 照合失敗後のシフト量は

照合を失敗したテキスト場所kの文字text[k]

パターンの場所をiとした場合、

shift[i]と(i- λ[text[k]) の大きい方の分だけシフトする

照合

各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算

λの計算

演習（その

）

2014/10/30 アルゴリズムとデータ構造

18

BM法による文字列照合 BM法による文字列照合

演習：BM法によるλとshiftの導出を行うプログラムを作成してみよう

入力：文字列

出力：文字の種類に応じたλ、文字列の長さに応じたshift

前提：アルファベット（文字の種類）は3文字（A、B、C）とする

木

木

木 データ構造における木（Tree）または有向木（Directed Tree）と は、節（Node）の有限集合 𝑇 であって、次の2つの性質を満たす ものを言う。

1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む

2. 根以外の節は0個以上の互いに素な部分集合𝑇₁, ⋯ , 𝑇_𝑛 に分割さ れ、各 𝑇_𝑖 1 ≤ 𝑖 ≤ 𝑛 は再び木になっている

互いに素な集合：

共通の要素がない集合同士 互いに素な集合：

共通の要素がない集合同士 𝑇_𝑖 を木𝑇の部分木

（Subtree）という 𝑇_𝑖 を木𝑇の部分木

（Subtree）という

グラフ理論の木の構造をしたデータ構造 木構造

木構造

木の表現例

2014/10/30 アルゴリズムとデータ構造

20

𝐴

𝐵 𝐶 𝐷

𝐸 𝐹 𝐺 𝐻 𝐼

𝐽

𝐴 𝐵 𝐸 𝐹 𝐽 𝐺 𝐶 𝐷 𝐻 𝐼

𝐴 𝐴 𝐵

𝐵 𝐶𝐶 𝐷𝐷

𝐸

𝐸 𝐹𝐹 𝐺𝐺 𝐻𝐻 𝐼𝐼 𝐽𝐽

根からその節に至るまでに出会う節の個数

木の用語（１）

節の次数

節の次数 その節から出ている枝の本数。部分木の個数。

葉（Leaf）

葉（Leaf） 次数0の節 内部節

（Internal Node）内部節

（Internal Node） 葉以外の節。分枝節（Branch Node）とも。

節のレベル

（Level）

節のレベル

（Level）

レベルの最大値 木の高さ

（Height）木の高さ

（Height）

子から見たもとの木の根

木の用語（２）

2014/10/30 アルゴリズムとデータ構造

22

子

（Child、Son）

子

（Child、Son） 木の根から見て部分木の根 親

（Parent）

親

（Parent）

節𝑥が（節𝑥の）親を通過しないで節𝑦へ至る1つ以上 の枝の系列（長さが1以上の経路）があるとき、 節𝑥 を節𝑦の先祖という。

先祖

（Ancestor）先祖

（Ancestor）

上記のとき、 節𝑦を節𝑥の子孫という。

子孫

（Descendant）子孫

（Descendant）

0個以上の木の有限集合 森

（Forest）

森

（Forest）

多進木

順序木

（Ordered Tree）

順序木

（Ordered Tree） 木 𝑇 の部分木 𝑇₁, ⋯ , 𝑇_𝑛 について順序が導入されてい るとき、その木を順序木と言う。

図式表現では左の部分木ほど前にあるものと考える 図式表現では左の部分木ほど前にあるものと考える

𝐴 𝐴 𝐵

𝐵 𝐶𝐶 𝐷𝐷

𝐴 𝐴 𝐵 𝐶 𝐵

𝐶 𝐷𝐷

兄弟（Brother）：

より前の部分木の根であるものを、後ろのものの兄といい、

逆を弟という

𝑛

進木

2014/10/30 アルゴリズムとデータ構造

24

𝑛進木

（ 𝑛-ary tree）𝑛進木

（ 𝑛-ary tree） 節（Node）の有限集合 𝑇 であって、空集合であるか、

または次の2つの性質を満たすものを言う。ただし𝑛 ≥ 1 。

1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む

2. 根以外の節は 𝑛個の互いに素な順序の付いた部分集合𝑇₁, ⋯ , 𝑇_𝑛 に分割され、各 𝑇_𝑖 1 ≤ 𝑖 ≤ 𝑛 は再び𝑛進木になっている

部分木𝑇_𝑖 を第𝑖 部分木という。

特に𝑛 = 1の場合、𝑛進木は線型 リストになる

部分木𝑇_𝑖 を第𝑖 部分木という。

特に𝑛 = 1の場合、𝑛進木は線型 リストになる

𝑛 ≥ 2のとき多進木（Multiway Tree）という。

𝑛 ≥ 2のとき多進木（Multiway Tree）という。

二分木

二分木

（Binary Tree）二分木

（Binary Tree） 節（Node）の有限集合 𝑇 であって、空集合であるか、

または次の2つの性質を満たすものを言う。

1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む 2. 根および2個の互いに素な二分木𝑇_𝑙, 𝑇_𝑟 とからなる

兄の𝑇_𝑙 を左部分木（Left

Subtree）、弟の𝑇_𝑟 を右部分木

（Right Subtree）という。

兄の𝑇_𝑙 を左部分木（Left

Subtree）、弟の𝑇_𝑟 を右部分木

（Right Subtree）という。

図式表現においては、左部分木 と右部分木をはっきり区別でき るように描かなければならない 図式表現においては、左部分木 と右部分木をはっきり区別でき るように描かなければならない

𝐴

𝐴 𝐴𝐴 𝐴𝐴

二分木の走査

2014/10/30 アルゴリズムとデータ構造

26

二分木の走査

二分木の走査 二分木のすべての節を訪問する処理

𝑅 𝑅

𝛼

𝛼 𝛽𝛽

二分木の 再帰的構造

二分木の 再帰的構造

木𝑥の走査を行う手順を𝑡𝑟𝑎𝑣 𝑥 とすると、以下の3通りの走 査が考えられる

1. 先順： 𝑅 → 𝑡𝑟𝑎𝑣 𝛼 → 𝑡𝑟𝑎𝑣(𝛽) 2. 中順： 𝑡𝑟𝑎𝑣 𝛼 → 𝑅 → 𝑡𝑟𝑎𝑣(𝛽) 3. 後順： 𝑡𝑟𝑎𝑣 𝛼 → 𝑡𝑟𝑎𝑣(𝛽) → 𝑅

二分木の走査の例

𝐴 𝐴 𝐵

𝐵 𝐶𝐶

𝐷

𝐷 𝐹𝐹 𝐺𝐺

先順 先順

中順 中順

後順 後順

演習１：二分木の走査

2014/10/30 アルゴリズムとデータ構造

28

下記の二分木を先順・中順・後順でそれぞれ走査し たときの、節の訪問順序を記載せよ

𝐴 𝐴 𝐵

𝐵 𝐶𝐶

𝐷

𝐷 𝐸𝐸 𝐹𝐹 𝐺𝐺 𝐻

𝐻 𝐼𝐼 𝐽𝐽

二分木の節の物理構造

データ本体

left record right p

public class BinTreeNode {

public BinTreeNode left;

public BinTreeNode right;

public String record;

public BinTreeNode(){

left = null;

right = null;

} }

演習（その

）

2014/10/30 アルゴリズムとデータ構造

30

二分木の走査 二分木の走査

演習：下記の二分木を先順・中順・後順でそれぞれ走査したときの、節の訪問 順序を記載せよ

入力：なし（二分木データはプログラム中に記載してよい）

出力：先順、中順、後順

前提：各順での訪問順序 _𝐴𝐴

𝐵

𝐵 𝐶𝐶

𝐷

𝐷 𝐸𝐸 𝐹𝐹 𝐺𝐺 𝐻

𝐻 𝐼𝐼 𝐽𝐽

演習（その

）：実行イメージ

> java BinTree First:

A->B->D->H->I->

（省略）

Middle:

（省略）

Last:

（省略）

> java BinTree First:

A->B->D->H->I->

（省略）

Middle:

（省略）

Last:

（省略）

2

項演算子と、算術式の木構造

2013/10/24 アルゴリズムとデータ構造

32

d=a*(b+c)

=

d *

a +

b c

z=y+1/(x-1)

=

z +

y /

1 -

x 1

2項演算子

2項演算子 2つの項を用いて演算を行う演算子

グラフ理論の木の構造をしたデータ構造 木構造

木構造

算術式の基本構造

演算子

第

被演算子 第

被演算子

二分木の節の物理構造

2014/10/30 アルゴリズムとデータ構造

34

データ本体

left record right p

d=a*(b+c)

=

d *

a +

b c

=

d *

a +

b c

決定木：偽コインの問題（１）

8枚のコイン𝑎, 𝑏, ⋯ , ℎ があり、そのうち1枚だけが偽物である。偽物は外見は 違わないが、重さが異なっているので区別できる。ただし、偽物が本物より 重いのか軽いのか不明である。ここで、天秤を3回だけ用いて、どのコイン が偽物でかつそれは本物より重いのか軽いのかを知るにはどうすれば良いか 8枚のコイン𝑎, 𝑏, ⋯ , ℎ があり、そのうち1枚だけが偽物である。偽物は外見は 違わないが、重さが異なっているので区別できる。ただし、偽物が本物より 重いのか軽いのか不明である。ここで、天秤を3回だけ用いて、どのコイン が偽物でかつそれは本物より重いのか軽いのかを知るにはどうすれば良いか

𝑎, 𝑏, 𝑐を左、𝑑, 𝑒, 𝑓を右

𝑎, 𝑏, 𝑐を左、𝑑, 𝑒, 𝑓を右 左が重い 𝑎, 𝑏, 𝑐 のどれかが重い or 𝑑, 𝑒, 𝑓のどれかが軽い 𝑎, 𝑏, 𝑐 のどれかが軽い or

𝑑, 𝑒, 𝑓のどれかが重い 右が重い

𝑔, ℎ のどちらかが偽物 釣り合う

𝑎, 𝑑を左、 𝑏, 𝑒を右 𝑎, 𝑑を左、 𝑏, 𝑒を右

…

…

左が重い 𝑎が重いor

𝑒が軽い

右が重い

𝑎を左、𝑒以外の何かを右 𝑎を左、𝑒以外の何かを右

決定木：偽コインの問題（２）

2014/10/30 アルゴリズムとデータ構造

36

𝑎 + 𝑏 + 𝑐 ∶ 𝑑 + 𝑒 + 𝑓 𝑎 + 𝑏 + 𝑐 ∶ 𝑑 + 𝑒 + 𝑓

𝑎 + 𝑑 ∶ 𝑏 + 𝑒

𝑎 + 𝑑 ∶ 𝑏 + 𝑒 𝑎 + 𝑑 ∶ 𝑏 + 𝑒𝑎 + 𝑑 ∶ 𝑏 + 𝑒

𝑎 ∶ 𝑥

𝑎 ∶ 𝑥 𝑐 ∶ 𝑥𝑐 ∶ 𝑥 𝑏 ∶ 𝑥𝑏 ∶ 𝑥 𝑑 ∶ 𝑥𝑑 ∶ 𝑥 𝑓 ∶ 𝑥𝑓 ∶ 𝑥 𝑒 ∶ 𝑥𝑒 ∶ 𝑥 𝑔 ∶ ℎ

𝑔 ∶ ℎ

𝑔 ∶ 𝑥

𝑔 ∶ 𝑥 ℎ ∶ 𝑥ℎ ∶ 𝑥

> = <

>

=

< > < > <

=

演習（その

）

偽コインの問題 偽コインの問題

演習：8枚のコインから決定木を用いて偽コインを見つけるプログラムを作成し、

天秤で比較される順序と結果を記載せよ 入力：偽コインの指定（0～7）

出力：3回の天秤の比較において、それぞれに載せられるコインとその結果

演習（その

）：実行イメージ

2014/10/16 アルゴリズムとデータ構造

38

> java FakeCoin First:

(0, 1, 2) – (3, 4, 5) -> (3, 4, 5) is heavier Second:

(0, 3) – (1, 4)

-> (0, 3) is heavier Thrid:

(0) – (1)

-> (0) is heavier Result:

Fake Coin is 0, and it is heavy.

> java FakeCoin First:

(0, 1, 2) – (3, 4, 5) -> (3, 4, 5) is heavier Second:

(0, 3) – (1, 4)

-> (0, 3) is heavier Thrid:

(0) – (1)

-> (0) is heavier Result:

Fake Coin is 0, and it is heavy.

本日の到達目標と概要

•

到達目標

–

木の定義と様々な木を理解する

•

概要

–

木の定義

多進木

木の走査

–

決定木（偽コインの問題）

締切と提出方法：演習その

～

• 締切

– 3週間後（11月20日）の16:10まで

• 提出方法

– 電子メール

• メールアドレス

– [email protected]

– メールのタイトルに「アルゴリズムとデータ構造第4回課題」と書 いてください

– 作ったプログラムをメールに添付してください。

• 注意事項

– 必ず金岡から受領確認メールを返します。

• 必ず日本語で受領確認メールを返します

• 英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです

– メールで提出がされていないものは未提出とみなします

2014/10/30 アルゴリズムとデータ構造

40