講義「アルゴリズムとデータ構造」

(1)

講義「アルゴリズムとデータ構造」

第６回探索のためのデータ構造（１）

大学院情報科学研究院情報理工学部門情報知識ネットワーク研究室

喜田拓也

2019/5/22 講義資料

(2)

今日の内容

探索

^※

のためのデータ構造

整列済み配列による辞書の実現二分探索木による辞書の実現平衡探索木による辞書の実現

※

探索：データの中から，特定の要素を探し出すこと

2

(3)

探索のためのデータ構造：辞書 (dictionary)

次の３つの基本操作を伴う集合

𝑆𝑆

を辞書（

dictionary

）という

1. member( 𝑥𝑥 , 𝑆𝑆 ): 𝑥𝑥 ∈ 𝑆𝑆

ならば

yes, 𝑥𝑥 ∉ 𝑆𝑆

ならば

no

を出力

2. insert( 𝑥𝑥 , 𝑆𝑆 ): 𝑆𝑆

を

𝑆𝑆 ∪ 𝑥𝑥

に更新

3. delete( 𝑥𝑥 , 𝑆𝑆 ): 𝑆𝑆

を

𝑆𝑆 − 𝑥𝑥

に更新

調べたり新しい項目を書き入れたり項目を消したり（汗

3

(4)

整列済み配列による辞書の実現

以降，集合

𝑆𝑆

は全順序集合であると仮定する配列

𝐴𝐴

に

𝑆𝑆

の要素を小さい順に格納する

member( 𝑥𝑥, 𝑆𝑆 )

：配列上を二分探索する

insert( 𝑥𝑥, 𝑆𝑆 )

：

𝑥𝑥

が入る位置を見つけたら，

それ以降の要素を後ろにずらして，できた空きに

𝑥𝑥

を入れる

delete( 𝑥𝑥, 𝑆𝑆 )

：

𝑥𝑥

の位置を見つけたら，それ以降の要素を一つずつ前に詰めていく．

𝑆𝑆

の最後の要素は空きとなる

delete( 7, 𝑆𝑆 )

の処理

1 3 5 7 9 10 12

最悪時間計算量

O log 𝑛𝑛

次で説明

O 𝑛𝑛

1 3 5 9 9 10 12 1 3 5 9 10 10 12 1 3 5 9 10 12 12 1 3 5 9 10 12

𝑆𝑆

コピー

削除

𝐴𝐴

は整列（ソート）済み配列

4

(5)

配列を二分探索するアルゴリズム

Step 1: left ← 0 , right ← 𝑛𝑛

Step 2: left ≥ right

なら

no

を出力して停止

Step 3: mid ← ⌊ (left + right)/ 2⌋

Step 4: if 𝑥𝑥 < 𝐴𝐴 [mid]

then right ← mid

else if 𝑥𝑥 = 𝐴𝐴 [mid]

then yes

else left ← mid +1

Step 2

へ

１回で範囲を半分以下に絞れるので，

𝑘𝑘

回で範囲を

𝑛𝑛/2

^𝑘𝑘以下に絞れる範囲が空となったら終わりだから

𝑛𝑛/2

^𝑘𝑘

< 1

．よって

log

₂

𝑛𝑛 < 𝑘𝑘

．

これを満たす最小の整数

𝑘𝑘

は

⌊ log

₂

𝑛𝑛 + 1⌋

このループは高々

⌊ log

₂

𝑛𝑛 + 1⌋

回

member( 5, 𝑆𝑆 )

の場合

1 3 5 7 9 10 12

𝑆𝑆

left mid right

1 3 5 7 9 10 12 0 1 2 3 4 5 6 7

1 3 5 7 9 10 12

yes

0 1 2 3 4 5 6 7

5

(6)

二分探索木による辞書の実現

二分木（

binary tree

）とは，各節点が高々二つの子をもつ根付き木

二分探索木（

binary search tree

）とは，任意の節点

𝑢𝑢

に対して次の条件が成り立つ二分木のこと

2

分木の例

2

