アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習

Presentation on theme: "アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習"— Presentation transcript:

1 アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
アルゴリズムとデータ構造 第3章　ヒープ 5月31日分の復習 情報知能学科 白井英俊

2 二進木（二分木）とは 高々2個 Binary tree の訳語 定義： どの頂点も2個以下の子をもつ木 2個の子は左の子と右の子のどちらか
定義：　どの頂点も2個以下の子をもつ木 2個の子は左の子と右の子のどちらか ０個の子 １個の子 ２個の子 左 右 左 右

3 頂点の深さと木の高さ この木の高さ＝ 4 根と頂点の間の枝の数が「頂点の深さ」 最も深い頂点の｢深さ」が「木の高さ」 根＝深さ ０ 深さ 1
深さ 2 深さ 3 深さ 4

4 練習問題 この木の高さは？ 8 10 12 5 9 3 1 7 左部分木の高さ と 右部分木の高さ の大きい方＋１

5 二進木を用いたソート(sort) 二進木を利用して、n個の実数を小さいものから大きいものへと昇順に並べる（ソート, sort)ことを考えよう
このために用いる二進木を「二分探索木」(binary search tree)と呼ぶ 与えられた実数を1個ずつ読み込み、それぞれを頂点に格納しながら、二分探索木を作っていく すべての実数に対応する頂点をもつ二分探索木の完成後、すべての頂点を中間順で読みだす。これによりソートが完成される

6 二進木のデータ構造 二進木の場合、子は左か右しかない だから、｢一般の木」よりも特殊なデータ構造を考えるのが便利 class Vertex
　だから、｢一般の木」よりも特殊なデータ構造を考えるのが便利 class Vertex def initialize(data=“ “, left=nil, right=nil) @data = data @left = left @right = right end # initialize attr_attribute :data, :left, :right end # class 「引数=値」とは、引数が省略できること、省略された場合に「値」となることを意味する

7 木に要素xを加えるインスタンスメソッドinsert(x)
class Vertex def initialize(data=“ “, left=nil, right=nil) @data = data @left = left @right = right end # initialize に続けて… def insert(x) # xは付け加える要素 1)xがdata より小さいなら if x 　a) 左の子がなければ if == nil) xの値をもつ新たな頂点 @left = Vertex.new(x) を作成し左の子とする　 else 　b) さもなくば　　　　　　　 @left.insert(x) 　　　　 end 2) 1)でなければ else 　右の子に対して同様にする 　　　…

8 インスタンスメソッドinsert(x) 続き
def insert(x) 　　if (x # x がtの値より小さい場合 if = = nil) # t　の左の子がないなら @left = Vertex.new(x) # xを値とする頂点を else # 作って t の左の子に @left.insert(x) # 左の子に対し再帰 end #if # xがtの値以上の場合 elsif = = nil)　　　　 # t の右の子がないなら @right = Vertex.new(x) # xを値とする頂点を else # 作って t の右の子に @right.insert(x) # 右の子に対し再帰 end # if end # def 左 left 右 right

9 二分探索木を作る…(続き） 4 { 4 5 8 3 6 3 5 } 10 2 9 1 2 8 6 1 10 9 入力データ:
2<4だから左 4<10から右 3<4だから左 4 ４<５だから右 ４<８だから右 入力データ: ４<６だから右 { 4 5 8 3 6 3 5 2<3だから左 ５<８だから右 5<10から右 ５<６だから右 } 10 2 9 1 2 6<8だから左 8 8<10から右 6 1 10 どこにノードができるか予想しよう 9

10 頂点の値が真ん中の位置で読み出されるので「中間」順
｢木のなぞり」、または値の読出し 頂点の値が真ん中の位置で読み出されるので「中間」順 中間順の読出し 　　左の子、根頂点の値、右の子 　という順に、値を読み出す ・参考：先行順、後行順、もある 例 スタートはいつも根が基準 根頂点(２) 8 左(1) 5 10 右(3) だから、 5, 8, 10

11 中間順の｢木のなぞり」 根頂点(２) 8 左(1) 5 10 右(3) 3 7 20 スタートはいつも根が基準 根の｢右部分木」は
(部分）木なので、中間 順が適用され: 3 7 20 ｢左部分木」は(部分）木なので、 中間順が適用され:

12 他の｢木のなぞり」 先行順： 「根頂点の値」、左の子、右の子 後行順： 左の子、右の子、 「根頂点の値」
先行順：　「根頂点の値」、左の子、右の子 後行順：　左の子、右の子、 「根頂点の値」 先の演習問題の木に対し、先行順と後行順のそれぞれで｢木をなぞる」と、どのようになるか？

13 先行順の｢木のなぞり」 根頂点(１) 8 左(２) 5 10 右(3) 3 7 20 スタートはいつも根が基準 根の｢右部分木」は
(部分）木なので、 先行順が適用され: 3 7 20 ｢左部分木」は(部分）木なので、 先行順が適用され:

14 後行順の｢木のなぞり」 根頂点(３) 8 左(1) 5 10 右(２) 3 7 20 スタートはいつも根が基準 根の｢右部分木」は
(部分）木なので、 後行順が適用され: 3 7 20 ｢左部分木」は(部分）木なので、 後行順が適用され:

15 応用問題：数式の木 例： (a+b)*(c-d*e) は次の二進木で表現される（葉には変数が、葉以外の頂点は演算子が書かれる） ＊ ＋ ー a b c ＊ d e

16 数式の木の問題 先の木をそれぞれ次でなぞった時 １） 中間順(inorder) a + b * c – d * e
　　２）　先行順(preorder) ポーランド記法 * + a b – c * d e 　　３）　後行順(postorder) 逆ポーランド記法 a b + c d e * – * 逆ポーランド記法は「日本語的」