アルゴリズムとデータ構造第3章ヒープ 5月31日分の復習情報知能学科白井英俊二進木（二分木）とは高々2個 • Binary tree の訳語定義：どの頂点も2個以下の子をもつ木 2個の子は左の子と右の子のどちらか左右０個の子１個の子２個の子左右頂点の深さと木の高さ • 根と頂点の間の枝の数が「頂点の深さ」 • 最も深い頂点の｢深さ」が「木の高さ」根＝深さ０深さ 1 深さ 2 深さ 3 深さ 4 この木の高さ＝ 4 練習問題この木の高さは？左部分木の高さと右部分木の高さの大きい方＋１ 3 1 8 5 10 7 9 12 二進木を用いたソート(sort)  二進木を利用して、n個の実数を小さいものから大きいものへと昇順に並べる（ソート, sort)ことを考えよう  このために用いる二進木を「二分探索木」 (binary search tree)と呼ぶ  与えられた実数を1個ずつ読み込み、それぞれを頂点に格納しながら、二分探索木を作っていく  すべての実数に対応する頂点をもつ二分探索木の完成後、すべての頂点を中間順で読みだす。これによりソートが完成される二進木のデータ構造 • 二進木の場合、子は左か右しかないだから、｢一般の木」よりも特殊なデータ構造を考えるのが便利「引数=値」とは、引数が省略できること、省略された場合に「値」となることを意味する class Vertex def initialize(data=“ “, left=nil, right=nil) @data = data @left = left @right = right end # initialize attr_attribute :data, :left, :right end # class 木に要素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 < @data a) 左の子がなければ if (@left == nil) xの値をもつ新たな頂点 @left = Vertex.new(x) を作成し左の子とする else b) さもなくば @left.insert(x) end 2) 1)でなければ右の子に対して同様にする else … インスタンスメソッドinsert(x) 続き def insert(x) if (x < @data) # x がtの値より小さい場合 if (@left = = nil) # t の左の子がないなら @left = Vertex.new(x) # xを値とする頂点を左 else # 作って t の左の子に left @left.insert(x) # 左の子に対し再帰 end #if # xがtの値以上の場合 elsif (@right = = nil) # t の右の子がないなら @right = Vertex.new(x) # xを値とする頂点を右 # 作って t の右の子に right else @right.insert(x) # 右の子に対し再帰 end # if end # def 二分探索木を作る…(続き） 2<4だから 3<4だから左左 2<3だから左 2 1 3 4<10から４<５だから４<８だから４<６だから右右右右 4 5 6<8だから左入力データ: {4 5 8 3 6 ５<８だから 5<10から５<６だから右右 10 2 9 1 } 右 8 6 8<10から右 10 9 どこにノードができるか予想しよう｢木のなぞり」、または値の読出し頂点の値が真ん中の位置で読み出されるので「中間」順 • 中間順の読出し左の子、根頂点の値、右の子という順に、値を読み出す・参考：先行順、後行順、もある例スタートはいつ根頂点(２) 8 も根が基準左(1) 5 だから、 5, 8, 10 10 右(3) 中間順の｢木のなぞり」根頂点(２) 8 左(1) 5 3 10 7 スタートはいつも根が基準右(3) 20 ｢左部分木」は(部分）木なので、中間順が適用され: 根の｢右部分木」は (部分）木なので、中間順が適用され: 他の｢木のなぞり」 • 先行順：「根頂点の値」、左の子、右の子 • 後行順：左の子、右の子、「根頂点の値」先の演習問題の木に対し、先行順と後行順のそれぞれで｢木をなぞる」と、どのようになるか？先行順の｢木のなぞり」根頂点(１) 8 左(２) 5 3 10 7 スタートはいつも根が基準右(3) 根の｢右部分木」は 20 (部分）木なので、先行順が適用され: ｢左部分木」は(部分）木なので、先行順が適用され: 後行順の｢木のなぞり」根頂点(３) 8 左(1) 5 3 10 7 スタートはいつも根が基準右(２) 根の｢右部分木」は 20 ｢左部分木」は(部分）木なので、後行順が適用され: (部分）木なので、後行順が適用され: 応用問題：数式の木例： (a+b)*(c-d*e) は次の二進木で表現される（葉には変数が、葉以外の頂点は演算子が書かれる）＊＋ a ー b ＊ c d e 数式の木の問題 • 先の木をそれぞれ次でなぞった時１）中間順(inorder) a+b*c–d*e ２）先行順(preorder) ポーランド記法 * + a b – c * d e ３）後行順(postorder) 逆ポーランド記法 ab+cde*–* 逆ポーランド記法は「日本語的」