分探索木の例

根

𝑢𝑢 𝑢𝑢

の子

𝑣𝑣

の親

7

3 10

1 4

5

8 6

𝑢𝑢

の

左部分木

𝑢𝑢

の

右部分木

5

3 7

1 4

8 6 10

同じ要素が格納された異なる二分探索木

𝑢𝑢

の左部分木の任意

の節点の要素＜

𝑢𝑢

の要素＜

𝑢𝑢

の右部分木の任意の節点の要素

子が１個の場合もある

この二分探索木を使って全順序集合

𝑆𝑆

を管理し，辞書とする

6

(7)

二分探索木における member( 𝑥𝑥, 𝑆𝑆 ) 操作

Step 1: 𝑢𝑢 ←

根の節点

Step 2: 𝑦𝑦 ←

節点

𝑢𝑢

の要素

Step 3: if 𝑥𝑥 = 𝑦𝑦 then

yes

else if 𝑥𝑥 > 𝑦𝑦 then

if 𝑢𝑢

の右の子が存在

then

𝑢𝑢 ← 𝑢𝑢

の右の子

else

no

else if 𝑢𝑢

の左の子が存在

then

𝑢𝑢 ← 𝑢𝑢

の左の子

else

no

Step 2

へ

member( 5, 𝑆𝑆 )

の場合

7

3 10

1 4

5

8 6

yes

5 <

< 5

< 5 5 <

5 =

𝑢𝑢

𝑥𝑥 ≤ 𝑦𝑦

member( 9, 𝑆𝑆 )

の場合

7

3 10

1 4

5

8 6

𝑢𝑢

< 9

9 <

< 9

no

7

(8)

二分探索木における insert (𝑥𝑥 , 𝑆𝑆) 操作

Step 1: 𝑢𝑢 ←

根の節点

Step 2: 𝑦𝑦 ←

節点

𝑢𝑢

の要素

Step 3: if 𝑥𝑥 = 𝑦𝑦 then

何もしないで停止

else if 𝑥𝑥 > 𝑦𝑦 then

if 𝑢𝑢

の右の子が存在

then

𝑢𝑢 ← 𝑢𝑢

の右の子

else

𝑢𝑢

の右の子として

𝑥𝑥

を要素とする節点を追加して停止

else if 𝑢𝑢

の左の子が存在

then

𝑢𝑢 ← 𝑢𝑢

の左の子

else

𝑢𝑢

の左の子として

𝑥𝑥

を要素とする節点を追加して停止

Step 2

へ

insert( 9, 𝑆𝑆 )

の場合

赤字の部分が

member( 𝑥𝑥, 𝑆𝑆 )

操作と違うところ

7

3 10

1 4

5

8 6

𝑢𝑢

< 9

9 <

< 9 9 追加

8

(9)

二分探索木における delete( 𝑥𝑥, 𝑆𝑆 ) 操作

Step 1: 𝑢𝑢 ←

根の節点

Step 2: 𝑦𝑦 ←

節点

𝑢𝑢

の要素

Step 3: if 𝑥𝑥 = 𝑦𝑦 then Step 4

へ

else if 𝑥𝑥 > 𝑦𝑦 then

if

右の子が存在

then 𝑢𝑢 ←

右の節点

else

else if

左の子が存在

then 𝑢𝑢 ←

左の節点

else

Step 2

へ

Step 4: if 𝑢𝑢

は葉

then 𝑢𝑢

を木から除いて停止

else if 𝑢𝑢

が１つの子をもつ

then 𝑢𝑢

の子を

𝑢𝑢

の位置に上げて停止

else 𝑣𝑣 ← 𝑢𝑢

の右部分木の最小要素をもつ節点

Step 5: 𝑢𝑢

の要素

← 𝑣𝑣

の要素

Step 6: if 𝑣𝑣

は葉

then 𝑣𝑣

を木から除いて停止

else ( 𝑣𝑣

が１つの子を持つ場合

)

𝑣𝑣

を

𝑢𝑢

の位置に上げて停止

