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

情報工学概論
(アルゴリズムとデータ構造)
第9回
14. データ構造の補強
• 新しいデータ構造が必要なときでも，標準的な
データ構造に情報を追加することで十分な場合
が多い
• 2色木を拡張する
– 動的集合での順序統計量の計算
– 区間の動的集合の管理
2
14.1 動的順序統計量
• n 個の要素からなる集合の i 番目の順序統計
量: 集合の中で i 番目に小さいキーを持つ要素
• 任意の順序統計量は O(n) 時間で求まる
• 2色木を補強して，任意の順序統計量を O(log n)
時間で決定できるようにする．
• 要素のランク (rank) (指定された要素が小さい方
から何番目か) も O(log n) 時間で求まる
3
順序統計量木
size(x) = 20 26
12 17
7 41
7 14
4 10
2 7
1 3
4 21
2 16
1 12
1 15
2 19
1 20
1 23
5 30
1 28
1 47
3 38
1 35 1 39
各ノード x は部分木のサイズ size(x) を
格納するフィールドを持つ
size(x) = size(left(x)) + size(right(x)) + 1
4
与えられたランクを持つ要素を求める
• OS_SELECT(x, i): x を根とする部分木で i 番目に
小さいキー (順序統計量) を持つ節点を返す
• size(left(x)) + 1はxを根とする部分木でのxのランク
• 計算量: O(lg n)
node OS_SELECT(node x, int i)
{
int r;
r = size(left(x)) + 1;
if (i == r) return x;
else if (i < r) return OS_SELECT(left(x),i);
else
return OS_SELECT(right(x), i-r);
}
5
OS_SELECT(root(T), 17) の場合
20 26 i = 17 > 12+1
12 17
i = 4 < 5+1
7 14
4 10
2 7
1 12
4 21
2 16
1 15
2 19
1 20
1 23
7 41
1
5 30 i = 4 > 1+1 47
1 28
3 38 i = 2 = 1+1
1 35 1 39
1 3
6
要素のランクを求める
• 節点 x のポインタが与えられたときに，その要素が
小さい方から何番目かを返す
• 計算量: O(lg n)
int OS_RANK(tree T, node x)
{
int r; node y;
r = size(left(x)) + 1; // r を根とする部分木での x のランク
y = x;
while (y != root(T)) {
if (y == right(p(y))) r += size(left(p(y)) + 1;
y = p(y);
}
return r;
}
7
OS_RANK(T, x) の例
r = r + 12+1
20 26 = 17
12 17
7 14
4 10
2 7
1 3
1 12
4 21
2 16
1 15
2 19
1 20
1 23
r = r +1+1
=4
5 30
28
1
1
7 41
1
47
3 38 x
r = 1+1
35 1 39
8
部分木のサイズの管理
• 2色木の形状が変化すると size フィールドの値は
変化する
• 挿入，削除後も size の値を維持できることを示す
• 挿入の場合
–
–
–
–
木を根から辿り新しい要素を挿入する場所を見つける
新しい要素の祖先の size を1ずつ増やす
2色木の回転操作を行う
size を調整する
9
y
19 93 x
RIGHT_ROTATE(T,x)
19
42
x
11 42 y
6
4
93 12
7
6
4
7
size(y) = size(x)
size(x) = size(left(x)) + size(right(x)) + 1
1回の回転は O(1) 時間
回転は高々2回
全体の計算量: O(lg n)
10
削除の場合
• ノード y を削除したあとに size が変化する節点
は，y の祖先のみ
• y から根までの経路を辿りながら size を1ずつ減
らせばいい
• 回転操作は挿入と同様
– 高々3回の回転
• 計算量: O(lg n)
11
14.2 データ構造の補強
1. 元になるデータ構造を選ぶ
•
2色木
2. 元になるデータ構造で追加情報として管理さ
れるものを決定する
•
部分木のサイズ size
3. 元になるデータ構造の基本操作に対して追加
情報を維持できることを確認する
•
挿入，削除時の size の更新が O(lg n) 時間
4. 新しい操作を開発する
•
OS_SELECT, OS_RANK
12
定理15.1 (2色木の補強) T を n 節点からなる2色木，
f を T を補強するフィールドとする．節点 x に対する
f の内容は x の情報 (left(x), right(x), f(left(x),
f(right(x)) のみを用いて計算できるとする．
このとき，挿入/削除の際に T の全ての節点の f の
値を O(lg n) 時間で維持できる．
証明： (アイデア) f の内容はその子供から決まる．
よってある節点 x での f の変更はその祖先にしか
影響を与えない．よって挿入/削除の際の f の更新は
13
O(lg n) 時間．
挿入の場合：
第1段階: 新しい節点 xは既存の節点の子として挿入.
x の子は共にNILなので f(x) は O(1) 時間で計算可．
x の祖先の節点での f の更新は O(lg n) 時間．
第2段階: 木構造の変化は回転によってのみ発生．
1つの回転では2つの節点のみが変化する．
節点が1つ変化するたびにその節点とその先祖の
f を更新する．その時間は O(lg n)．
挿入の際に発生する回転は高々2回であるため，
挿入に要する総時間は O(lg n)．
削除も同様．
14
注：多くの場合，回転後の更新のコストは O(lg n)
ではなく O(1)．
RIGHT_ROTATE(T,y)
19 93 y
x
19
42
y
11 42 x
6
4
93 12
7
6
4
size(y) = size(x)
size(x) = size(left(x)) + size(right(x)) + 1
7
15
14.3 区間木
• 定義: 閉区間 (closed interval) とは，実数の順序対
[t1, t2] (t1  t2)
• 開区間(open interval),半開区間(half-open interval)
は区間の短点の両方または片方を省いたもの
• ここでは閉区間のみを扱う
• 区間木は，ある与えられた期間に起こった出来事
を見つける質問などに用いられる
16
区間の間の関係
• 区間 [t1, t2] をオブジェクト i とする．
• i はフィールド low[i] = t1 (下端点),
high[i] = t2 (上端点) で表される
• 区間 i と i’ が重なる  i  i’   つまり
1. low[i]  high[i’] かつ low[i’]  high[i]
i
i
i’
i’
i
i
i’
i’
• 区間 i と i’ が重ならない場合
– 2. high[i] < low[i’] または 3. high[i’] < low[i]
i
i’
i’
i
17
区間木での操作
•
•
•
•
木の各要素は区間 Int(x) を持つ
INTERVAL_INSERT(tree T, node x): x を挿入
INTERVAL_DELETE(tree T, node x): x を削除
INTERVAL_SEARCH(tree T, interval i): Int(x) が
区間 i と重なっている要素 x のポインタを返す
1. 元になるデータ構造: 2色木
– 各節点 x は区間 Int(x) を含む
– x のキーは区間の下端点 low(Int(x))
18
19
8 9
6
0
5
3
10
8
17
16
15
20
19
21
26 26
25
30
23
[16,21]
30
Int
[8,9]
23
[15,23]
23
[5,8]
10
[0,3]
3
[25,30]
Max
30
[6,10]
10
[17,19]
20
[26,26]
26
[19,20]
20
Max(x): x を根とする部分木に蓄えられている区間の
端点の最大値 (つまり上端点の最大値)
19
2. 追加情報
– Int(x): 区間
– Max(x): x を根とする部分木に蓄えられている区間の端
点の最大値 (つまり上端点の最大値)
3. 情報の更新
– 挿入/削除を行なったときに Max が O(lg n) 時間で更新
できることを示す
– Max(x) = max{high(Int(x)), Max(left(x)), Max(right(x))}
より，O(lg n) 時間で更新できる
20
4. 新しい操作の実装
区間 i と重なっている区間を見つける
O(lg n) 時間
node INTERVAL_SEARCH(tree T, interval i)
{
node x;
x = root(T);
while ((x != NIL)
&& (high(i) < low(int(x)) || high(int(x)) < low(i))) {
//
i と int(x) が重ならない
if (left(x) != NIL && Max(left(x)) >= low(i)) x = left(x);
else x = right(x);
}
return x;
}
21
i = [22,25]
Max(left(x))  low(i)
23  22 [16,21]
30
[8,9]
23
[0,3]
3
10 < 22
[15,23]
23
[5,8]
10
[6,10]
10
[25,30]
30
i と重なりを
もつので出力
[17,19]
20
[26,26]
26
[19,20]
20
22
i = [11,14]
23  11
左の部分木は
i とは重ならない
[6,10]
10
右の部分木のどの区間も
i とは重ならない
[25,30]
30
10 < 11
[15,23]
23
[5,8]
10
[0,3]
3
[8,9]
23
[16,21]
30
[17,19]
20
[26,26]
26
[19,20]
20
右の子はNILなので
NILを出力
23
定理 15.2 INTERVAL_SEARCH(T, i) の実行中の
whileループにて，
1. 探索が左に行ったとき: x の左部分木は i と重なり
合う区間を含むか，x の右部分木のどの区間も i と
は重ならない
2.探索が右に行ったとき: x の左部分木のどの区間も
i とは重ならない
証明: 2の場合: 右に行く場合は left(x) = NIL または
Max(left(x)) < low(i) が成り立つ．
前者の場合は x の左部分木は空であるので成立．
24
後者の場合， i’ を x の左部分木内の区間とする．
Max(left(x))は x の左部分木中の最大の端点なので
high (i ' )  Max (left ( x))
 low(i )
となり，どの区間も i と重ならない．
i’
i
Max(left(x)) low(i)
25
1の場合: x の左部分木中の区間で i と重なり合う
ものが見つかれば探索は終了する．
見つからない場合に，x の右部分木中のどの
区間も i と重ならないことを示す．
分岐の条件より， Max(left(x))  low(i).
Maxの定義より，x の左部分木中にある区間 i’ が
存在して
high (i ' )  Max (left ( x))
 low(i )
i
i’
i と i’ は重ならないため
high (i )  low(i ' )
low(i)
26
Max(left(x))
キーは区間の下端点であり，探索木の性質から，
x の右部分木中のどの区間 i’’ に対しても
low(i ' )  low(i ' ' )
i’’
が成り立つ．つまり
i
high (i )  low(i ' ' )
i’
となり，i と i’’ は重ならない．
low(i)
Max(left(x))
この定理から，ある方向に探索して区間が見つか
らなかった場合は反対側にも解がないことが保障
される．
27
問合せと交わる区間を全て出力
void interval_search_enumerate(tree *T, node *x, interval i)
{
if (x == nil(T)) return;
if (low(i) > Max(x)) return; // i の下端点が, x を根とする部分木内の区間の上端点より
//大きいなら部分木内の全ての区間は i と交わらない
if (left(x) != nil(T)) interval_search_enumerate(T, left(x), i);
if (low(i) <= high(Int(x)) && low(Int(x)) <= high(i)) { // 交わっていれば表示
printf("[%lf,%lf]\n", low(Int(x)), high(Int(x)));
}
if (high(i) < low(Int(x))) return; // i の上端点が, x を根とする部分木内の区間の下端点より
//小さいなら, 右部分木内の全ての区間は i と交わらない
if (right(x) != nil(T)) interval_search_enumerate(T, right(x), i);
}
28
10. 中央値と順序統計量
• n 要素の集合の i 番目の順序統計量 (order
statistic): その集合で i 番目に小さい要素
• 最小値 (minimum): i = 1
• 最大値 (maximum): i = n
• 中央値 (median):
– n が奇数のとき i = (n+1)/2
– n が偶数のとき i  (n  1) / 2とi  (n  1) / 2
– いずれの場合も i  (n  1) / 2
29
選択問題 (selection problem)
• 入力: n 個の異なる数の集合 A, 整数 i (1  i  n)
• 出力: A 中のちょうど i 1 個の他の要素より大きい
要素 x  A
• 選択問題は O(n lg n) 時間で解ける
– A の要素をソートする
– 出力配列の i 番目の要素を返す
• 選択問題は O(n) 時間で解ける
30
10.2 平均線形時間の選択法
• 順序統計量は (n) 時間で求まるが複雑
• まず，平均的に O(n) 時間のアルゴリズムを考える
data RANDOMIZED_SELECT(data *A, int p, int r, int i)
// A[p..r] の中で i 番目に小さい要素を返す
{
int q, k;
if (p == r) return A[p];
q = RANDOMIZED_PARTITION(A,p,r); // q: 分割の位置
k = q – p + 1;
// k: 左部分の要素数
if (i <= k) return RANDOMIZED_SELECT(A,p,q,i);
else
return RANDOMIZED_SELECT(A,q+1,r,ik);
31
}
• q = RANDOMIZED_PARTITION(A,p,r);の実行後
– 2つの空でない部分配列 A[p..q], A[q+1..r] に分かれる
– 左側の各要素は右側よりも小さい
– k = q – p + 1; は左側の要素数
• i  k ならば i 番目の要素は左側の i 番目
• i  k ならば i 番目の要素は右側の i  k 番目
• 部分配列のサイズが 1 になるまで繰り返す
32
平均実行時間の上界
• T(n): n 要素の集合での選択問題の平均時間
• 分割の左側のサイズが
– 1 になる確率 = 2/n
– i になる確率 = 1/n (i = 2,3,...,n1)
• T(n) は単調増加と仮定する
n 1
1

T n    T max 1, n  1   T max k , n  k   O(n)
n
k 1

n 1

1
  T n  1  2  T k   O(n)
n
k  n / 2 

2 n 1

T k   O(n)

n k  n / 2 
33
• RANDOMIZED_SELECTの最悪実行時間は(n2)
よって 1/n T(n1) = O(n)
• T(n)  cn と仮定すると
2 n 1
T n  
 ck  dn
n k  n / 2 
n / 2 1 
2c  n 1
   k   k   dn
n  k 1
k 1 
2c  1
1   n   n  
  n  1n      1     dn
n 2
2   2   2  
cn n
 cn  1    1  dn
n2 2
1
3
 c n    dn
2
4
if c(n / 4  1 / 2)  dn 
 cn
34
10.3 最悪線形時間の
選択アルゴリズム
アルゴリズム SELECT: i 番目に小さい要素を返す
1. 入力配列の n 要素をグループに分割
–
–
5要素のグループ n/5 個
n mod 5 要素のグループ高々1個
2. n/5 個の各グループを(挿入ソート等で)ソートし，
それぞれの中央値を求める
3. SELECTを再帰的に用いてステップ2で求めた
n/5 個の値の中央値 x を求める
35
4. PARTITIONを修正したものを用い，入力配列を x
によって分割する．左側の要素数を k とする.
5. i  k ならば，左側で i 番目に小さい要素を再帰
的に見つける．
i  k ならば，右側で ik 番目に小さい要素を再帰
的に見つける．
36
SELECTの実行時間の解析
• 分割に用いた x より大きい要素数の下界を求める
• ステップ 2 で求めた中央値の少なくとも半分は x
(中央値の中央値) 以上
• 中央値が x 以上のグループには，x 以上の値が 3
個以上ある
• x 以上となる要素数は少なくとも
  1  n    3n
3      2  
6
  2  5    10
37
• 同様に，x 以下となる要素数も少なくとも 3n/106
• ステップ 5 で再帰的に呼ばれる SELECT の部分
問題のサイズは高々 7n/10+6
• ステップ 1,4: O(n) 時間
• ステップ 2: 5 要素のソートを n/5 回⇒ O(n)時間
• ステップ 3: T(n/5) 時間
(1)
n  80のとき

T ( n)  
T n / 5  T 7n / 10  6  On  n  80のとき
38
• n  80 に対して T(n)  cn と仮定する.
c を十分大きくとれば
T (n)  c n / 5  c7n / 10  6  On 
 cn / 5  7cn / 10  6c  On 
 9cn / 10  7c  On 
 cn
• よって，SELECTの最悪実行時間は線形
• これは比較しか用いていない
39
• クイックソートの pivot として厳密な中央値を
用いれば，最悪計算量が O(n log n) になる
• ただし，SELECTが複雑なので実行速度は
速くない
• また，in-placeではなくなる
40

Download Report