算法数理工学 第4回 定兼　邦彦

2分探索木とは何か? 各節点は key, left, right, p フィールドを持つ 2分探索木条件 (binary-search-tree property) 節点 y が x の左部分木に属する⇒ key[y]key[x] 節点 y が x の右部分木に属する⇒ key[x]key[y] 5 2 3 7 8 5 2 3 7 8

ランダムに構成された2分探索木 2分探索木上の基本操作は O(h) 時間で実行可 要素の挿入削除を繰り返すと探索木の高さ h は変化する n 個の相異なるキーをランダムな順序で挿入した2分探索木の高さを解析する 高さの期待値は O(lg n)

仮定 確率変数の定義 入力キーの n! 種類の順列がどれも等確率で出現する 全てのキーは異なる Xn: n 個のキー上のランダムに構成された2分探索木の高さ Yn = 2Xn 指数高さ Rn: n 個のキーの中での根のキーの順位 (rank) Rn = i なら，根の左部分木は i1 個のキー上の ランダムに構成された2分探索木，右部分木は ni 個のキー上のランダムに構成された2分探索木

2分探索木の高さは根の左右の部分木の高さの 大きいほう+1． Rn = i のとき Y1 = 1. 便宜上 Y0 = 0 と定義する. 指標確率変数 を次のように定義 Rn の値は {1,2,…,n} の任意の要素を等確率で 取るから，Pr{Rn = i} = 1/n (i=1,2,…,n) よって

根の順位が i のときだけ Zn,i = 1 になるから E[Yn] が多項式であることが示せれば， E[Xn] が O(lg n) であることが示せる． Zn,i は Yi1 とも Yni とも独立 根の左部分木内の各要素は根よりも小さい，つまり 順位が i より小さい i1 個のキー上のランダムに構成 された木である． この部分木は順位の制約がないi1 個のキー上のランダムな木と同じ 部分木の高さ Yi1 と根の順位 Zn,i は独立

を示す

関数 f(x) = 2x は下に凸であるから 以上より 定理 n 個のキー上のランダムに構成された2分探索木の高さの期待値は O(lg n).

2色木 2分探索木は，基本的な動的集合操作を 木の高さに比例する時間で実現できる 2分探索木は，基本的な動的集合操作を 木の高さに比例する時間で実現できる 探索木の高さは要素の挿入順に依存し， 最悪の場合は O(n) になる 2色木は，基本操作が最悪でも O(lg n)時間になるような探索木の1つである

2色木条件 各節点に1ビットの情報(色)を加えた2分探索木 各節点は赤または黒の色がついている 各節点の要素 color, key, left, right, p 外部節点 (葉) は NIL で表される 内部節点のみが key を持つ

2色木条件 (Red-Black Property) 2分探索木が下記の2色木条件を満たすならば，2色木である． 各節点は赤か黒のどちらか 葉 (NIL) は全て黒 もしある節点が赤ならば，その子供は両方黒 1つの節点からその子孫の葉までのどの単純な経路も，同じ数だけ黒節点を含む．

ある節点 x から葉までの経路上の黒節点の数 (x は含まない) を黒高さと呼び，bh(x) で表す 3 26 3 17 2 41 2 14 2 21 2 30 1 47 2 10 1 16 1 19 1 23 1 28 1 38 NIL NIL 1 7 1 12 1 15 20 1 35 1 39 NIL NIL NIL NIL NIL NIL 1 3 NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL ある節点 x から葉までの経路上の黒節点の数 (x は含まない) を黒高さと呼び，bh(x) で表す

補題 n 個の内点をもつ2色木の高さは高々 2 lg (n+1) である 証明: まず，任意の節点 x を根とする部分木は少なくとも 2bh(x)  1 個の内点を含むことを示す． x の高さが 0 のとき，x は葉で，x を根とする部分木 は少なくとも 2bh(x)  1 = 20  1 = 0 個の内点を含む． 高さ h  0 以下の全ての木で成り立つとする．高さ h+1 の木の根 x は2つの子供を持ち，それぞれ bh(x) または bh(x)1 の黒高さを持つ．各子供は少なくとも 2bh(x)1  1 個の内点を持つため，x は少なくとも (2bh(x)1  1)+(2bh(x)1  1)+1= 2bh(x)  1 個の内点を含む．よって高さ h+1 の木でも成り立つ