^𝑣𝑣

^{は部分木の最小要}

素をもつ節点なので子の数は高々１つ

これ以降は

𝑢𝑢

が２つの子をもつ場合

𝑆𝑆

中に

𝑥𝑥

が無ければ何もしない

9

(10)

二分探索木における delete( 𝑥𝑥, 𝑆𝑆 ) 操作の例

7

3 10

1 4

5

8 6 5 <

< 5

< 5 5 <

5 =

𝑢𝑢

delete( 5, 𝑆𝑆 )

の場合

7

3 10

1 4

5

8 6 4 <

< 4

= 4

𝑢𝑢

delete( 4, 𝑆𝑆 )

の場合

7

3 10

1 4

5

8 6

7

3 10

1 5

8 6

7

3 10

1 4

5

8 6 7 =

delete( 7, 𝑆𝑆 )

の場合

𝑢𝑢

𝑣𝑣

8

3 10

1 4

5

8 6

7

3 10

1 4

5

8 6 3 <

= 3

𝑢𝑢

delete( 3, 𝑆𝑆 )

の場合

𝑣𝑣

7

4 10

1 5

6 8

10

(11)

二分探索木に対する操作の時間計算量

𝑛𝑛

要素の二分探索木に対する各操作の計算時間は，

𝑥𝑥 ∈ 𝑆𝑆

の場合，

𝑥𝑥

を要素としてもつ節点の深さ^※に比例する

𝑥𝑥 ∉ 𝑆𝑆

の場合，

insert( 𝑥𝑥, 𝑆𝑆 )

を行うことによってできる

𝑥𝑥

を要素としてもつ節点の深さ

−1

に比例する

最悪時間計算量は

O(𝑛𝑛)

，平均時間計算量は

O log 𝑛𝑛

大きい順に格納

※𝑥𝑥 が２つの子を持つ場合のdelete(𝑥𝑥,𝑆𝑆)は，𝑥𝑥 の右部分木の最小要素の節点𝑣𝑣 の深さにも比例

4 3 2 1

最悪な場合（木の深さ

= 𝑛𝑛 − 1

）最良の場合（木の深さ

= log 𝑛𝑛

）

4 3 2 1

小さい順に格納

5

5 4

2

1 3

6

6 6

節点の深さの期待値は

O log 𝑛𝑛

11

(12)

深さの期待値が O log 𝑛𝑛 である証明

（証明）二分探索木の全ての節点がちょうど２つの子をもつように

𝑛𝑛 + 1

個の節点を加える．

もとの節点を内点，新しく加えた節点を外点と呼ぶ．

「外点の深さの平均」

≥

「内点の深さの平均」

であるから外点の深さの平均が

O log 𝑛𝑛

であることを示せばよい．

7

3 10

1 4

5

8 6

内点

外点

トーナメントの試合数を考えてみよう

0 1 2 3 4 5

節点の深さ＝

根からの路の長さ

12

(13)

証明つづき

𝐷𝐷 𝑛𝑛

を外点の深さの平均とする．

最初に格納されるものが

𝑖𝑖

番目の大きさである確率を

1/𝑛𝑛

（等確率）とすれば，

𝐷𝐷 𝑛𝑛 = 1 𝑛𝑛 �

𝑖𝑖=1

𝑛𝑛

𝑖𝑖 𝐷𝐷 𝑖𝑖 − 1 + 1 + (𝑛𝑛 − 𝑖𝑖 + 1)(𝐷𝐷 𝑛𝑛 − 𝑖𝑖 + 1) 𝑛𝑛 + 1

= 2

𝑛𝑛 𝑛𝑛 + 1 �

𝑖𝑖=1 𝑛𝑛

𝑖𝑖𝐷𝐷(𝑖𝑖 − 1) + 1

= 2

𝑛𝑛 𝑛𝑛 + 1

2 𝑛𝑛 𝑛𝑛 − 1 �

𝑖𝑖=1 𝑛𝑛−1

𝑖𝑖𝐷𝐷 𝑖𝑖 − 1 + 1 𝑛𝑛 𝑛𝑛 − 1

