第4章データ探索 - 講義ノート

4.1 2分探索

検索・挿入・削除がO(logn)時間で実行される。

4.2 2分探索木

右の子<親<左の子の関係を保っている2分木
検索・挿入・削除は木の高さに比例する。
最悪の場合木の高さはn-1になる。

ランダムに要素を挿入すると…

データの割り当てられている点の個数をn個として、これを内点と呼び、その外側に加えた架空の点（n+1個加えることができる）を外点と呼ぶとする。
根から外点までの距離の総和をD(n)で表すとすると
$\frac{1}{n} \sum_{i=1}^{n}(D(i-1)+D(n-i)+n+1)$
（注：2つに分割し、根からそれぞれの木までの距離は1なので1*(n+1)（総和だから）を加算する。）
ただしD(0)=0。これを計算すると
$D(n)=n+1+\frac{2}{n} \sum_{i=1}^{n}D(i-1)$
根から各外点までの路長の平均は $\frac{D(n)}{n+1}$ であり
D(n)の式より $\frac{D(n)}{n+1}-\frac{D(n-1)}{n}=\frac{2}{n+1}$ となるので
$\frac{D(n)}{n+1}=2\sum_{i=2}^{n+1}(\frac{1}{i})\le \int_{1}^{n+1} (\frac{1}{x})\, dx = 2\ln(n+1)\le1.4\log_{2}(n+1)$

4.3 2色木

2分探索木の各頂点に以下の条件を満たすように赤または黒の色を塗ったもの

外点の色は黒である
根から外点に至る路はどれも同じ数の黒点を含む
どの赤点も親があればそれは黒点である。

高さはO(log(n))になるらしい
資料：
http://sunak2.cs.shinshu-u.ac.jp/~miyao/AL/Class/13-red-black-tree.pdf
http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html
ワカンネ…

高さはO(log(n))になることの証明:
任意の2色木のうち、根から外点への経路をたどった際にもっとも深さの小さい頂点をvとし、vの深さをdとする。
すると、頂点は最低でも2^d-1個ある。
またこのとき、もっとも深い頂点をv'とする。根からv'への経路には、根からvへの経路と同数の黒頂点があるため、条件3よりv'の深さは高々2dである。つまり
v'の深さ≦2d≦2log(n+1)=O(log(n))

挿入の実現

とりあえず新しい頂点を赤色にして適切な位置に挿入する
挿入した要素vの親uが赤色だったらまずい
1. uの兄弟が赤の場合、uの親を黒にして、uとuの兄弟を黒にする（交換：最大lob(n)回発生する）。根まできたら根は黒にする。
2. uの兄弟が黒の場合、回転を行う。教科書を見るともしかしたら分かるかもしれない。（回転：最大2回発生する）回転する時さりげなく色も変わっているが気にしてはいけない。

…分かったことにしようぜ

削除の実現

赤は削除できる
黒だとやばい
1. 右の子ｗを上に上げてみる
2. ｗが赤なら黒にして解決。そうでないなら
- wの兄弟を赤にして黒不足を上に上げてみたりする。
- wの兄弟がすでに赤ならそれを回転して上に上げてみたりする

（以下略…わけわからん）