アルゴリズムとデータ構造
第6週 木の走査、二分木、決定木
2013年10月31日 金岡 晃
授業計画
第1週 (9/26)
データ構造とアルゴリズムの基 礎
第2週 (10/3)
アルゴリズムの効率、線形構造 第3週
(10/10)
スタックと待ち行列 第4週
(10/17)
文字列照合（KMP法、BM法）
第5週 (10/24)
木構造、木の走査
→文字列照合（BM法）、木構 造
第6週 (10/31)
木の走査、二分木、決定木
第8週 (11/21)
休講 第9週
(11/28)
グラフ構造と最短路問題 第10週
(12/5)
解の探索：Aアルゴリズム 第11週
(12/12)
データ整列：ヒープソート 法
第12週 (12/19)
データ整列：クイックソー ト法
第13週 (1/9)
データ探索：ハッシュ法 第14週 データ探索：木構造探索法
第 5 週【復習】
文字列照合（ BM 法）、木の構造
アルゴリズムとデータ構造
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 shift[1] 3文字 shift[1]=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 B A B B A B
BM
法：
shiftの導出
shiftの導出
（アルゴリズム）
BM
法：
λと
shiftの利用
アルゴリズムの流れ
パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算
shiftの計算
パターンの末尾から照合していくが 照合失敗後のシフト量は
照合を失敗したテキスト場所kの文字text[k]
パターンの場所をiとした場合、
shift[i]と(i- λ[text[k]) の大きい方の分だけシフトする
照合
各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算
λの計算
演習
1：
BM法における
λと
Shift導出
パターン “BACBABA”の場合の λとshiftの導出を行え。
λはアルゴリズムを用い、
shiftは図解とアルゴリズムを用いて示せ
ただし、
アルファベットは A,B,Cの3文字とする
2
項演算子と、算術式の木構造
d=a*(b+c)
=
d *
a +
b c
z=y+1/(x-1)
=
z +
y /
1 -
x 1
2項演算子 2つの項を用いて演算を行う演算子
グラフ理論の木の構造をしたデータ構造 木構造
算術式の基本構造
演算子
第
1被演算子 第
2被演算子
中置記法と後置記法
•
中置記法
–
演算子が中央に置かれている
A+B
•
前置記法
–
演算子が前に置かれている
+AB
•
後置記法（ポーランド記法）
–
演算子が後ろに置かれている
AB+
人が通常使う記法
コンパイラが通常使う記法
第 6 週
木の走査、二分木、決定木
アルゴリズムとデータ構造
本日の到達目標と概要
•
到達目標
–
木の定義と様々な木を理解する
•
概要
–
木の定義
–
多進木
–
木の走査
–
決定木（偽コインの問題）
木
木 データ構造における木（Tree）または有向木（Directed Tree）と は、節（Node）の有限集合 𝑇 であって、次の2つの性質を満たす ものを言う。
1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む
2. 根以外の節は0個以上の互いに素な部分集合𝑇1, ⋯ , 𝑇𝑛 に分割さ れ、各 𝑇𝑖 1 ≤ 𝑖 ≤ 𝑛 は再び木になっている
互いに素な集合：
共通の要素がない集合同士 𝑇𝑖 を木𝑇の部分木
（Subtree）という
木の表現例
𝐴
𝐵 𝐶 𝐷
𝐸 𝐹 𝐺 𝐻 𝐼
𝐽
𝐴 𝐵 𝐸 𝐹 𝐽 𝐺 𝐶 𝐷 𝐻 𝐼
𝐴
𝐵 𝐶 𝐷
𝐸 𝐹 𝐺 𝐻 𝐼
𝐽
根からその節に至るまでに出会う節の個数
木の用語（１）
節の次数 その節から出ている枝の本数。部分木の個数。
葉（Leaf） 次数0の節 内部節
（Internal Node） 葉以外の節。分枝節（Branch Node）とも。
節のレベル
（Level）
木の高さ
子から見たもとの木の根
木の用語（２）
子
（Child、Son） 木の根から見て部分木の根 親
（Parent）
節𝑥が（節𝑥の）親を通過しないで節𝑦へ至る1つ以上 の枝の系列（長さが1以上の経路）があるとき、 節𝑥 を節𝑦の先祖という。
先祖
（Ancestor）
上記のとき、 節𝑦を節𝑥の子孫という。
子孫
（Descendant）
0個以上の木の有限集合 森
（Forest）
多進木
順序木
（Ordered Tree） 木 𝑇 の部分木 𝑇1, ⋯ , 𝑇𝑛 について順序が導入されてい るとき、その木を順序木と言う。
図式表現では左の部分木ほど前にあるものと考える
𝐴
𝐵 𝐶 𝐷
𝐴
𝐶 𝐵 𝐷
兄弟（Brother）：
より前の部分木の根であるものを、後ろのものの兄といい、
逆を弟という
𝑛
進木
𝑛進木
（ 𝑛-ary tree） 節（Node）の有限集合 𝑇 であって、空集合であるか、
または次の2つの性質を満たすものを言う。ただし𝑛 ≥ 1 。
1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む
2. 根以外の節は 𝑛個の互いに素な順序の付いた部分集合𝑇1, ⋯ , 𝑇𝑛 に分割され、各 𝑇𝑖 1 ≤ 𝑖 ≤ 𝑛 は再び𝑛進木になっている
部分木𝑇𝑖 を第𝑖 部分木という。
特に𝑛 = 1の場合、𝑛進木は線型
リストになる
𝑛 ≥ 2のとき多進木（Multiway Tree）という。
二分木
二分木
（Binary Tree） 節（Node）の有限集合 𝑇 であって、空集合であるか、
または次の2つの性質を満たすものを言う。
1. 根（Root）と呼ばれる節 𝑅 をちょうど1つ含む 2. 根および2個の互いに素な二分木𝑇𝑙, 𝑇𝑟 とからなる
兄の𝑇𝑙 を左部分木（Left
Subtree）、弟の𝑇𝑟 を右部分木
（Right Subtree）という。
図式表現においては、左部分木 と右部分木をはっきり区別でき るように描かなければならない
𝐴 𝐴 𝐴
二分木の走査
二分木の走査 二分木のすべての節を訪問する処理
𝑅
𝛼 𝛽
二分木の 再帰的構造
木𝑥の走査を行う手順を𝑡𝑟𝑎𝑣 𝑥 とすると、以下の3通りの走 査が考えられる
1. 先順： 𝑅 → 𝑡𝑟𝑎𝑣 𝛼 → 𝑡𝑟𝑎𝑣(𝛽) 2. 中順： 𝑡𝑟𝑎𝑣 𝛼 → 𝑅 → 𝑡𝑟𝑎𝑣(𝛽) 3. 後順： 𝑡𝑟𝑎𝑣 𝛼 → 𝑡𝑟𝑎𝑣(𝛽) → 𝑅
二分木の走査の例
𝐴
𝐵 𝐶
𝐷 𝐹 𝐺
先順
中順
後順
演習１：二分木の走査
下記の二分木を先順・中順・後順でそれぞれ走査し たときの、節の訪問順序を記載せよ
𝐴
𝐵 𝐶
𝐷 𝐸 𝐹 𝐺
𝐻 𝐼 𝐽
二分木の節の物理構造
データ本体
left record right p
d=a*(b+c)
=
d *
=
d *
a +
決定木：偽コインの問題（１）
8枚のコイン𝑎, 𝑏, ⋯ , ℎ があり、そのうち1枚だけが偽物である。偽物は外見は 違わないが、重さが異なっているので区別できる。ただし、偽物が本物より 重いのか軽いのか不明である。ここで、天秤を3回だけ用いて、どのコイン が偽物でかつそれは本物より重いのか軽いのかを知るにはどうすれば良いか
𝑎, 𝑏, 𝑐を左、𝑑, 𝑒, 𝑓を右 左が重い 𝑎, 𝑏, 𝑐 のどれかが重い or 𝑑, 𝑒, 𝑓のどれかが軽い 𝑎, 𝑏, 𝑐 のどれかが軽い or
𝑑, 𝑒, 𝑓のどれかが重い 右が重い
𝑔, ℎ のどちらかが偽物 釣り合う
𝑎, 𝑑を左、 𝑏, 𝑒を右
…
…
左が重い 𝑎が重いor
𝑒が軽い
右が重い 釣り合う …
𝑎を左、𝑒以外の何かを右
わかる！
決定木：偽コインの問題（２）
𝑎 + 𝑏 + 𝑐 ∶ 𝑑 + 𝑒 + 𝑓
𝑎 + 𝑑 ∶ 𝑏 + 𝑒 𝑎 + 𝑑 ∶ 𝑏 + 𝑒
𝑎 ∶ 𝑥 𝑐 ∶ 𝑥 𝑏 ∶ 𝑥 𝑑 ∶ 𝑥 𝑓 ∶ 𝑥 𝑒 ∶ 𝑥
𝑔 ∶ ℎ
𝑔 ∶ 𝑥 ℎ ∶ 𝑥
> = <
>
=
< > < > <
=
演習２：
10枚のコインの場合
偽コインの問題で、コインが全部で10枚ある場合の 決定木を書け
本日の到達目標と概要
•
到達目標
–
木の定義と様々な木を理解する
•
概要
–
木の定義
–
多進木
–
木の走査
–