2 − 𝑛𝑛 𝑛𝑛 − 1

2 + 𝑛𝑛𝐷𝐷 𝑛𝑛 − 1 + 1

= 𝐷𝐷 𝑛𝑛 − 1 + 2 𝑛𝑛 + 1

外点の数

=

内点の数＋１

𝐷𝐷(𝑛𝑛 − 1)

内点が

𝑖𝑖 − 1

個

内点が

𝑛𝑛 − 𝑖𝑖

個根の要素の大きさが

𝑖𝑖

番目

𝐷𝐷 𝑖𝑖 − 1

左側の総深さ右側の総深さ

𝑖𝑖𝐷𝐷 𝑖𝑖 − 1

と

𝑛𝑛 − 𝑖𝑖 + 1 𝐷𝐷(𝑛𝑛 − 𝑖𝑖)

は

𝑖𝑖

に対して対称なので

𝑖𝑖 = 𝑛𝑛

のところを抽出して分解

13

(14)

証明つづき

よって，

𝐷𝐷(𝑛𝑛) − 𝐷𝐷(𝑛𝑛 − 1) = 2/(𝑛𝑛 + 1)

となる．

𝐷𝐷 0 = 0

であるから，

𝐷𝐷 𝑛𝑛 = 2 �

𝑖𝑖=2 𝑛𝑛+1 1

𝑖𝑖 ≤ 2 �

1 𝑛𝑛+1 1

𝑥𝑥 𝑑𝑑𝑥𝑥 = 2 log _𝑒𝑒 (𝑛𝑛 + 1)

したがって

𝐷𝐷 𝑛𝑛 = O log 𝑛𝑛

である．【証明終わり】

調和級数の部分和

…

1/2 1

1/3

1 2 𝑛𝑛 𝑛𝑛 + 1

𝑦𝑦 = 1 𝑥𝑥 𝑦𝑦

𝑥𝑥

₁₄

(15)

平衡探索木（ balanced search tree ）

各節点において，その子を根とする全ての部分木の高さがほぼ平衡している探索木

AVL

木どの節点においても，その左部分木と右部分木の高さの差が１以下である二分探索木

AVL

は提唱者（

Adel’son-Vel’skii

と

Landis

）の頭文字

2

色木二分探索木の各辺に次の条件を満たすように赤か黒の

色を塗れるもの

1.

外点に接続する辺の色は黒

2.

根から外点までのどの路も赤い辺が連続しない

3.

根から外点までのどの路も含む黒い辺の数が同じ

B

木根と葉を除く各節点が

𝑚𝑚/2

個以上，

𝑚𝑚

個以下の子を持

つ探索木（

𝑚𝑚

は自然数）

2-3

木

𝑚𝑚 = 3

の場合の

B

木

1 ≥

15

(16)

AVL 木における insert( 𝑥𝑥, 𝑆𝑆 ) 操作

𝑇𝑇 _𝐿𝐿 ^𝑢𝑢

を節点

𝑢𝑢

の左部分木，

𝑇𝑇 _𝑅𝑅 ^𝑢𝑢

を

𝑢𝑢

の右部分木，

𝑠𝑠(𝑢𝑢)

を

𝑢𝑢

の状態とする

挿入前の

𝑠𝑠(𝑢𝑢)

は次のように設定されている．

𝑆𝑆 𝑢𝑢 = � 𝐿𝐿, 𝑇𝑇 _𝐿𝐿 ^𝑢𝑢

の高さ

> 𝑇𝑇 _𝑅𝑅 ^𝑢𝑢

の高さの場合，

𝐸𝐸, 𝑇𝑇 _𝐿𝐿 ^𝑢𝑢

の高さ

= 𝑇𝑇 _𝑅𝑅 ^𝑢𝑢

の高さの場合，

𝑅𝑅, 𝑇𝑇 _𝐿𝐿 ^𝑢𝑢

の高さ

< 𝑇𝑇 _𝑅𝑅 ^𝑢𝑢

