アルゴリズムとデータ構造

(1)

アルゴリズムとデータ構造

2012 年 6 月 18 日

酒居敬一

([email protected])

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

1

(2)

平衡木

•   木を作り変えて性能のよい形に保つ

•   作り変えるための計算量が多すぎてもダメ

–   ほどほどにバランスをとる

•   AVL 木

–   ２分探索木の一種

•   B 木

–   多分木 (maybe tree ではなく、 multiway tree)

(3)

AVL 木

•   どの頂点においても、

その左部分木と右部分木の高さの差が

+1, 0, -1 のいずれかである２分探索木

(4)

Fibonacchi 数列

h=2

2

1

+ +

=

_h₋ _h₋

h

N N

N

とおくと、

+ 1

=

_h

h

N

f

2 ,

1 )

2

(h ≥ N₀ = N₁ =

1 )

1 (

₁

+

₂

+ +

=

_h₋ _h₋

h

N N

f

頂点数最少の

AVL

木の頂点数

) 1 (

) 1

(

₁

+ +

₂

+

= N

_h₋

N

_h₋

2

1 −

−

+

= f

_n

f

_n

0

= 2 f

1

= 3 f

この漸化式は

Fibonacci

数列として有名

(5)

17

9 21

23 13

11 5

7 3

19

17

9 21

23 13

11 5

7 3

19

1

1 を挿入すると

…

バランスが崩れて、

AVL

木でなくなった。

(

のノードの左部分木と右部分木

) 90

ページ

a)

15

17

(6)

17

9 21

23 13

11 5

7 3

19

1 9 とを入れ替える（回転する）。 17

17 9

21

23 13

11 5

7 3

19 1

15

(7)

17

9 21

13 23 11

5

7 3

19

91

ページ

c)

15

17

9 21

23 13

11 5

7 3

19

10 10 を挿入すると

…

AVL

15

(8)

17 9

21

23 13

11 5

7 3

19 10

1

回転してもダメ

15

17 9

21 13

11

5 15

を根に置くことにして、

２回転します。

13

17

9 21

23 13

11 5

7 3

19

10 10 を挿入すると

…

AVL

15

(9)

削除の場合

1.   通常の２分探索木として頂点を削除 2.   削除した結果の木が、

AVL 木の条件を満たさない場合

Ø  木の形が９０ページ a) では一重回転 Ø  木の形が９１ページ c) では二重回転

Ø   教科書９８ページにも、そう書いてある。

Ø  挿入にせよ削除にせよ、結果の木の形で

再構成の要・不要を判断する。ということ。

(10)

B 木（ B-tree ） 

Ø  二分木ではないが、探索用のｍ分木 Ø   いわゆる平衡木

Ø   順序木である

Ø   B 木を構成するためのルール

Ø  根から葉までの深さはどの葉についても同じである Ø  各頂点（葉以外）の子の数は最大 m である

Ø  各頂点（葉以外）の子の数は最小である

Ø 

は切り上げを意味する記号である

Ø 

根は例外で、最小

2

である

(11)

頂点の構造

頂点にはデータは置かない探索キーだけをおく

キーは枝をたどるときの境目

(12)

B 木の探索 

Ø  途中の頂点にはデータは入ってない

Ø  入ってる値は部分枝の選択のためのキー値 Ø  データは葉の部分におかれている

Ø 

そうしない実装もある

Ø  根から部分木を選択しながら下降する

Ø  部分木の選択には O(log m) 必要

Ø   葉に達したら探索は終了

Ø  葉の値と一致すれば成功、そうでなければ失敗

(13)

B 木の頂点に置く境界値 

•   頂点に置かれる値は部分木選択に使われる

•   境界値の条件は次の２つを満たす

–   左に位置する部分木の最大値以上 –   右に位置する部分木の最小値以下

•   条件を満たす値は複数あるがどれでもいい

境界値の左部分木境界値の右部分木境界値

(14)

7 31

3 6 22 29 49 - -

0 3 6 7 22 29 31 49

7未満の数 7以上31未満の数 31以上の数

• 未満, less than, より小さい

• 以上, greater than or equal to

29

を探索

3 44

を探索を探索

探索失敗

(15)

新しいデータ（子）を追加するとき

1.  追加すべき位置（親の頂点）を決定します 2.  親の頂点に空きがあるか調べます

3.  空きがない場合は親の頂点を分割します  親の親の頂点から新たに枝を増やします 

親が根である場合は、新たな根を親の親として増やします 4.  子を頂点に追加します

(16)

データ（子）を削除するとき

1.  削除すべきデータを探索し、削除します

2.  親からの枝の本数が最少数を満たすかどうか調べます 3.  最少数に満たない場合は隣の頂点と子を按分します 

按分した結果最少数を満たせない場合は隣の頂点と併合します  親が根である場合に最少数２を割ったら、根を削除します

(17)

計算量の考察 

•   キー値の比較を 1 回行うと候補は半減する

–   候補が半減する場合がもっとも効率が良い –   半減するようにデータを保持する

•  

例：平衡木を使う

•   ちょうど半分ずつ絞りこめば O(log N)

•   キーの比較という手法を使う限りはこれ以

上探索の効率はよくならない。

(18)

17 9

21

23 13

11 5

7

3 10 19

８ページ下の図からを削除します。

15

1.  AVL

木としてバランスが取れなくなりました。どのノードの左部分木と右部分木の高さが規定外なのでしょうか？

アルゴリズムとデータ構造