データ構造とアルゴリズム
(第4回)
静岡大学工学部
安藤和敏
2007.12.10
第3章アルゴリズムにおける基本概念
3.1 木
3.2 再帰
第3章アルゴリズムにおける基本概念
3.1 木
3.2 再帰
一般生活における木(トーナメント表)
優勝
浜
名
日
大
三
島
藤
枝
明
誠
藤
枝
東
清
水
東
常
葉
橘
磐
田
東
静
岡
北
清
水
商
業
静
岡
学
園
一般生活における木(組織図)
社長
広報部
営業部
開発部
総務部
経理部
デバイス
機械
制御機器
個人
法人
木の概念
いくつかの節点と節点どうしをつなぐ
いくつかの辺から構成される
節点は,この
ように円で表
す.
各節点はデータをもつ場合がある
節点を表す円の
内部にそのデー
タを記入する.
9
2
8
3
2
15
17
10
5
11
23
28
木の根
節点の中には根と
呼ばれる節点が1
つだけ存在して,根
を起点として下に
分岐するように描
かれる. 2
8
3
9
2
15
17
10
5
11
23
28
親子
u は v の親である,
といい, v は u の子
であるという.
9
u
2
v 8
3
2
15
17
10
5
11
23
28
葉と内部節点
子をもたない節点を
葉と呼び,葉以外の
節点を内部節点と
呼ぶ.
9
2
8
3
2
15
17
10
5
11
23
28
k分木
9
これは,2分木である.
2
8
3
2
15
17
10
5
11
23
28
レベルと木の高さ
根までの
経路
9
2
8
3
15
17
レベル0
レベル1
この節点のレベル=この節
2
点から根までの経路に含ま
れる辺の数
レベル2
10
5
11
23
28
木の高さ=レベルの最大値+1
レベル3
これは完全2分
木の例
完全k分木
全ての葉のレベ
ルが等しく,かつ,
全ての内部節点
がk個の子を持
つ木
性質3.1
完全2分木の葉の数は,その完全2分木の高さを h とす
h 1
h である.
ると,
2  O( 2 )
レベルh-1
性質3.2
完全2分木の高さは,その完全2分木の葉の数を m と
すると,
1  log 2 m  O(log m)
である.
性質3.1によって,
h 1
.
m2
h 1  log m.
ゆえに,
性質3.3
完全2分木の節点の数は,その完全2分木の高さを h
とすると,
2  1  O( 2 )
h
である.
h
性質3.4
完全2分木の高さは,その完全2分木の節点の数を n
とすると,
log 2 (n  1)  O(log n)
である.
木の実現
1
2
1
12
4
5
10
9
33
10
12
3
6
21
8
23
32
7
2
11 12
9
28
5
13 14
19
15
15
6
木の実現
1
2
1
12
4
5
10
9
33
10
12
3
6
21
8
23
32
7
2
5
13 14
11 12
9
28
19
15
15
6
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
T 32
1
12 10 21
2
… 5
23 33 12
9
28 19 15
6
第3章アルゴリズムにおける基本概念
3.1 木
3.2 再帰
問題3.1
ある細胞は,試験管中で1分経過すると分裂し,数
が2倍になるが,分裂直後に全細胞のうちの4つは
死滅してしまう.最初に試験管に10個の細胞を入れ
たとき,細胞を入れてから n 分後の試験管中の細
胞の数はいくつか.
n 分後の細胞の個数を c(n) という関数で表す.
c(n) は以下の漸化式の解である.
c(n)  2c(n  1)  4,

c(0)  10
アルゴリズム3.1
cell (n) {
if (n == 0) {
return 10;
} else {
return 2*cell(n-1) - 4;
}
}
関数 cell()の実行の様子
cell (3)
52
2 * cell (2) - 4
2 * 28 - 4
2 * cell (1) - 4
2 * 16 - 4
2 * cell (0) - 4
2 * 10 - 4
10
10
アルゴリズム3.2(和の計算)
sum = 0;
for (i=0; i<n; i=i+1) {
sum = sum + A[i];
}
sum を出力;
このアルゴリズムの時間計算量はO(1)×n=O(n).
アルゴリズム3.3
和の計算を行う再帰アルゴリズム(その1)
recursive_sum1(A[0], A[1],...,A[n-1]) {
if (引数がA[0]のみである) {
return A[0];
} else {
return recursive_sum1(A[0],A[1],...,A[n-2])+A[n-1];
}
アルゴリズム3.4
和の計算を行う再帰アルゴリズム(その2)
recursive_sum2(A[0], A[1],...,A[n-1]) {
if (引数がA[k]という1つの配列要素のみである) {
return A[k];
} else {
配列Aを半分ずつの以下の2つの配列に分割する;
A1 = { A[0],A[1],...,A[(n-1) /2]}
A2 = { A[(n-1)/2+1],A[(n-1)/2 + 2],...,A[n-1]}
x = recursive_sum2(A1);
y = recursive_sum2(A2);
return x + y;
}
宿題
第3章の演習問題の全て.(提出しなくてもよい.巻末
の解答例を見て自己採点せよ.)
ダウンロード

PPT