の高さの場合．

Step 1:

二分木と同様に挿入を行う．挿入した節点の親を

𝑢𝑢

とする

Step 2: 𝑠𝑠 𝑢𝑢 ≠ 𝐸𝐸

となるまで次のことを繰り返す

1. 𝑠𝑠 𝑢𝑢

を，挿入して高くなった方（

𝐿𝐿

か

𝑅𝑅

）に更新

2. 𝑢𝑢 ← 𝑢𝑢

の親

Step 3: if 𝑠𝑠 𝑢𝑢 = 𝑅𝑅

かつ

𝑇𝑇

_𝐿𝐿^𝑢𝑢 が高くなった

or 𝑠𝑠 𝑢𝑢 = 𝐿𝐿

かつ

𝑇𝑇

_𝑅𝑅^𝑢𝑢 が高くなった

then

𝑠𝑠 𝑢𝑢 ← 𝐸𝐸

として停止

else

回転して停止

左が高い

右が高い

挿入したことによる祖先のラベル変更

ここの処理は定数時間

16

(17)

AVL 木における挿入（左）に伴う回転操作

𝑢𝑢 𝑣𝑣

𝐸𝐸 ⇒ 𝐿𝐿

𝐿𝐿 𝑢𝑢

𝑣𝑣 𝐸𝐸

𝐸𝐸

回転

11

1

回転

1

𝑢𝑢

𝑤𝑤

𝐸𝐸 ⇒ 𝐿𝐿 𝑅𝑅 _𝑣𝑣

𝐿𝐿 ^𝑢𝑢

𝑤𝑤 𝐸𝐸

𝐸𝐸 _𝑣𝑣 𝑅𝑅

𝑠𝑠 𝑣𝑣 = 𝐿𝐿

の場合

𝑠𝑠 𝑣𝑣 = 𝑅𝑅

の場合

𝑇𝑇

_𝐿𝐿^𝑤𝑤

< 𝑇𝑇

_𝑅𝑅^𝑤𝑤 の場合もある 17

(18)

AVL 木における delete( 𝑥𝑥, 𝑆𝑆 ) 操作

Step 1:

一般の二分木の同じように削除を行う．

削除した最も下の節点の親を

𝑢𝑢

とする．

Step 2: 𝑠𝑠 𝑢𝑢 = 𝐸𝐸

となるまで次のことを繰り返す．

1. if 𝑠𝑠 𝑢𝑢 = 𝐿𝐿

かつ

𝑇𝑇

_𝐿𝐿^𝑢𝑢 が低くなった

or 𝑠𝑠 𝑢𝑢 = 𝑅𝑅

かつ

𝑇𝑇

_𝑅𝑅^𝑢𝑢 が低くなった

then 𝑠𝑠(𝑢𝑢) ← 𝐸𝐸

else if 𝑠𝑠 𝑢𝑢 = 𝑅𝑅

かつ

𝑇𝑇

_𝐿𝐿^𝑢𝑢 が低くなった

or 𝑠𝑠 𝑢𝑢 = 𝐿𝐿

かつ

𝑇𝑇

_𝑅𝑅^𝑢𝑢 が低くなった

then (1)

回転

(2) 𝑠𝑠 𝑢𝑢 ≠ 𝐸𝐸

ならば停止

2. 𝑢𝑢 ← 𝑢𝑢

の親

Step 3: 𝑠𝑠 𝑢𝑢

を，低くなった方の逆（

𝐿𝐿 or 𝑅𝑅

）に更新

高々，木の高さの回数しか繰り返さない回転処理は

定数時間

18

(19)

11 11

AVL 木における削除（左）に伴う回転操作

𝑣𝑣 𝑢𝑢 𝑅𝑅

𝐸𝐸

𝑣𝑣

𝑅𝑅 𝑢𝑢

𝐿𝐿

高さ変化せず

𝑣𝑣 𝑢𝑢 𝑅𝑅

𝑅𝑅

𝑣𝑣

𝐸𝐸 𝑢𝑢

