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

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

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

二進木のいろいろ (1) 高さ 0 の二進木 根一個からなる木も二進木 (2) 高さ 1 の二進木 ．．．3通り 左 右 左 右 (3) 高さ 2 の二進木 は…

高さ 2 の二進木 左 左 左 右 右 左 左 右 右 右 左 右 左 右 左 右 左 左 右 …などなど 右 右

二進木の演習 高さ2の二進木をすべて書いてみよう。 　何個あるだろうか？

二進木のデータ構造 二進木の場合、子は左か右しかない だから、｢一般の木」よりも特殊なデータ構造を考えるのが便利 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 「引数=値」とは、引数が省略できること、省略された場合に「値」となることを意味する

二進木用のデータ構造を図示すると data left right または data left right 図で書くと二進木を構成するデータ構造は 数または文字列 data left ポインタ( nilのことも） right ポインタ( nilのことも） または data left right

二進木の表現 4 4 3 5 3 5 2 8 2 8 6 1 1 6 7 7

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

二分探索木を作る… 入力データが {4, 5, 8, 3, 6, 10, 2, 9, 1} とする。どのように二分探索木を作るか？ 最初だけ特別：先頭の要素を値に持つ根の頂点を作る root = Vertex.new(4) ここでは図を書いて、木ができていく様子を見よう

二分探索木を作る…(続き） root = Vertex.new(4) によって以下の頂点が作られる： 4 4 または 　 さもなくば 　　　　右の部分木を 成長させる 新たな頂点を作って、元の頂点と接続する

二分探索木を作る…(続き） 4 4 4 4 5 5 または に続く要素は 5 で、4 < 5 なので、次のよ うに「右の部分木」を成長させる: 4 4 元の頂点と接続 5 5 新たな頂点

二分探索木を作る…(続き） 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

練習：二分探索木を作る 4 3 5 2 1 8 6 7 先のスライドにならって、次のデータから二分探索木を求めよ。 { 5, 9, 2, 7, 1, 3, 6, 8, 4} 　注：表記法について 　右の木に対し下のように書いてもよいとする 　　　[4, [3, [2, [1],nil ],nil ], [5, nil, [8,[6,nil,[7]], nil]]] 頂点のラベル 4 3 5 2 1 8 6 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 < @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.insert(x) # 左の子に対し再帰 end #if # xがtの値以上の場合 elsif (@right = = nil)　　　　 # t の右の子がないなら @right = Vertex.new(x) # xを値とする頂点を else # 作って t の右の子に @right.insert(x) # 右の子に対し再帰 end # if end # def 左 left 右 right

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

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

練習：中間順の木のなぞり 8 5 10 3 7 9 12 1

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

練習：先行順と後行順の木のなぞり 8 5 10 3 7 9 12 1

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

数式の木の問題 先の木を １） 中間順(inorder) ２） 先行順(preorder) ３） 後行順(postorder) 　でそれぞれなぞった時にはどのような記号列が表示されるか？ 参考：ポーランド記法、逆ポーランド記法

中間順に木をなぞるプログラム 先行順(preorder)、後行順(postorder)のプログラムはどう書ける？ class Vertex def initialize … 　　attr_attribute :data, :left, :right def inorder # 中間順でなぞる 　　　@left.inorder if @left != nil　　 # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder if @right != nil　# vの右の子をなぞる end # def of inorder end # class 先行順(preorder)、後行順(postorder)のプログラムはどう書ける？

2進木を用いたソート 入力データから insert によって二分探索木をつくり、最終的にできた木の頂点を｢中間順」に読み出すと… 入力データの最も小さいものから大きいものへ 順に入力データが並ぶ…ソートされている！ これはどのような計算量で実行可能か？

二分探索木を作り、中間順に読み出す 4 { 4 5 8 3 6 3 5 } 10 2 9 1 2 8 6 1 10 9 入力データ: 中間順に読出し： 6 1 10 9

2進木によるソート 最悪のケース：教科書p.28図32の様な場合 n個のデータから二分探索木を作る ⇒ O(n2) 平均的に(特にデータをシャッフルすると）n個のデータから作られる木の高さは O(n log n) ⇒ 従って二分探索木を作る計算量も O(n log n) 理由： n個のデータに対し、高さに比例した個数の枝をたどって頂点を付け加えるから