PowerPoint プレゼンテーション

基本情報技術概論 I (第11回)
アルゴリズム と データ構造
埼玉大学 理工学研究科
堀山 貴史
1
前回までの復習:
データ構造

基本的なデータ構造
 配列 (array)
 リスト (list)

その他のデータ構造
 スタック (stack)
 待ち行列 (queue, キュー)
 木 (tree)、2分木 (binary tree)

2分探索木、ヒープ
この後、すぐ
2
前回までの復習:
アルゴリズム

問題を解決するための、有限ステップからなる手順
(言葉やフローチャートなどで書く)

線形探索 (linear search)
探索キー
70


A[ ]
1 2
1 2
3 4 5 6 7 8 9 10
5 10 35 50 70 100 110 150 …
先頭から順番に調べる
大きさ n の配列の探索時間 (計算量)
O( n )
3
前回までの復習:

A[ ]
1 2
1 2
アルゴリズム
2分探索 (binary search)
3 4 5 6 7 8 9 10 11 12 13 14 15
5 10 35 50 70 100 110 150 190 191 200 300 400
探索キー
70



ソートされた配列に対し、高速に探索できる
探索範囲の中央を調べる
→ 探索キーとの比較で、探索範囲が半分に
計算量 … O( log n )
4
データ構造:

木
深さ
0…
(tree)
節点 と 辺 (枝 ともいう) からなり
以下の 1、2 を満たすもの
1…
2…
3…
1. すべての節点が連結である
2. サイクルを持たない
葉
先祖
親
この節点から見て
子
根
兄弟
子孫
5
データ構造:


2分木
(binary tree)
___________
各節点の子は、高々2つ
右の子 と 左の子 は、区別する
例) 下の3つは、どれも異なる2分木

完全2分木
… 20 個
… 21 個
… 22 個
6
2分木の実現法

リスト
2
1
4
2
5
深さ 0
5
7
7
配列
A[ ] 1
3
3
4

1
2
3
1
4
5
6
2
7
節点 i の
 左の子 2i
 右の子 2i + 1
 親
i /2
________
7
___________
2分探索木
8
データ構造:
2分探索木
___________

2分木の各節点に、データを格納

節点 v のデータは
(1) v のどの左の子孫よりも大きい
(2) v の 〃 右
〃
小さい
例)
6
3
最小 →
1
10
4
8
12
← 最大
7
9
2分探索木の操作
探索

探索キー
8
6
3
1
10
4
8
12
7

根から出発

探索キー = 節点のキー … 探索成功
探索キー < 節点のキー … 左の部分木へ
探索キー > 節点のキー … 右の部分木へ
10
2分探索木の操作
追加

9 を追加
6
3
1
10
8
4
7
12
9

探索と同様にして、木をたどる

木から飛び出したところに、新しい節点を加える
11
2分探索木の操作
削除

10 を削除
6
3
1
10
4
8
12
7


削除するキーを探索して削除
2分探索木の条件に合うように移動 (子孫も同様)
左部分木の最大値を移動
or 右部分木の最小値を移動
12
___________
ヒープ
13
データ構造:
ヒープ
(heap)
___________

完全2分木の各節点に、データを格納

親と子の大小関係をそろえる (ヒープ ソートに利用)


親 > 子 なら、根が最大
親 < 子 なら、根が最小
例)
2分探索木との
9
違いに注意
6
3
7
2
4
1
14
ヒープの操作

探索
最大値は?
7
6
3
5
2
4
1
ヒープ ソート


値を順に追加
最大値を順に取り出す
(最大値を探索 & 削除)
15
ヒープの操作
追加

8 を追加
7
6
3
5
2
4
1
8

ヒープの最後 (深さ最大、左詰め) に新しい節点を追加

ヒープの維持
16
ヒープの操作

削除
7
1
6
3
5
2
4
6
1
3
5
2
4
7 を削除

ヒープの最後を削除する節点に追加移動

ヒープの維持
17
データ構造:

2分木
 2分探索木
 ヒープ


木
(tree)
まとめ
左の子孫 < 親 < 右の子孫
親 > 子 (または 親 < 子)
バランス木
部分木の節点数や深さにバランスを
 完全バランス木
左右の部分木の節点数の差が1以内
 AVL 木
左右の部分木の深さが1以内
多分木
 B 木 (各節点が最大 m 個の子をもつバランス木)
18
19
20
アルゴリズム:

バブルソート
(隣接交換法)
隣り合うデータを見比べて、大小関係が逆なら交換
小 大
小
が
バ
ラ
大 バ
ラ
20
30
5
10
1
20
30
5
見比べて 1
交換
10
1
20
30
5
10
1
20
5
30
10
20
30
1
5
10
1 確定
20
バ
30
ラ
バ
5
ラ
10
20
1
30
5
10
1
5 確定
20
バ
ラ
30
バ
10
ラ
…
21
アルゴリズム:

n個
バブルソート
(隣接交換法)
計算量
1
20
30
5
10
確定
1
5
20
30
10
1
確定 5
10
20
30
1個目を確定させるのに 2個目
比較が n – 1 回
n–2回
確定
…
1
5
10
20
30
3個目
… n - 1 個目
n–3回 … 1回
全部で O( n2 )
22
アルゴリズム:

ヒープソート
(heap sort)
ヒープの最大値の取り出し、ヒープの維持を繰り返す
7
1
6
5
6
3
2
4
1
最大値の取り出し
5
6
3
2
4
1 7
最後の葉の移動
3
7
2
4
ヒープの維持
4
6
3
5
5
7
1
2
4
最大値の取り出し
3
5
67
1
2
4
最後の葉の移動
3
1
5
67
2
ヒープの維持
23
アルゴリズム:

ヒープソート
(heap sort)
ヒープの最大値の取り出し、ヒープの維持を繰り返す
7
6
1
5
6
3
2
4
1
最大値の取り出し
計算量 O( 1 )
3
5
7
2
4
ヒープの維持
計算量 O( log n )
n 回 繰り返し
… トータルの計算量
O( n log n )
24
アルゴリズム:

マージソート
ソートされた2つの列
→ 1つにマージ(併合)するのは簡単
(各列の先頭を見比べながら、小さい方を取っていく)
5 20 25 50

(併合ソート)
1 10 30 40
1回のマージの実行時間は、要素数に比例
25
アルゴリズム:
マージソート
(併合ソート)
5 25 50 20 30 40 10 1
5 25 50 20
5 25
5
25
5 25
30 40 10 1
50 20
50
20
20 50
30 40
30
40
30 40
分割
10 1
10
log n 段
1
1 10
マージ
log n 段
1 段に O( n ) 時間 → 全部で O( n log n ) 時間
27
28
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」 との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件29
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山 貴史 2007-2009 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 3, 4, 10 ~ 12, 14 ~ 17
 クリップアート : Microsoft Office Online / クリップアート

その他
 堀山 貴史

30