𝐸𝐸

高さ

1

減少

回転

𝑠𝑠 𝑣𝑣 = 𝐸𝐸

の場合

𝑠𝑠 𝑣𝑣 = 𝑅𝑅

の場合

19

(20)

AVL 木における削除（左）に伴う回転操作

高さ１減少

𝑠𝑠 𝑣𝑣 = 𝐿𝐿

の場合

𝑢𝑢

𝑤𝑤

𝑅𝑅 𝐿𝐿 𝐸𝐸 𝑣𝑣

11

𝑢𝑢

𝑤𝑤 𝐸𝐸

𝐸𝐸 𝐸𝐸 𝑣𝑣

回転

20

(21)

AVL 木に対する操作の時間計算量

𝑛𝑛

要素の

AVL

木に対する各操作の計算時間は，

最悪時間計算量は

O(log 𝑛𝑛)

，平均時間計算量は

O log 𝑛𝑛

AVL

木のどの操作も，木の高さに比例した時間しかかからない．

𝑛𝑛

節点の

AVL

木の高さは

O log 𝑛𝑛

21

(22)

AVL 木の高さが O log 𝑛𝑛 の証明

𝑓𝑓 ℎ

を高さ

ℎ

の

AVL

木の最小節点数とすれば，以下の漸化式が成り立つ．

𝑓𝑓(ℎ) = 𝑓𝑓(ℎ − 1) + 𝑓𝑓(ℎ − 2) + 1

，

𝑓𝑓(0) = 1

，

𝑓𝑓(1) = 2

．

𝐹𝐹 ℎ = 𝑓𝑓 ℎ + 1

とすれば，

𝐹𝐹 ℎ = 𝐹𝐹 ℎ − 1 + 𝐹𝐹 ℎ − 2

，

𝐹𝐹 (0) = 2

，

𝐹𝐹 (1) = 3

．すると，

𝐹𝐹 ℎ

はフィボナッチ数列なので，

𝐹𝐹(ℎ) = 𝜑𝜑 ₁ ^ℎ+3 − 𝜑𝜑 ₂ ^ℎ+3 5

ただし，

𝜑𝜑 ₁ = ^{1+ 5} ₂

，

𝜑𝜑 ₂ = ^{1− 5} ₂

である．

高さ

ℎ

の節点数最小の

AVL

木

高さ

ℎ − 1

の節点数最小の

AVL

木高さ

ℎ − 2

の

節点数最小の

AVL

木

根だけの木

22

(23)

証明つづき

高さ

ℎ

の

AVL

木の節点数を

𝑛𝑛

とすれば，

𝑓𝑓 (ℎ)

はその下限なので，

𝑓𝑓 ℎ ≤ 𝑛𝑛

である．よって，

𝜑𝜑 ₁ ^ℎ+3 − 𝜑𝜑 ₂ ^ℎ+3 ≤ 5 𝑛𝑛 + 1

．

𝜑𝜑 ₂ < 1

なので，

𝜑𝜑 ₁ ^ℎ+3 − 1 ≤ 5 𝑛𝑛 + 1

．よって，

ℎ ≤ log 5 𝑛𝑛 + 1 + 1

log 𝜑𝜑 ₁ − 3

．

したがって，

ℎ = 𝑂𝑂 log 𝑛𝑛

である．【証明終わり】

∵ 𝜑𝜑

₁^ℎ+3

− 𝜑𝜑

₂^ℎ+3

5 = 𝑓𝑓 ℎ + 1

23

(24)

今日のまとめ

探索のためのデータ構造である辞書の実現方法を学んだ整列済み配列による辞書の実現

member

は最悪時間計算量

O(log 𝑛𝑛) insert

と

delete

は

O(𝑛𝑛)

かかる

二分探索木による辞書の実現最悪時間計算量

O 𝑛𝑛

平均時間計算量

O log 𝑛𝑛

平衡探索木による辞書の実現

最悪時計算量も平均時間計算量も

O log 𝑛𝑛

24

講義「アルゴリズムとデータ構造」