Purely Functional Data Structures exercise 3.9 （Red-Black Tree 赤黒木）
第3回PFDS(Purely Functional Data Structures)読書会で
exercise 3.9 のときに紹介された論文「Constructing Red-Black Trees」（この名前でググるとPDF版が見つかる。Postscript版はこちら）に載っている関数 bottom-up の計算量が O(n) であることを確認する。
コードは
data Color = R | B data RBTree a = E | N Color (RBTree a) a (RBTree a) data Digit a = One a (RBTree a) | Two a (RBTree a) a (RBTree a) incr :: Digit a -> [Digit a] -> [Digit a] incr (One a t) [] = [One a t] incr (One a1 t1) (One a2 t2 : ps) = Two a1 t1 a2 t2 : ps incr (One a1 t1) (Two a2 t2 a3 t3 : ps) = One a1 t1 : incr (One a2 (N B t2 a3 t3)) ps bottomUp :: [a] -> RBTree a bottomUp = linkAll . foldr add [] add a ps = incr (One a E) ps linkAll = foldl link E link l (One a t) = N B l a t link l (Two a1 t1 a2 t2) = N B (N R l a1 t1) a2 t2
linkAll は O(n) なので foldr add ［］ が O(n) であることを確認すればよい。
n回目だけの add で結果［Digit a］がどうなるかと incr が何回呼ばれるかを表にしてみる。
One a t は "1" と、Two a1 t1 a2 t2 は "2" と略記する。
| n回目 | [Digit a］ | 回数 |
|---|---|---|
| 0 | ［］ | 0 |
| 1 | ［1］ | 1 |
| 2 | ［2］ | 1 |
| 3 | ［1 1］ | 2 |
| 4 | ［2 1］ | 1 |
| 5 | ［1 2］ | 2 |
| 6 | ［2 2］ | 1 |
| 7 | ［1 1 1］ | 3 |
| 8 | ［2 1 1］ | 1 |
| 9 | ［1 2 1］ | 2 |
| 10 | ［2 2 1］ | 1 |
| 11 | ［1 1 2］ | 3 |
| 12 | ［2 1 2］ | 1 |
| 13 | ［1 2 2］ | 2 |
| 14 | ［2 2 2］ | 1 |
| 15 | ［1 1 1 1］ | 4 |
| 16 | ［2 1 1 1］ | 1 |
| 17 | ［1 2 1 1］ | 2 |
| 18 | ［2 2 1 1］ | 1 |
| 19 | ［1 1 2 1］ | 3 |
| 20 | ［2 1 2 1］ | 1 |
| 21 | ［1 2 2 1］ | 2 |
| 22 | ［2 2 2 1］ | 1 |
| 23 | ［1 1 1 2］ | 4 |
| 24 | ［2 1 1 2］ | 1 |
じっと眺めると
4〜5 の incrの呼ばれた回数は 2〜3 の incrの呼ばれた回数と同じで
6〜7 の incrの呼ばれた回数は 2〜3 の incrの呼ばれた回数の最後だけ 1 増えていて、
8〜11 の incrの呼ばれた回数は 4〜7 の incrの呼ばれた回数と同じで
12〜15 の incrの呼ばれた回数は 4〜7 のincrの呼ばれた回数の最後だけ 1 増えていて、
16〜23 の incrの呼ばれた回数は 8〜15 の incrの呼ばれた回数と同じで
24〜31 の incrの呼ばれた回数は 8〜15 の incrの呼ばれた回数の最後だけ 1 増えていて、
...
2^i〜2^i+2^(i-1)-1 の incrの呼ばれた回数は 2^(n-1)〜2^(n-1)+2^(i-2)-1 の incrの呼ばれた回数と同じで
2^i+2^(i-1)-1〜2^(i+1)-1 の incrの呼ばれた回数は 2^(n-1)〜2^(n-1)+2^(i-2)-1 の incrの呼ばれた回数の最後だけ 1 増えている
ことが見えてくる。
これは
［d1, d2, d3 ... , di, 1］に add するときの処理は［d1, d2, d3 ... , di］に add するときの処理とほぼ同じで
［d1, d2, d3 ... , di, 2］に add するときの処理は［d1, d2, d3 ... , di］に add するときの処理とほぼ同じものの
d1, ... di すべて 2 のときは特別に繰り上がり処理が一手間増えるということから納得できる。（ちゃんとやるには数学的帰納法で証明）
incrの呼ばれた回数の合計で見直すと
4〜5 の 回数の合計は 2〜3 の 回数の合計 3 と同じで 3。
6〜7 の 回数の合計は 2〜3 の 回数の合計 3 足すことの 1 で 4。
つまり 4〜7 の 回数の合計は 2〜3 の 回数の合計 3 の倍足すことの 1 で 7。
同様に 8〜15 の 回数の合計は 4〜7 の 回数の合計 7 の倍足すことの 1 で 15。
同様に 16〜31 の 回数の合計は 8〜15 の 回数の合計 15 の倍足すことの 1 で 31。
...
同様に 2^i〜2^(i+1)-1 の 回数の合計は 2^(i-1)〜2^i-1 の 回数の合計 2^i-1 の倍足すことの 1 で 2^(i+1)-1。
これらを合計すると
1〜2^i-1 の 回数の合計は 1 + 3 + 7 + 15 + ... + (2^i - 1) 。
2^i回目 の incrの呼ばれる回数は 1回なので
1〜2^i の 回数の合計は 1 + 3 + 7 + 15 + ... + (2^i - 1) + 1。
これは
1 + 2 + 4 + 8 + 16 + ... + 2^i == 2*(2^i) - 1 より小さくなる。
f(n) で n回 add するときの incrの呼ばれた回数の合計を表すと上記の考察から
n == 2^i のときは f(n) < 2*n
ということがわかる。
２のベキ乗に限らない一般の n に対して
n <= 2^i < 2*n
という i を取ると、f は単調増加関数ということに注意して
f(n) <= f(2^i) < 2*(2^i) < 2*(2*n) == 4*n
f(n) < 4*n つまり f(n) は O(n) である。
