情報とコンピュータ

データ構造とアルゴリズム
(第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
木の根
節点の中には根と
呼ばれる節点が１
つだけ存在して，根
を起点として下に
分岐するように描
かれる． 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
これは完全２分
木の例
完全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
ある細胞は，試験管中で１分経過すると分裂し，数
が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
和の計算を行う再帰アルゴリズム（その１）
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]という１つの配列要素のみである) {
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章の演習問題の全て．（提出しなくてもよい．巻末
の解答例を見て自己採点せよ．）

Download Report