証明の続き: 木の高さを h とする．条件3より，根から葉までの どの経路上の根以外の節点の少なくとも半分は黒． よって，根の黒高さは少なくとも h/2． 上の命題より n  2h/21，つまり h  2 lg (n+1). この補題より，SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR はO(h) = O(lg n)時間で終わることがわかる INSERT, DELETEは2色木条件を壊すため，アルゴリズムを変更する必要あり

回転 2色木で節点を追加/削除すると2色木の条件を満たさなくなることがある． 条件を満たすように木の構造を変更する  < x <  < y <  の順を保つ RIGHT_ROTATE(T,y) y x y x   LEFT_ROTATE(T,x)    

7 11 4 6 3 2 9 18 14 12 17 19 22 20 x y  LEFT_ROTATE(T,x)  7 11 4 6 3 2 9 18 14 12 17 19 22 20 y  x

O(1) 時間 LEFT_ROTATE(tree T, node x) { node y; y = right(x); right(x) = left(y); if (left(y) != NIL) p(left(y)) = x; p(y) = p(x); if (p(x) == NIL) { root(T) = y; } else { if (x == left(p(x)) left(p(x)) = y; else right(p(x)) = y; } left(y) = x; p(x) = y; x y    y x  O(1) 時間  

新しい節点の挿入 keyに従って節点 x を葉に挿入する x の色を赤にする x を挿入後の2色木条件 各節点は赤か黒のどちらか…OK 葉 (NIL) は全て黒…OK もしある節点が赤ならば，その子供は両方黒…? 1つの節点からその子孫の葉までのどの単純な経路も，同じ数だけ黒節点を含む…OK x の親が赤のときは条件3を満たさない⇒回転操作

挿入後の回転操作 x の親 z が赤である間以下を繰り返す z の兄弟 y が赤のとき: z と y を黒，x をそれらの親とし，赤にする y が黒で x が左の子のとき: x の親を黒，その親を赤にして右回転

場合1 z の兄弟 y が赤のとき 11 2 14 1 7 z 15 5 8 y x 4 11 2 14 x 7 1 15 5 8 4

場合2 y が黒で x が右の子のとき 11 z 2 y 14 x 7 1 15 5 8 4 11 7 y 14 x 8 2 15 5 1 4

場合3 y が黒で x が左の子のとき 11 z 7 y 14 x 8 2 15 5 1 4 7 11 x 2 8 5 14 1 4 15

場合1: z の兄弟 y が赤のとき z の親 w は黒 (元の木では赤は連続しない) y, z の子孫の節点の黒深さは変化しない new x の親が赤の可能性があるため繰り返す new x w C C z y A D A D x      B  B    

場合2: y が黒で x が右の子のとき z で左回転を行う⇒ x は左の子になる 場合3に移る w C C y y z A B D D x x A  B     

場合3: y が黒で x が左の子のとき p(p(x)) で右回転を行う 各部分木で黒高さは保存される 赤節点が連続することはない⇒終了 C B y z x C B A D y x A   D    

計算量 2色木の高さは O(lg n) TREE_INSERTは O(lg n) 時間 RB_INSERTでのwhileループでは x のポインタは木を登っていく ループの実行回数は木の高さ以下⇒ O(lg n) ループ内の処理は定数時間 全体でも O(lg n) 時間，高々2回の回転

削除 探索木から節点 z を削除する z が子を持たない場合 z が子を1つ持つ場合 z の親 p(z) を変更する 2 5 3 z 5 7 8 z y x

削除: z が子を2つ持つ場合 z の次節点は左の子を持たない z の場所に y を入れ，元の y を削除する 5 10 3 12 13 15 z 6 7 y 6 10 3 12 13 15 7 x

2色木の修正 削除される節点を y, その子の1つを x とする y が黒のとき，削除すると y を含んでいたどの経路も黒高さが1減る

場合1: x の兄弟 w が赤 B で左回転 B と D の色を変える x の兄弟が黒になる⇒場合2 D B E w x D B A     C E x C A new w        

場合2: w の左右の子が黒 D の色を変える B が赤ならそれを黒にして終了 B が黒なら B を新しい x として繰り返す new x A A   C E   C E        

場合3: w の右の子が黒 D で右回転 C と D の色を変える⇒場合4 B B new w C x A w x D A D          

場合4: w の右の子が赤 B で左回転 B, D, E の色を変える⇒終了 c c D B E w B x D A c’   c’   C C E A         new x = root(T)

RB_DELETEの計算時間 TREE_DELETEは O(lg n) 時間 場合1, 3, 4は定数時間，最大3回の回転 場合3,4に行くとそこで終了 場合1から2へ移った場合，新しい x は赤なので終了 場合2では回転は行わず，O(lg n) 回木を登る 全体で O(lg n) 時間，高々3回の回転

ハッシュ表 辞書操作 (INSERT, DELETE, SEARCH) を効率よく実現するデータ構造 キー：変数名などの文字列 ハッシュ表は実際的な場面では極めて速い 妥当な仮定の下で，SEARCHの時間の期待値は O(1) 最悪の場合 (n)

直接アドレス表 出現する可能性のあるキーの全集合 (普遍集合, universal set) が大きくない場合にうまく働く キーが普遍集合 U = {0,1,, m1} から選択され，どの2つの要素も同じキーをもたないと仮定する 直接アドレス表 (direct-access table) T で動的集合を表現する 配列 T[0..m1] の各要素が U のキーに対応 T[k] は，キー k を持つ要素をさす．そのような要素がなければ T[k] = NIL T[k] をスロット k と呼ぶ

T 1 キー 付属データ U (キーの普遍集合) 2 2 3 4 7 6 3 9 4 1 5 K (実際 のキー) 5 2 6 5 7 3 8 8 8 9

辞書操作の実現 DIRECT_ADDRESS_SEARCH(T,k) DIRECT_ADDRESS_INSERT(T,x) return T[k] DIRECT_ADDRESS_INSERT(T,x) T[key(x)] = x DIRECT_ADDRESS_DELETE(T,x) T[key(x)] = NIL いずれも O(1) 時間 T にオブジェクトそのものを格納してもいい

直接アドレス表の欠点 キーの普遍集合 U が大きい場合は非現実的 表 T をメモリに格納できない T に割り付けた領域のほとんどが無駄になる 辞書に格納されているキーの集合 K が U に比べて十分に小さい場合はハッシュ表が有効

ハッシュ表 直接アドレス表では，キー k はスロット k に格納 ハッシュ表 T[0..m1] では，スロット h(k) に格納 h: ハッシュ関数 (hash function) h: U  {0,1,,m1} 必要な領域: (|K|) 要素の探索: O(1) (平均時間)

ハッシュ関数の衝突 衝突 (collision): 2つのキーが同じスロットにハッシュされること T h(k2) U (キーの普遍集合) のキー) k1 h(k3) = h(k4) k3 k4 k2

衝突の回避方法 別のハッシュ関数を用いる |U| > m なので完全に回避することは不可能 チェイン法 オープンアドレス法

チェイン法による衝突解決 同じスロットにハッシュされたすべての要素を連結リストに格納 CHAINED_HASH_INSERT(T,x) リスト T[h(key(x))] の先頭に x を挿入, O(1) 時間 CHAINED_HASH_SEARCH(T,k) リスト T[h(k)] の中からキー k を持つ要素を探索 CHAINED_HASH_DELETE(T,x) リスト T[h(key(x))] から x を削除, 双方向リストを用いれば O(1) 時間

チェイン法を用いるハッシュ法の解析 SEARCHは最悪の場合 (n) 時間 平均時間を解析する スロット m 個, n 要素を格納するハッシュ表 T の負荷率 (load factor)  = n/m と定義  は1つのチェインに格納される要素数の平均 解析は  を変数として行う (n, m が共に無限大に近づくとき，  はある定数に留まるとする)

ハッシュ法の平均的性能 各要素は m 個のスロットに同じ程度にハッシュされると仮定する (単純一様ハッシュの仮定 simple uniform hashing) ハッシュ値 h(k) は O(1) 時間で計算できると仮定 キー k をもつ要素の探索は，リスト T[h(k)] の長さに比例した時間が必要

定理1 チェイン法を用いるハッシュ表で，単純一様ハッシュを仮定すると，失敗に終わる探索にかかる時間の平均は (1+ ) 証明 単純一様ハッシュを仮定すると，任意のキーは m 個の各スロットに同程度にハッシュされる． あるキーの探索が失敗するとき，その時間の平均は，1つのリストを最後まで探索する時間の平均． リストの長さの平均は負荷率  = n/m. よって検査される要素数の期待値は , 時間は (1+ )

定理2 チェイン法を用いるハッシュ表で，単純一様ハッシュを仮定すると，成功する探索にかかる時間の平均は (1+ ) 証明 INSERTにおいて，新しい要素はリストの末尾に挿入されると仮定する． 成功する探索で検査される要素数の期待値は， 見つかった要素が挿入されたときに検査された要素数+1. 表に格納されている n 個の要素について平均を取る.

i 番目の要素が付け加えられるときのリストの長さの期待値は (i1)/m 成功する探索に必要な時間は (1+ ) ハッシュ表中の要素数が n = O(m) のとき = n/m = O(m)/m = O(1) つまり，すべての辞書操作が平均 O(1) 時間

ハッシュ関数 良いハッシュの条件 = 単純一様ハッシュ 各キーは U から確率分布 P に従って独立に取り出されると仮定すると，条件は と書ける ただし，一般に P は未知 キーがランダムな実数k (0k1)で一様独立のとき, h(k) = km は上の条件を満たす

除算法 キー k を m で割った剰余をハッシュ値とする 利点: ハッシュ関数の計算が高速 m は 2 のべき乗に近くない素数がいい h(k) = k mod m 利点: ハッシュ関数の計算が高速 m は 2 のべき乗に近くない素数がいい m = 2p のとき，h(k) は k の最下位 p ビット m = 2p1 で k が基数 2p の文字列のとき，文字を並び替えてもハッシュ値は同じ

例 n = 2000 個の文字列を格納する場合 負荷率  を 3 に近くするには, m = 701 にすればいい 701 は素数で，2のべき乗には近くない h(k) = k mod 701 とすればいい このハッシュ関数が実際のデータでうまく働くことを確かめるべき

乗算法 まず，キー k にある定数 A (0 < A < 1) を掛け，その小数部分 kAkA を取り出す 次に，その値に m を掛け，小数部分を切り捨てる m の値はあまり重要ではない 2のべき乗にすると計算が簡単 が良いと言われる

オープンアドレス指定法 オープンアドレス指定法 (open addressing)では，要素は連結リストではなくハッシュ表の中に格納される． ハッシュ表が埋まるとそれ以上挿入できない 負荷率は1以下 連結リストを用いないため，スペースが小さい ハッシュ関数を拡張して衝突を回避する 引数: キーと探査番号 h: U  {0,1,...,m1}  {0,1,...,m1} 探査列 h(k,0), h(k,1),..., h(k,m1) は 0,1,...,m1 の順列でなければならない

要素の挿入 int HASH_INSERT(data *T, data k) { int i, j; i = 0; // i: 探査番号 do { j = h(k,i); if (T[j] == NIL) { // スロットが空なら T[j] = k; // 新しいデータを挿入 return j; } else { i++; // 探査番号を1増やす } } while (i != m); // m 回試す printf(“ハッシュ表オーバーフロー\n”);

要素の検索 int HASH_SEARCH(data *T, data k) { int i, j; i = 0; // i: 探査番号 do { j = h(k,i); if (T[j] = k) return j; // k を発見 i++; } while (T[j] != NIL && i != m); // スロットが空か，m 回探索した return NIL; // k は見つからなかった }

要素の削除 削除したい要素のあるスロットを NIL にすると，他の要素が検索できなくなる 削除するときは NIL でなく特別な値 DELETED を格納する SEARCHではDELETEDが現れても探索を続ける INSERTではNILまたはDELETEDの場所に挿入 問題点: 探索時間が負荷率  で表せない 要素を削除する必要がある場合はチェイン法が好まれる

衝突回避の方法 一様ハッシュ (uniform hashing) を仮定: 各キーに対する探査列として， {0,1,...,m1} の m! 通りの順列のどれもが同程度に現れる 近似的な一様ハッシュを用いる 線形探査 2次関数探査 ダブルハッシュ法

線形探査 通常のハッシュ関数 h’: U  {0,1,...,m1} に対し h(k,i) = (h’(k)+i) mod m (i=0,1,...,m1) を用いる 探査されるスロット: T[h’(k)], T[h’(k)+1],..., T[m1], T[0], T[1],..., T[h’(k)1] 異なる探査列は m 通りしかない (開始位置で決定) 問題点: 主クラスタ化 (primary clustering) が起きる 直前の i 個のスロットが使用中である空きスロットが選択される確率は (i+1)/m であるため，連続する使用中のスロットは常に大きくなる

2次関数探査 2次関数探査 (quadratic probing) では h(k,i) = (h’(k)+c1i+c2i2) mod m (i=0,1,...,m1) を用いる c1, c2, m は適切に選ぶ必要がある h(k1,0) = h(k2,0) の場合は h(k1,i) = h(k2,i) となってしまう (副クラスタ化, secondary clustering) 異なる探査列は m 通りしかない (開始位置で決定)

ダブルハッシュ法 h(k,i) = (h1(k)+i h2(k)) mod m h2(k) と m の最大公約数が d のとき，ハッシュ表の1/d しか検査しない 例1: m を2のべき乗，h2 は常に奇数 例2: m を素数， h2 は m 未満の非負整数 h2(k)=1+(k mod m’) (m2) 個の探査列が利用できる

オープンアドレスハッシュ法の解析 ハッシュ表の負荷率  をパラメータとして解析 一様ハッシュを用いると仮定する 定理 負荷率  =n/m<1 のオープンアドレスハッシュ表において，失敗に終わる探索に必要な探査数の期待値は 1/(1) 以下 証明 失敗に終わる探索では，最後の探査を除いて，毎回の探査では異なるキーを格納しているスロットにアクセスし，最後に未使用のスロットにアクセスする．

i = 0,1,... に対して， pi = Pr{未使用のスロットを見つけるまでちょうど i 回の探査を行った} qi = Pr{未使用のスロットを見つけるまで少なくとも i 回の探査を行った} と定義する．探査回数の期待値は 最初の探査が使用中のスロットにアクセスする確率は n/m であるから

一様ハッシュ法では，2回目の探査は残りの m1 個のスロットの1つに対して行われ，その中にはn1 個の使用中のスロットがあるため 一般に

失敗に終わる探索に必要な探査回数の期待値は が定数なら O(1) 時間で実行できる  = 0.5 なら 2回 以下  = 0.9 なら 10回 以下

系 一様ハッシュを仮定すると，負荷率のオープンアドレスハッシュ表に，ある要素を挿入するために必要な探査回数の平均は1/(1) 以下 証明 キーを挿入するには未使用スロットを発見する必要がある．その探査回数の期待値は失敗に終わる探索での探査回数の期待値に等しい．

定理 一様ハッシュを仮定し，表内の各キーは等確率で探索の対象になるとする．負荷率  のオープンアドレスハッシュ表において，成功に至る探索に必要な探査回数の期待値は 証明 キー k の探索は，それを挿入したときと同じ探査列を探査する．系より，k がハッシュ表に i+1 番目に挿入されたキーならば，探索に必要な探査回数の期待値は 1/(1i/m) = m/(mi)以下

ハッシュ表に存在する n 個のキーについて平均を取ると，成功に至る探索に必要な探査回数の平均が得られる． =0.5 のとき 3.387回 以下 =0.9 のとき 3.670回 以下

万能ハッシュ法 運が悪いと，n 個のキーが同じスロットにハッシュされ，平均検索時間が (n) になってしまう 万能ハッシュ法 (universal hashing) では，ハッシュ関数をランダムに選択する どのように意地悪くキーを選択しても，平均として良い性能を示す．

H: キーの普遍集合 U から値域 {0,1,...,m1} へのハッシュ関数の有限集合 H が万能 (universal) ⇔ 全ての異なるキーの組 x, y  U に対し，h(x) = h(y) となるハッシュ関数 h  H の個数がちょうど |H|/m ハッシュ関数を万能な H の中からランダムに選んだときに，x と y が衝突する確率が 1/m これは h(x) と h(y) が値域 {0,1,...,m1} からランダムに選択されたときの衝突確率に等しい

定理 h を万能な集合から選択されたハッシュ関数とする．h を用いて n 個のキーをサイズが m のハッシュ表にハッシュする 定理 h を万能な集合から選択されたハッシュ関数とする．h を用いて n 個のキーをサイズが m のハッシュ表にハッシュする. 衝突はチェイン法で解消する．このとき，キー k のハッシュ先のリストの長さの期待値 E[nh(k)] は 　　　高々α（キーが表に存在しないとき） 　　高々1+α（キーが表に存在するとき） 期待値の計算は全てハッシュ関数に関して行い， キーの分布については何も仮定しないことに注意

証明:異なるキーのペア k, l に対して，指標確率変数 を定義する． ハッシュ関数の定義より，1つのキーのペアが衝突を起こす確率は高々 1/m．つまり Pr{h(k)=h(l)}1/m よって E[Xkl]  1/m. キー k に対し，k 以外で k と同じスロットにハッシュされるキーの個数を確率変数 Yk で表す．

k  T のとき 従って k  T のとき, キー k はリスト T[h(k)] に存在し， カウント Yk には k は含まれていないので 従って

万能ハッシュ関数族の設計 どんなキー k も 0 から p-1 までの範囲に入るような十分大きな素数 p を選ぶ．p > m を仮定． 　　　　　　　　　　　　　　　　　　　　　と定義 ただし a  {1,2,…,p-1}, b  {0,1,,…,p-1}． m は素数でなくてもいい． 定理: ハッシュ関数のクラス は万能である． 証明：相異なるキー k, l  Zp を考える．ハッシュ関数 ha,b に対し 　　r = (ak+b) mod p s = (al+b) mod p と置く．

命題：r  s rs  a(kl) (mod p) である． 　a も kl も法 p の下で 0 ではない． 　p は素数だから右辺の積も 0 ではない． (k,l) を固定する．p(p1) 個存在するハッシュ関数のパラメタのペア (a,b) は， (k,l) を異なるペア (r,s) に写像する． r  s であるペアは p(p1) 個存在するので， (a,b) と (r,s) には1対1対応がある． (a,b) を一様ランダムに選べば， (r,s) も一様ランダム．

従って，相異なるキー k と l が衝突する確率は， 法 p の下で相異なる r と s をランダムに選択したときに r  s (mod m) となる確率に等しい． r を固定すると，r 以外の p1 個の値の中で r  s (mod m) となる s の個数は高々 よって，s と r が衝突する確率は高々 1/m 従って，任意の異なる値 k,l Zp のペアに対し つまり は万能