情報工学概論 (アルゴリズムとデータ構造) 第7回

11.3.3 万能ハッシュ法 運が悪いと，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} からランダムに選択されたときの衝突確率に等しい

定理 11. 3 h を万能な集合から選択されたハッシュ関数とする．h を用いて n 個のキーをサイズが m のハッシュ表にハッシュする 定理 11.3 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 は素数でなくてもいい． 定理11.5: ハッシュ関数のクラス は万能である． 証明：相異なるキー 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 のペアに対し つまり は万能

乱数発生法 {0, 1, …, p1} の整数を一様ランダムに生成 C言語 int x; x = rand() % p; // 整数乱数を p で割った余り Fortran real r integer x call RANDOM_NUMBER(r) ! 0 <= r < 1 の実数乱数 x = INT(r * p)

乱数の種の設定 現在時刻を乱数の種にする C言語 Fortran srand((int)clock()); srand((int)time(NULL)); Fortran call random_seed()

12. 2分探索木 探索木: SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE等が利用できる動的集合用データ構造 辞書やプライオリティーキューとして利用できる 基本操作は木の高さに比例した時間がかかる ランダムに構成された2分探索木の高さ: O(lg n) 最悪時: O(n) 最悪時でも O(lg n) に改良できる (2色木)

12.1 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

