2010年2月22日月曜日

Network 設定

contentpath
hosts/etc/hosts
hostname/etc/sysconfig/network
ipaddress/etc/sysconfig/network-scripts/ifcfg-eth0
dns/etc/resolv.conf

Windows でよく使うフォント

Family Name Note Sample
ArialThe quick brown fox jumps over the lazy dog. 0123456789
TahomaThe quick brown fox jumps over the lazy dog. 0123456789
VerdanaThe quick brown fox jumps over the lazy dog. 0123456789
Century GothicMicrosoft OfficeThe quick brown fox jumps over the lazy dog. 0123456789
Courier NewmonospaceThe quick brown fox jumps over the lazy dog. 0123456789
Lucida ConsolemonospaceThe quick brown fox jumps over the lazy dog. 0123456789
HGGothicMmonospace, Microsoft OfficeThe quick brown fox jumps over the lazy dog. 0123456789
MeiryoMicrosoft Download CenterThe quick brown fox jumps over the lazy dog. 0123456789
  • HGGothicM 系の HGPGothicM と HGSGothicM は英数字の幅が詰まりすぎで残念
  • HGGothicE は HGGothicM の太字体

2009年9月25日金曜日

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つの場合を一つずつ考えてみる。

2009年9月11日金曜日

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

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

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


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

二分探索木の場合はノードの補充を次のどちらかで行えるけれど、left-leaning 赤黒木の場合は 2. の方が平衡を取り戻すために必要な操作の数が少そうなので 2. で行ってみる。
  1. 削除するノード ◎a の左の子の部分木の中から最も大きな値のノードを補充に使う。
  2. 削除するノード ◎a の右の子の部分木の中から最も小さな値のノードを補充に使う。

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

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

2009年9月6日日曜日

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 赤黒木のノードの追加するときについての全ては説明が済んだことになる。