x - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第9回
12.4 ランダムに構成された2分探索木
• 2分探索木上の基本操作は O(h) 時間で実行可
• 要素の挿入削除を繰り返すと探索木の高さ h
は変化する
• n 個の相異なるキーをランダムな順序で挿入し
た2分探索木の高さを解析する
• 高さの期待値は O(lg n)
2
• 仮定
– 入力キーの n! 種類の順列がどれも等確率で出現する
– 全てのキーは異なる
• 確率変数の定義
– Xn: n 個のキー上のランダムに構成された2分探索木の
高さ
– Yn = 2Xn 指数高さ
– Rn: n 個のキーの中での根のキーの順位 (rank)
Rn = i なら，根の左部分木は i1 個のキー上の
ランダムに構成された2分探索木，右部分木は
ni 個のキー上のランダムに構成された2分探索木
3
• 2分探索木の高さは根の左右の部分木の高さの
大きいほう+1． Rn = i のとき
X n  max X i 1 , X n i  1
Yn  2 max Yi 1 , Yn i 
• Y1 = 1. 便宜上 Y0 = 0 と定義する.
• 指標確率変数 Z n,1 , Z n, 2 ,, Z n,n を次のように定義
Rn  i 
1
Z n ,i  IRn  i  
0 それ以外
• Rn の値は {1,2,…,n} の任意の要素を等確率で
取るから，Pr{Rn = i} = 1/n (i=1,2,…,n) よって
1
EZ n ,i  
n
4
• 根の順位が i のときだけ Zn,i = 1 になるから
n
Yi   Z n ,i 2 max Yi 1 , Yn i 
i 1
• E[Yn] が多項式であることが示せれば，
E[Xn] が O(lg n) であることが示せる．
• Zn,i は Yi1 とも Yni とも独立
– 根の左部分木内の各要素は根よりも小さい，つまり
順位が i より小さい i1 個のキー上のランダムに構成
された木である．
– この部分木は順位の制約がないi1 個のキー上のラン
ダムな木と同じ
– 部分木の高さ Yi1 と根の順位 Zn,i は独立
5
 n

EYi   E  Z n ,i 2 max Yi 1 , Yn i 
 i 1

  EZ n ,i 2 max Yi 1 , Yn i 
n
(期待値の線形性)
i 1
  EZ n ,i E2 max Yi 1 , Yn i 
n
(独立性)
i 1
2 n
  Emax Yi 1 , Yn i 
n i 1
2 n
  EYi 1   EYn i 
n i 1
4 n 1
  EYi 
n i 0
6
•
1  n  3

EYn   
4 3 
を示す
1  3 1
0  Y0  EY0     
4  3 4
1 1  3 
  1
1  Y1  EY1   
4 3 
4 n 1
EYn    EYi 
n u 0
4 n 1 1  i  3 

  
n u 0 4  3 
1  n  3

 
n 4 
1  n  3

 
4 3 
7
• 関数 f(x) = 2x は下に凸であるから
2
E X n 
   EY 
E2
Xn
n
• 以上より
1  n  3
  Olog n 
EX n   log EYn   log 
4 3 
• 定理12.4 n 個のキー上のランダムに構成さ
れた2分探索木の高さの期待値は O(lg n).
8
13. 2色木
• 2分探索木は，基本的な動的集合操作を
木の高さに比例する時間で実現できる
• 探索木の高さは要素の挿入順に依存し，
最悪の場合は O(n) になる
• 2色木は，基本操作が最悪でも O(lg n)時間
になるような探索木の1つである
9
13.1 2色木条件
• 各節点に1ビットの情報(色)を加えた2分探索木
• 各節点は赤または黒の色がついている
• 各節点の要素
– color, key, left, right, p
• 外部節点 (葉) は NIL で表される
• 内部節点のみが key を持つ
10
2色木条件 (Red-Black Property)
2分探索木が下記の2色木条件を満たすならば，
2色木である．
1. 各節点は赤か黒のどちらか
2. 葉 (NIL) は全て黒
3. もしある節点が赤ならば，その子供は両方黒
4. 1つの節点からその子孫の葉までのどの単純
な経路も，同じ数だけ黒節点を含む．
11
3 26
3 17
2 41
2 14
2 10
1 7
1 3
NIL
1 16
1 12
NIL
NIL
2 21
NIL
1 15
NIL
NIL
NIL
1 19
NIL
2 30
1 23
20
NIL
NIL
NIL
NIL
1 28
NIL
NIL
1 47
1 38
NIL
1 35 1 39
NIL
NIL
NIL
NIL
NIL
ある節点 x から葉までの経路上の黒節点の数
(x は含まない) を黒高さと呼び，bh(x) で表す
12
NIL
補題13.1: 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 の木でも成り立つ 13
証明の続き:
木の高さを 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色木条件を壊すため，アル
ゴリズムを変更する必要あり
14
13.2 回転
• 2色木で節点を追加/削除すると2色木の条
件を満たさなくなることがある．
• 条件を満たすように木の構造を変更する
•  < x <  < y <  の順を保つ
RIGHT_ROTATE(T,y)
y