木の中間順巡回 木の中間順巡回 (通りがけ順, inorder tree walk 根の左部分木に出現するキー集合 根のキー 右部分木に出現するキー集合の順にキーを出力 木の根から辿ると，全てのキーをソートされた順序で出力できる (n) 時間 5 2 3 7 8 INORDER_TREE_WALK(node x) { if (x != NIL) { INORDER_TREE_WALK(left(x)); print(key(x)); INORDER_TREE_WALK(right(x)); } 5 7 3 2 8 5

その他の巡回法 先行順巡回 (行きがけ順, preorder tree walk): 根節点を先に出力し，次に左右の部分木を出力 後行順巡回 (帰りがけ順, postorder tree walk): 先に左右の部分木を出力し，最後に根節点を出力 PREORDER_TREE_WALK(node x) { if (x != NIL) { print(key(x)); PREORDER_TREE_WALK(left(x)); PREORDER_TREE_WALK(right(x)); } POSTORDER_TREE_WALK(node x) { if (x != NIL) { POSTORDER_TREE_WALK(left(x)); POSTORDER_TREE_WALK(right(x)); print(key(x)); }

12.2 2分探索木に対する質問操作 質問操作は高さに比例した時間で終了する 探索: 2分探索木の中から，ある与えられたキーを持つ節点のポインタを求める(存在しなければNIL) TREE_SEARCH(node x, data k) { if (x == NIL || k == key(x)) return x; if (k < key(x)) return TREE_SEARCH(left(x),k); else return TREE_SEARCH(right(x),k); }

探索の正当性 キー k が見つかったら探索を終了する k が key(x) より小さい場合 k が key(x) より大きい場合 2分探索木条件より，k は x の右部分木にはない 左部分木に対して探索を続行する k が key(x) より大きい場合 右部分木に対して探索を続行する 探索する節点は根からのパスになる 実行時間は O(h) (h: 木の高さ)

再帰はwhileループにすることができる ITERATIVE_TREE_SEARCH(node x, data k) { while (x != NIL && k != key(x)) { if (k < key(x)) x = left(x); else x = right(x); } return x;

最小値と最大値 最小/最大のキーを持つ要素のポインタを返す O(h) 時間 TREE_MINIMUM(node x) { while (left(x) != NIL) { x = left(x); } return x; TREE_MAXIMUM(node x) { while (right(x) != NIL) { x = right(x); } return x;

次節点と前節点 2分探索木のある節点が与えられたとき，木の中間順 (inorder) で次/前の節点を求める O(h) 時間 TREE_SUCCESSOR(node x) { node y; if (right(x) != NIL) return TREE_MINIMUM(right(x)); y = p(x); while (y != NIL && x == right(y)) { x = y; y = p(y); } return y;

x が右部分木を持つ場合 x の次節点は，x 以上の要素で最小 ⇒ x の次節点は， x の右部分木の最小要素 = TREE_MINIMUM(right(x)) 5 2 7 8 x 次節点

x が右部分木を持たない場合 x の親を y とする x が，x の親の右の子ならば，親は x 以下 次節点 x y y = p(x); while (y != NIL && x == right(y)) { x = y; y = p(y); } return y; 9 x y 5 x y 3 7 2 5 8

定理 12.2 高さ h の2分探索木上の動的集合演算 SEARCH, MAXIMUM, MINIMUM, SUCCESSOR, PREDECESSOR は O(h) 時間で実行できる

12.3 挿入と削除 要素を挿入/削除したあとも2分探索木条件が満たされる必要がある 挿入は比較的簡単 削除は複雑 どちらも O(h) 時間

挿入 5 6 z 3 6 z y x y 7 TREE_INSERT(tree T, node z) { node x,y; y = NIL; x = root(T); while (x != NIL) { // z を挿入する場所 x を決める y = x; if (key(z) < key(x)) x = left(x); else x = right(x); } // y は x の親 p(z) = y; // z の親を y にする if (y == NIL) root(T) = z; // T が空なら z が根節点 else if (key(z) < key(y)) left(y) = z; // y の子を z にする else right(y) = z; } 2 5 8 挿入場所は必ず葉

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

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

TREE_DELETE(tree T, node z) { node x, y; if (left(z) == NIL || right(z) == NIL) y = z; // z の子の数が1以下 else y = TREE_SUCCESSOR(z); // z は2つの子を持つ if (left(y) != NIL) x = left(y); else x = right(y); // x は y の子 if (x != NIL) p(x) = p(y); // y を削除する if (p(y) == NIL) root(T) = x; // y が根なら x を根に else if (y == left(p(y))) left(p(y)) = x; // y の親と子をつなぐ else right(p(y)) = x; if (y != z) { key(z) = key(y); // y の内容を z に移動 // y の付属データを z にコピー } return y; // 不必要な y を回収

12.4 ランダムに構成された2分探索木 2分探索木上の基本操作は O(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 = 1 と定義する. 指標確率変数 を次のように定義 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 は上に凸であるから 以上より 定理12.4 n 個のキー上のランダムに構成された2分探索木の高さの期待値は O(lg n).

補題 13.3 空の2分探索木に n 個の相異なるキーk1, k2,...,knをこの順序で挿入して得られる木をTとする． 1 i < j  n に対し，T の中で ki が kj の先祖であるための必要十分条件は ki = min{kl: 1 l  i かつ kl > kj} (k1から ki で kj より大きいものの中で最小) または ki = max{kl: 1 l  i かつ kl < kj} (k1から ki で kj より小さいものの中で最大) 15 6 ki 12 3 挿入順 (一例) 15, 6, 12, 3, 10, 7, 13 10 13 kj 7

kj は km の左の部分木， ki は km の右の部分木になり， ki が kj の先祖という仮定に矛盾する． 証明: (必要性) ki が kj の先祖だと仮定する． kj < ki とし， ki = min{kl: 1 l  i かつ kl > kj} が成り立たないと仮定する．つまり， kj < km < ki となる km (m < i) が存在する． kj は km の左の部分木， ki は km の右の部分木になり， ki が kj の先祖という仮定に矛盾する． kj > ki の場合も同様． 6 10 3 12 13 15 7 ki kj km 3 2 kj 5 ki

ki < x のとき， kj < ki より kj < x 証明: (十分性) ki は, k1から ki で kj より大きいものの中で最小と仮定する．探索木の根から ki までのパス上の節点 x を考える． ki < x のとき， kj < ki より kj < x x < ki のとき， x > kj とすると x は仮定を満たさない ので x < kj よって根から kj へのパスは ki を通る． つまり ki は kj の祖先 6 10 3 12 13 15 7 ki kj x

系13.4 空の2分探索木に n 個の相異なるキーk1, k2,...,kn をこの順序で挿入した結果を T とする． kj (1 j  n) に対し，Gj と Lj を Gj = {ki: 1 i  j かつ kl > kj である全ての l  i に対して kl > ki > kj} Lj = {ki: 1 i  j かつ kl < kj である全ての l  i に対して kl < ki < kj} とする．このとき，根と kj を結ぶパス上に現れるキーの集合は Gj  Lj に一致し， kj の T における深さ d(kj, T) は d(kj, T) = |Gj| + |Lj|

Gj 21 Lj 9 25 12 4 29 10 19 3 26 7 17 kj 6 18 キー 21 9 4 25 7 12 3 10 19 29 17 6 26 18 Gj’ 21 25 19 29 Gj 21 19 Lj’ 9 4 7 12 3 10 Lj 9 12 ←kj より大きい ←最小値を更新 ←kj より小さい ←最大値を更新

Gj のサイズの解析 Gj: kj より大きいキーの中で，今までの最小値を更新したものの集合 n 個の異なるキーが1つずつ動的集合に挿入されたと仮定する キーの全ての順列が同じ確率で出現するときに，集合の最小値が何回変化するか求める i 番目に挿入されたキーを ki とする (1 i  n) 最初の i 個の中で ki が最小値の確率 = 1/i

集合の最小値の変更回数の期待値は 補題 13.5 n 個の相異なる数のランダム順列を k1,k2,...,kn とし，|S| を，集合 S={ki: 1  i  n, かつ, 全ての l < i についてkl >ki} の大きさを表す確率変数とする．このとき Pr{|S|  (+1)Hn}  1/n2 (  4.32 は (ln  1) = 2 を満たす数)

証明: 集合 S の大きさは n 回のベルヌーイ試行から決定されるとみなすことができる． i 回目の試行が成功する確率は 1/i． 以下の定理を使う． 定理 6.6 i = 1,2,...,n に対して i 番目の試行の成功確率が pi である n 回のベルヌーイ試行の列を考える．Xを全成功回数を表す確率変数とし， = E[X] とおく．このとき r >  に対し

 > 1 より

定理 13.6 n 個の相異なるキー上のランダムに構成された2分探索木の高さの平均は O(lg n) 証明 n 個のキー上のランダム順列をk1,k2,...,kn とし，空の2分探索木にこれらをこの順序で挿入した結果を T とする．与えられたキー kj の深さ d(kj,T) が少なくとも t である確率を考える． 系13.4 より， kj の深さが少なくとも t ならば，集合 Gj, Lj のどちらかはサイズが t/2 以上．よって

t = 2(+1)Hn とすると

2分探索木には n 個の節点が存在する．少なくとも1つの節点が高さ 2(+1)Hn 以上である確率は高々 n(2/n2) = 2/n．