2009年9月5日土曜日

left-leaning 赤黒木(red-black tree) - ノードの追加(赤ノードの左)

追加するノード○aが、ある末端の赤ノード○zより小さいとき、または等しいとき(○a≦○z)を考えてみる。

○z は赤ノードのなので、黒の親ノード ●y の左ノードのはずで、この時、実際にノード○a を追加するときの木は次の図のようになる。




この木の状態は、赤ノード ○z の左が赤ノード ○a になって、
赤黒木の条件 4. を満たさなくなっている。
※ 4. 赤のノードの子ノードはすべて黒である。
このときの ○z と ○a の関係をここでは、(赤)左(赤)状態とよぶことにする。

崩れてしまった条件 4. を木の回転で平衡を取り戻してみる。




回転によって○z の右ノードの根から葉までの黒ノードの数は変わらないけれど、○z の左ノードの根から葉までの黒ノードの数は一つ減っているので、○a-1 で表す。

このとき ○a の色を黒に変えれば左側のノードは、根から葉までの黒ノードの数を一つ増やせることがわかる。実際に変えてみると図は次のようになる。




無事に追加できたけれど、ここで木の回転の前の ●y の他のノードとの関係を考えてみる。
●y は黒ノードだったので、回転の前の ●y は次の 5つ場合があり得る。
  1. ●y は根だった場合。
  2. 黒ノード ●x の左ノードだった場合。
  3. 黒ノード ●x の右ノードだった場合。
  4. 赤ノード ○x の左ノードだった場合。
  5. 赤ノード ○x の右ノードだった場合。
つまり、回転の後の木の状態は次の図のどれかのはず。
この 5つのどの図にあるか調べることが必要なとき、ここでは赤ノード ○z を(赤)頭状態と呼ぶことにする。



図の中の 1. 〜 4. の木の状態は、ここまでの説明で出てきた形になっていることがわかる。
  1. ノードの追加(根)
  2. ノードの追加(黒ノードの左) … (黒)左(赤)状態
  3. ノードの追加(黒ノードの右) … (黒)右(赤)状態
  4. ノードの追加(赤ノードの左) … (赤)左(赤)状態
赤黒木の条件または、left-leaning 赤黒木の追加条件を満たしていない 1. と 3. と 4. は同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。

同じように 5. の図は、次で説明するノードの追加(赤ノードの右)と同じ形になって同じ操作を繰り返すことで、親ノードを一つ含めた部分木の平衡を取り戻すことができる。

(赤)頭状態は、一段づつ根に近づきながら、最終的に (黒)左(赤) 状態になって、left-leaning 赤黒木の 6つの全ての条件を満たして操作が終わるか、根まで登って操作が終わる。

left-leaning 赤黒木(red-black tree) - ノードの追加(黒ノードの右)

追加するノード○aが、ある末端の黒ノード●zより大きいとき(●z<○a)を考えてみる。

実際に追加すると木は次の図になる。


新しく赤ノード○aが追加された木は、赤黒木の 5つの条件を満たしているけれど、left-leaning の追加条件を満たしていない。
※ 6. 全ての赤ノードは、黒ノードの左側の子ノードである。

この●zと○aの関係をここでは、(黒)右(赤) 状態と呼ぶことにする。

ここで、条件 6. を満たすようにするために、木の回転を行って平衡を取り戻してみる。


回転後は、○aの左右で平衡が崩れて、○aの右側の葉は根までの黒ノードの数が一つ少なくなってしまっている。この状態を■-1で表すことにする。

この状態は ○aを黒にして ●zを赤に色を変えれば ●aの左側のノードは、根から葉までの黒ノードの数を変えずに、●aの右側のノードの根から葉までの黒ノードの数を一つ増やせることがわかる。実際に変えてみると図は次のようになる。


黒ノード●a の左に赤ノード○z がぶら下がる形になったので、○z は left-leaning 赤黒木の追加条件 6. を満たしている。

また ●a は黒ノードなので、●a がある黒ノードの左右どちらかの子ノードであっても、ある赤ノードの左右どちらかの子ノードであっても、left-leaning 赤黒木の追加条件 6. を崩すことなないし、赤黒木の条件 2. を満たしている。
※ 2. 根は黒である。

さらに、崩れていた赤黒木の条件 5. が色の入れ替えで木の根から葉までの黒ノードの数が同じになって条件を満たすようになった。
※ どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である。

無事にノードの追加ができた。

2009年9月4日金曜日

left-leaning 赤黒木(red-black tree) - ノードの追加(黒ノードの左)

追加するノード○aが、ある末端の黒ノード●zより小さいか等しいとき(a≦z)を考えてみる。
※ a<z でもできるけれど、左ノードに追加した方が平衡に戻す操作が少くて済みそうなきがする。

実際に追加すると木は次の図になる。

新しく赤ノード○aが追加された木は、left-leaning 赤黒木の追加条件 6 も含めて赤黒木の条件を全て崩すことなく追加できた。

left-leaning 赤黒木(red-black tree) - ノードの追加(根)

ノードの追加は、二分探索木と同じように根からノードとたどっていずれかの葉へ追加するけれど、この時、必ず赤色で追加する。
※ 赤で追加すれば赤黒木の条件5.の木の高さを満たしたまま追加できるから。

まず、木が空のときについて考える。
木が空の場合に追加される場所は根。
上記のとおり赤ノードで追加すると木は次の図になる。
※ 図の中の■は葉
この状態は、赤黒木の条件 2 だけを満たしていない。
つまり、追加した赤ノードを黒に変えるだけで赤黒木の全ての
条件を満たすことができる。
実際に、色を変えると木は次の図になる。
赤ノードが木の中にないので、いうまでもないけれど
left-leaning 赤黒木の追加条件 6 も満たしている。
※ 全ての赤ノードは、黒ノードの左側の子ノードである