x


x
y

LEFT_ROTATE(T,x)


15
7
4
3
11
6
x
9
18

2
14
LEFT_ROTATE(T,x)
12
y
19
17
22

7
20
y
4
3
2

18
6
11
x
9
19
22
14
12
17
20
16
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;
}
O(1) 時間
x
y



y

x


17
13.3 新しい節点の挿入
•
•
•
keyに従って節点 x を葉に挿入する
x の色を赤にする
x を挿入後の2色木条件
1.
2.
3.
4.
各節点は赤か黒のどちらか…OK
葉 (NIL) は全て黒…OK
もしある節点が赤ならば，その子供は両方黒…?
1つの節点からその子孫の葉までのどの単純な経路
も，同じ数だけ黒節点を含む…OK
x の親が赤のときは条件3を満たさない⇒回転操作
18
挿入後の回転操作
•
x の親 z が赤である間以下を繰り返す
1. z の兄弟 y が赤のとき: z と y を黒，x をそれ
らの親とし，赤にする
2. y が黒で x が右の子のとき: 左回転→場合3
3. y が黒で x が左の子のとき: x の親を黒，そ
の親を赤にして右回転
19
場合1 z の兄弟 y が赤のとき
11
2
14
1
7
z
x
15
8 y
5
4
11
2
14
x 7
1
5
4
8
15
20
場合2 y が黒で x が右の子のとき 11
2
z
14
y
x 7
1
5
15
8
4
11
7
14
y
8
x 2
5
15
1
4
21
場合3 y が黒で x が左の子のとき
11
7 z
14
y
8
x 2
15
5
1
4
7
11
x 2
5
1
8
14
4
15
22
場合1: z の兄弟 y が赤のとき
•
•
•
•
•
z の親 w は黒 (元の木では赤は連続しない)
y, z の子孫の節点の黒深さは変化しない
w の黒深さは1増える
w の祖先の黒深さは変化しない
new x の親が赤の可能性があるため繰り返す
new x
w C
z
A
D

B

x


y

C
A
D


B



23
場合2: y が黒で x が右の子のとき
•
•
•
•
z で左回転を行う⇒ x は左の子になる
x, z ともに赤であるため，条件 3, 4 は満たされる
x, z の子孫の黒高さも変化しない
場合3に移る
w C
z
C
y
A
y
B
D

B

x

x A

D


24
場合3: y が黒で x が左の子のとき
• p(p(x)) で右回転を行う
• 各部分木で黒高さは保存される
• 赤節点が連続することはない⇒終了
C
z
y
B
x A

B
D


x A

C

y

D
25
計算量
• 2色木の高さは O(lg n)
• TREE_INSERTは O(lg n) 時間
• RB_INSERTでのwhileループでは x のポイン
タは木を登っていく
• ループの実行回数は木の高さ以下⇒ O(lg n)
• ループ内の処理は定数時間
• 全体でも O(lg n) 時間，高々2回の回転
26
13.4 削除
• 探索木から節点 z を削除する
• z が子を持たない場合
– z の親と z の子を結ぶ
3
z
– z の親 p(z) を変更する
• z が子を1つ持つ場合
3
2
2
5
5
5
7 z
y
x
8
8
27
削除: z が子を2つ持つ場合
• z の次節点は左の子を持たない
• z の場所に y を入れ，元の y を削除する
15
z
15
5
6
3
3
12
10
y
12
13
10
x
6
7
13
7
28
2色木の修正
• 削除される節点を y, その子の1つを x とする
• y が黒のとき，削除すると y を含んでいたどの
経路も黒高さが1減る
• x を含む全ての経路で黒高さが1増えればいい
29
場合1: x の兄弟 w が赤
• B で左回転
• B と D の色を変える
• x の兄弟が黒になる⇒場合2
D
B
D w
x A


C

x A
E


E
B


C




new w

30
場合2: w の左右の子が黒
• D の色を変える
• B が赤ならそれを黒にして終了
• B が黒なら B を新しい x として繰り返す
new x
B
B
D w
x A


C


E


D
A


C

E



31
場合3: w の右の子が黒
• D で右回転
• C と D の色を変える⇒場合4
B
B
new w
D w
x A



C

E


C
x A


D


E


32
場合4: w の右の子が赤
• B で左回転
• B, D, E の色を変える⇒終了
c
c
D
B
x A
D w

c’
E
B
c’

C


E

C
A







new x = root(T)
33
RB_DELETEの計算時間
• TREE_DELETEは O(lg n) 時間
• 場合1, 3, 4は定数時間，最大3回の回転
– 場合3,4に行くとそこで終了
– 場合1から2へ移った場合，新しい x は赤なので終了
• 場合2では回転は行わず，O(lg n) 回木を登る
• 全体で O(lg n) 時間，高々3回の回転
34

Download Report