二進木(二分木）

アルゴリズムとデータ構造
第3章ヒープ
６月３日分
情報知能学科
白井英俊
二進木（二分木）とは
高々2個
• Binary tree の訳語
定義：どの頂点も2個以下の子をもつ木
2個の子は左の子と右の子のどちらか
左
右
０個の子
１個の子
２個の子
左
右
頂点の深さと木の高さ
• 根と頂点の間の枝の数が「頂点の深さ」
• 最も深い頂点の｢深さ」が「木の高さ」
根＝深さ０
深さ 1
深さ 2
深さ 3
深さ 4
この木の
高さ＝ 4
練習問題
(1) 「３」の頂点の深さは？
(2) この木の高さは？
8
5
3
1
10
7
9
12
二進木のいろいろ
(1) 高さ 0 の二進木
根一個からなる木も二進木
(2) 高さ 1 の二進木．．．3通り
左
右
左
(3) 高さ 2 の二進木は…
右
高さ 2 の二進木
左
左
左
右
右
左
左
右
左
左
右
右
右
右
左
左
左
右
右
右
右
…などなど
二進木の演習
• 高さ2の二進木をすべて書いてみよう。
何個あるだろうか？
考え方ー場合分け：
(１) 根からみて左の部分木の高さが２の場合：
右の部分木の高さが0, 1, 2に分けると
(a)右の部分木の高さが0：１通り
(b)右の部分木の高さが1：１通り
(c)右の部分木の高さが2：あとで計算
ここで左の部分木の高さが２の場合は3通り
だから合計 2*3 = 6通り
（２）根からみて右の部分木の高さが２の場合: (1)と同様 6通り
（３）根からみて右と左の部分木がともに高さ２の場合: 3*3=9通り
高さ 2 の二進木
(1)
(2)
(3)
(8)
(7)
(10)
(11)
(4)
(5)
(6)
(9)
(12)
高さ 2 の二進木(続き）
(13)
(16)
(19)
(14)
(17)
(20)
(15)
(18)
(21)
二進木のデータ構造
• 二進木の場合、子は左か右しかない
だから、｢一般の木」よりも特殊なデータ構造を
考えるのが便利
「引数=値」とは、引数が省略できること、省略
された場合に「値」となることを意味する
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
ポインタ( nilのことも）
または
ポインタ( nilのことも）
data
left
right
二進木の表現
4
4
3
3
5
2
1
2
8
6
1
7
5
8
6
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
その次の要素を x とすると、
頂点の値 > x ならば、左の部分木を
さもなくば
右の部分木を
成長させる新たな頂点を作って、元の頂点
と接続する
二分探索木を作る…(続き）
入力データ：{4, 5, 8, 3, 6, 10, 2, 9, 1}
または
4
4
に続く要素は 5 で、4 < 5 なので、次のよ
うに「右の部分木」を成長させる:
4
4
元の頂点と接続
5
新たな頂点
5
二分探索木を作る…(続き）
2<4だ
3<4だ
から左
から左
2<3だ
から左
2
1
3
4<10
４<５だ
入力データ:
４<８だ
4
４<６だ
から右
から右
から右
から右 { 4 5 8 3 6
5 ５<８だ
5<10
５<６だ
}
10
2
9
1
から右
から右
から右
6<8だ
8
8<10
から左
から右
6
10
9
どこにノードがで
きるか予想しよう
練習：二分探索木を作る
• 先のスライドにならって、次のデータから二分
探索木を求めよ。
{ 5, 9, 2, 7, 1, 3, 6, 8, 4}
頂点のラベル
注：表記法について
右の木に対し下のように書いてもよいとする
4
[4, [3, [2, [1],nil ],nil ],
[5, nil,
[8,[6,nil,[7]],
nil]]]
3
5
2
1
左の木
8
6
右の木
7
練習問題の解答{ 5, 9, 2, 7, 1, 3, 6, 8, 4}
入力データ:
5
2
1
9
3
7
4
6
{5 9 2 7 1
3 6 8 4}
配列を用いて表すと：
8
[5, [2, [1], [3, nil, [4]]],
[9, [7, [6], [8]], nil]]
二分探索木の特徴
(1) n個の頂点の二分探索木の高さは log(n)に比例
(2) したがって、二分探索木上での探索は O(log(n))
根
R
S
SS
Sよりも小さい
B
SB
Sよりも大きい
根（R)より小さいもの
BS
BB
Bよりも小さい Bよりも大きい
根(R)よりも大きいもの
木に要素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を値とする頂点を
右 else
# 作って t の右の子に
right
@right.insert(x)
# 右の子に対し再帰
end # if
end # def
プログラムによる確認
• ウェブページにある June03.rb を走らせて
みる
｢木のなぞり」、または値の読出し
頂点の値が真ん中の位置で読
み出されるので「中間」順
• 中間順の読出し
左の子、根頂点の値、右の子
という順に、値を読み出す
・参考：先行順、後行順、もある
例スタートはいつ
根頂点(２)
8
も根が基準
左(1)
5
だから、 5, 8, 10
10 右(3)
部分木について
右は「８」を根とする木
これは、「５」を根とする木
と「10」を根とする木を、
それぞれ左と右に接続し
た木、とみなせる。
それぞれ、頂点「８」
から見て、左部分木
と右部分木と呼ぶ。
3
1
8
5
10
7
9
12
中間順の｢木のなぞり」の例2
根頂点(２)
8
左(1)
5
3
10
7
スタートはいつ
も根が基準
右(3)
20
｢左部分木」は(部分）木なので、
中間順が適用され:
根の｢右部分木」は
(部分）木なので、中間
順が適用され:
練習：中間順の木のなぞり
8
5
3
1
10
7
9
12
他の｢木のなぞり」
• 先行順：「根頂点の値」、左の子、右の子
• 後行順：左の子、右の子、「根頂点の値」
先の演習問題の木に対し、先行順と後行順の
それぞれで｢木をなぞる」と、どのようになる
か？
練習：先行順と後行順の木のなぞり
8
5
3
1
10
7
9
12
応用問題：数式の木
例： (a+b)*(c-d*e) は次の二進木で表現される（葉に
は変数が、葉以外の頂点は演算子が書かれる）
＊
＋
a
ー
b
＊
c
d
e
数式の木の問題
• 先の木を
１）中間順(inorder)
２）先行順(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)のプログ
このプログラムは頂点のデータ
ラムはどう書ける？を次々にprintするだけなので、
returnを用いていない。
2進木を用いたソート
入力データから insert によって二分探索
木をつくり、最終的にできた木の頂点を｢中間
順」に読み出すと…
入力データの最も小さいものから大きいものへ
順に入力データが並ぶ…ソートされている！
これはどのような計算量で実行可能か？
二分探索木を作り、中間順に読み出す
入力データ:
4
3
5
2
1
{4 5 8 3 6
10 2 9 1 }
中間順に読出し：
8
6
10
9
2進木によるソート
• 最悪のケース：教科書p.28図32の様な場合
n個のデータから二分探索木を作る ⇒ O(n2)
二進探索木を中間順に読み出す ⇒ O(n)
合計： O(n2)
• 平均的に(特にデータをシャッフルすると）n個
のデータから作られる木の高さは O(n log n)
⇒ 従って二分探索木を作る計算量も O(n log n)
理由： n個のデータに対し、高さに比例した個数
の枝をたどって頂点を付け加えるから
練習問題(宿題)
問題１．中間順に木をなぞるプログラムを参考にして
、後行順および先行順で木をなぞるインスタンスメ
ソッドを作る
問題２．中間順で木をなぞるプログラムを改変して、
「葉」の値だけを取り出すインスタンスメソッドを作
る。
8
例：右の木では、 1, 7, 9, 12 が
5
出力される
問題３.所与の頂点を根に持つ 3
木の高さを返すメソッドを作る
1
10
7 9
12

Download Report