2009年9月3日木曜日

left-leaning 赤黒木(red-black tree) - 説明の中で使う用語と記号

次の用語は Wikipedia にならって表記する。
  • ノード・根・葉・親・子・部分木・木の回転
次の用語をこの説明の中で独自に使うことにする。

 末端ノード - ある葉の親ノードのこと。

次の記号をこの説明の中で独自に使うことにする。

 ● - 黒ノードのこと、特定の黒ノード x は●の右肩に x を付けて●x と表記する。
 ○ - 赤ノードのこと、特定の赤ノード y は○の右肩に y を付けて○y と表記する。
 ◎ - 赤か黒か未確認のノード、特定の未確認ノード z は同様に◎z と表記する。
 ■ - 葉のこと。

2009年9月2日水曜日

left-leaning 赤黒木(red-black tree) - はじめに

効率的なデータ構造は? と聞かれたら、データベースなどで使われている B木(B-tree) を思い浮かべるけれど、自分で実装するとなると、だいぶ気が重い。

そこで、たやすく実装できる、程良く効率的なデータ構造を知りたくて、実装がやさしそうな二分探索木の平衡木にしぼって調べることにする。

まったく知識がない赤や黒が出てくるような平衡木は避けて AVL木から手をつけてみる。

はじめは良さそうに思えたけれど、節(node)の追加と削除について詳しくかかれているいくつかのサイトを見ると、追加と削除の場合分けが多いし、平衡の基準が厳しすぎて、節の左右の平衡を保つための操作が増えるので、追加と削除が多いデータには不向きという記述もある。

平衡を保つための木の回転という操作はわかった気がするので、ひとまずよしとしておく。

他の平衡二分探索木を調べ始めるけれど、やさしそうなものは見あたらず、あきらめて赤や黒の出てくる赤黒木(red-black tree)を読みといてみる。

赤黒木(red-black tree)
※ 引用元(http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8)

[性質]
  1. 各ノードは赤か黒の色をもつ。
  2. 根は黒である。
  3. 葉はすべて黒である(したがって、赤のノードは子をもつ)。
  4. 赤のノードの子ノードはすべて黒である(したがって、対偶より、赤のノードの親ノードもすべて黒である)。
  5. どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である(この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる)。
これらの条件から、次の赤黒木の重要な性質が導かれる。
  • 根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない。

わずか 5つの条件で上記の性質(●)が導かれるのは、いまひとつ実感がないけれどいろいろな場合を紙に描いて図にすると、
最短の葉の根からの節の色は黒黒黒黒黒で、
最長の葉の根からの節の色は黒赤黒赤黒赤黒赤黒となって
たしかにそのとおりになってる。

また、木から節の追加や削除をするときに行う平衡を保つための操作が、その節の深さを気にしなくても、その節の色を気にするだけで平衡を保っている。

すばらしい。赤黒木を考え付いた人は天才だ。

詳しくかかれているいくつかのサイトを見ると、赤黒木も節の追加と削除に操作は場合分けが多いので、全ての場合を理解するには時間がかかりそう。

いろいろと赤黒木について検索していると、赤黒木の改良でさらに実装がやさしい left-leaning 赤黒木と呼ばれる平衡二分探索木が 2008年に発表されたという記述を見つけた。
→ http://wtnb.mydns.jp/wordpress/archives/4719

赤黒木の性質にあとひとつ制限を加えればよいとかかれている。
Wikipedia と同じように表現してみると、次のようになるのだろうか。

  1. 全ての赤ノードは、黒ノードの左側の子ノードである。

現時点では下記のサイトで原文の PDF 文書が公開されているので、必要ならダウンロードできる。

→ http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

これは良さそうな気がするので、さっそく節の追加と削除について日本語で解説されているサイトを検索してみたけれど、その解説を理解するのに必要な知識が足りなかったり、追加と削除の操作の手順がはぶかれすぎていたりで繰り返し読んでみてもわからない。

そこで、自分で考えてみることにした。
以下の解説で前提とする知識の階層は次のとおり。
※ ただし、赤黒木は木の性質を押さえておけば、追加と削除の操作方法は不要。

赤黒木(red-black tree)
↑
木の回転(tree rotaion)
↑
二分探索木(binary search tree)
↑
連結リスト(linked list)

Wikipedia に記事が掲載されているので不明なところを補えるはず。

2009年9月1日火曜日

CentOS on VMware Server - VMware Server インストール

PC で作業ができなくなってしまうことを避けるために
Windows XP 上に Windows 用の VMware Server を導入する。
構成は以下のとおり。

CentOS(ゲストOS)
↑↑↑
VMware Server(Windows 用)
↑↑↑
Windows XP(ホストOS)
↑↑↑
PC(Pentium D 3.00Ghz, 2GB RAM)

早速ダウンロードして、インストール開始。
※ 現時点では次のサイトからダウンロードできた。

→ http://www.vmware.com/products/server/

もう少し説明がほしいなら下記記事が参考になるかもしれない。

→ http://itpro.nikkeibp.co.jp/article/COLUMN/20070904/281136/
→ http://www.atmarkit.co.jp/flinux/special/vmware/vmwarea.html

インストールにつまづきそうな所はなさそうだけれど、
途中で DHCP Server サービスがインストールされて、
有効になるので気を付けたい。
IT 部門からお叱りを受けないように、[コントロールパネル] 内の
[サービス] を監視して、すぐ無効にできるよう準備しておこう。
※ サービス名は "VMware DHCP Service"