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

赤ノード ○^z の左の黒ノード ●^a を取り除く場合を考えてみる。

●^a を取り除くと ○^z の左側は、葉から根までの黒ノードの数が他の葉より一つ少なくなって平衡が崩れてしまう。

「ノードの削除(赤ノードの右の黒)」と同様に ●^y の色を赤に変えると ○^z-1 となって、○^z-1 と ○^y の関係は (赤)右(赤) 状態となる。

「ノードの追加(赤ノードの右)」と同じように操作すると、

○^y-1 は (赤)頭^-1 状態になるので、色を黒に変えて平衡をとりもどす。

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

赤ノード ○^z の右の黒ノード ●^a を取り除く場合を考えてみる。

●^a を取り除くと ○^z の右側は、葉から根までの黒ノードの数が他の葉より一つ少なくなって平衡が崩れてしまう。この黒ノードが一つ少ない葉を ■^-1 で表す。

ひとまず ○^z の右と左で平衡を取り戻すために ●^y の色を赤に変えてみる。すると ○^z の左側の葉から根までの黒ノードの数が一つ減って ○^y-1 となる。○^z の左と右のどちらも葉から根までの黒ノードの数がその他より一つ少いので、左右の -1 を取り除いて ○^z-1 と描ける。

このとき ○^z-1 と ○^y は (赤)左(赤)の状態にあるので、「ノードの追加(赤ノードの左)」と同様に操作してみる。
赤ノード ○^z-1 は黒ノードの左ノードのはず。

この回転の前と後で ○^z-1 の右左の葉から根までの黒ノードの数の影響を考えてみる。

• ○^z-1 の右は、親の黒ノードが一つ減って右に追加されたので±0
• ○^z-1 の左は、親の黒ノードが一つ減って、赤ノード○^y の色が黒になったので±0

つまり、この回転の前と後では葉から根までの黒ノードの数に影響はないことがわかる。(影響があったら赤黒木の回転にならないから考えるまでもないけれど)

赤ノード ○^z-1 は葉から根までの黒ノードの数が他よりも一つ少いことを除くと、6つの left-leaning 赤黒木の全ての条件を満たしている。この ○^z-1 の状態をここでは (赤)頭^-1 状態と呼ぶことにする。

(赤)頭^-1 は、その赤ノードの色を黒へ変えると葉から根までの黒ノードの数が一つ増えて -1 が解消されので、6つの left-leaning 赤黒木の全ての条件がみたされるようになる。

left-leaning 赤黒木(red-black tree) - ノードの削除(末端ノード)

末端ノード◎^a を取り除くとき、その位置と色で 3つの場合に分けてみる。

1. 赤ノードのとき
2. 赤ノードの子を持つ黒ノードのとき
3. 赤ノードの子を持たない黒ノードのとき

1.の取り除くノード ○^a の色が赤のときを考えてみる。
赤ノードなので ○^a は黒ノードの左のはず。このとき取り除いた後も 6つの left-leaning 赤黒木の条件を全て満たしていることがわかる。

2.の取り除くノード ●^a が赤色の子ノード ○^z を持つときを考えてみる。

●^a が取り除かれたことで ○^z の葉と根までの黒ノード数が一つ減って ○^z-1 と変わって、木の枝が切れてしまっている状態となる。

まず ○^z-1 を ●^a のあった位置に移す。
次に ○^z-1 の色を黒に変ると ○^z-1 の葉から根までの間の黒ノードの数が一つ増えて ●^z となり 6つの left-leaning 赤黒木の条件を満たすようになることがわかる。

最後に 3.の赤ノードの子を持たない黒ノードを取り除くときについて 4つの場合に分けてみた。

1. 赤ノードの右の黒ノードを取り除くとき
2. 赤ノードの左の黒ノードを取り除くとき
3. 黒ノードの右の黒ノードを取り除くとき
4. 黒ノードの左の黒ノードを取り除くとき

次回から、この 4つの場合を一つずつ考えてみる。

left-leaning 赤黒木(red-black tree) - ノードの削除(削除ノードの補充)

まず、あるノード◎^a をリストから取り除く場合を考えてみる。

◎^aが末端の赤ノードなら left-leaning 赤黒木の 6つの条件をどれも崩さないで取り除けるけれど(下の図)

そうでない場合はその取り除かれた場所にどこからかノードを見繕って補充することが必要になってしまう。

二分探索木の場合はノードの補充を次のどちらかで行えるけれど、left-leaning 赤黒木の場合は 2. の方が平衡を取り戻すために必要な操作の数が少そうなので 2. で行ってみる。

1. 削除するノード ◎^a の左の子の部分木の中から最も大きな値のノードを補充に使う。
2. 削除するノード ◎^a の右の子の部分木の中から最も小さな値のノードを補充に使う。

もちろん赤黒木なので ◎^a の色は赤のときと黒のときがあるけれど、赤ノード○^a を取り除くときは ◎^z の色を赤で補充すればよいし、黒ノード●^a を取り除くときは ◎^z の色を黒で補充できる。

また、補充を済ませた木の形(下図の左側)は、取り除かれるノードが末端のときの木(下図の右側)とおなじ形になるので、あとは、末端のノードが取り除かれたときについて考えれば良いことになる。

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

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

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

この木の状態は、赤ノード ○^z の右が赤ノード ○^a になって、
赤黒木の条件 4. を満たさなくなっている。
※ 4. 赤のノードの子ノードはすべて黒である。

さらに、left-leaning 赤黒木の追加条件 6. も崩れている。
※ 6. 全ての赤ノードは、黒ノードの左側の子ノードである。

この赤ノード ○^z の状態を (赤)右(赤) 状態と呼ぶことにする。

崩れてしまった 2つの条件を木の回転で取り戻してみる。

この木の状態は、前回の説明のノードの追加(赤ノードの左)と同じ形で、赤ノード ○^a は (赤)左(赤) 状態になった。

さらに、(赤)左(赤) のときに赤黒木の条件 4. 満たすための操作をすると (赤)頭状態になる。

(赤)頭状態のときに気にしなければならないことは前回の説明で終えているので、left-leaning 赤黒木のノードの追加するときについての全ては説明が済んだことになる。

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

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

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 も満たしている。
※ 全ての赤ノードは、黒ノードの左側の子ノードである

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

次の用語は Wikipedia にならって表記する。

• ノード・根・葉・親・子・部分木・木の回転

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

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

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

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

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 と同じように表現してみると、次のようになるのだろうか。

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

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

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

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

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

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

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

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"