ノードの追加は、二分探索木と同じように根からノードとたどっていずれかの葉へ追加するけれど、この時、必ず赤色で追加する。
※ 赤で追加すれば赤黒木の条件5.の木の高さを満たしたまま追加できるから。
まず、木が空のときについて考える。
木が空の場合に追加される場所は根。
上記のとおり赤ノードで追加すると木は次の図になる。
※ 図の中の■は葉
この状態は、赤黒木の条件 2 だけを満たしていない。
つまり、追加した赤ノードを黒に変えるだけで赤黒木の全ての
条件を満たすことができる。
実際に、色を変えると木は次の図になる。
赤ノードが木の中にないので、いうまでもないけれど
left-leaning 赤黒木の追加条件 6 も満たしている。
※ 全ての赤ノードは、黒ノードの左側の子ノードである
2009年9月4日金曜日
2009年9月3日木曜日
left-leaning 赤黒木(red-black tree) - 説明の中で使う用語と記号
次の用語は Wikipedia にならって表記する。
末端ノード - ある葉の親ノードのこと。
次の記号をこの説明の中で独自に使うことにする。
● - 黒ノードのこと、特定の黒ノード x は●の右肩に x を付けて●x と表記する。
○ - 赤ノードのこと、特定の赤ノード y は○の右肩に y を付けて○y と表記する。
◎ - 赤か黒か未確認のノード、特定の未確認ノード z は同様に◎z と表記する。
■ - 葉のこと。
- ノード・根・葉・親・子・部分木・木の回転
末端ノード - ある葉の親ノードのこと。
次の記号をこの説明の中で独自に使うことにする。
● - 黒ノードのこと、特定の黒ノード 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)
[性質]
わずか 5つの条件で上記の性質(●)が導かれるのは、いまひとつ実感がないけれどいろいろな場合を紙に描いて図にすると、
最短の葉の根からの節の色は黒黒黒黒黒で、
最長の葉の根からの節の色は黒赤黒赤黒赤黒赤黒となって
たしかにそのとおりになってる。
また、木から節の追加や削除をするときに行う平衡を保つための操作が、その節の深さを気にしなくても、その節の色を気にするだけで平衡を保っている。
すばらしい。赤黒木を考え付いた人は天才だ。
詳しくかかれているいくつかのサイトを見ると、赤黒木も節の追加と削除に操作は場合分けが多いので、全ての場合を理解するには時間がかかりそう。
いろいろと赤黒木について検索していると、赤黒木の改良でさらに実装がやさしい left-leaning 赤黒木と呼ばれる平衡二分探索木が 2008年に発表されたという記述を見つけた。
→ http://wtnb.mydns.jp/wordpress/archives/4719
赤黒木の性質にあとひとつ制限を加えればよいとかかれている。
Wikipedia と同じように表現してみると、次のようになるのだろうか。
現時点では下記のサイトで原文の PDF 文書が公開されているので、必要ならダウンロードできる。
→ http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
これは良さそうな気がするので、さっそく節の追加と削除について日本語で解説されているサイトを検索してみたけれど、その解説を理解するのに必要な知識が足りなかったり、追加と削除の操作の手順がはぶかれすぎていたりで繰り返し読んでみてもわからない。
そこで、自分で考えてみることにした。
以下の解説で前提とする知識の階層は次のとおり。
※ ただし、赤黒木は木の性質を押さえておけば、追加と削除の操作方法は不要。
赤黒木(red-black tree)
↑
木の回転(tree rotaion)
↑
二分探索木(binary search tree)
↑
連結リスト(linked list)
Wikipedia に記事が掲載されているので不明なところを補えるはず。
そこで、たやすく実装できる、程良く効率的なデータ構造を知りたくて、実装がやさしそうな二分探索木の平衡木にしぼって調べることにする。
まったく知識がない赤や黒が出てくるような平衡木は避けて AVL木から手をつけてみる。
はじめは良さそうに思えたけれど、節(node)の追加と削除について詳しくかかれているいくつかのサイトを見ると、追加と削除の場合分けが多いし、平衡の基準が厳しすぎて、節の左右の平衡を保つための操作が増えるので、追加と削除が多いデータには不向きという記述もある。
平衡を保つための木の回転という操作はわかった気がするので、ひとまずよしとしておく。
他の平衡二分探索木を調べ始めるけれど、やさしそうなものは見あたらず、あきらめて赤や黒の出てくる赤黒木(red-black tree)を読みといてみる。
赤黒木(red-black tree)
※ 引用元(http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8)
[性質]
- 各ノードは赤か黒の色をもつ。
- 根は黒である。
- 葉はすべて黒である(したがって、赤のノードは子をもつ)。
- 赤のノードの子ノードはすべて黒である(したがって、対偶より、赤のノードの親ノードもすべて黒である)。
- どのノードからも、子孫にあたる葉までの道に含まれる黒いノードの数は、一定である(この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる)。
- 根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない。
わずか 5つの条件で上記の性質(●)が導かれるのは、いまひとつ実感がないけれどいろいろな場合を紙に描いて図にすると、
最短の葉の根からの節の色は黒黒黒黒黒で、
最長の葉の根からの節の色は黒赤黒赤黒赤黒赤黒となって
たしかにそのとおりになってる。
また、木から節の追加や削除をするときに行う平衡を保つための操作が、その節の深さを気にしなくても、その節の色を気にするだけで平衡を保っている。
すばらしい。赤黒木を考え付いた人は天才だ。
詳しくかかれているいくつかのサイトを見ると、赤黒木も節の追加と削除に操作は場合分けが多いので、全ての場合を理解するには時間がかかりそう。
いろいろと赤黒木について検索していると、赤黒木の改良でさらに実装がやさしい left-leaning 赤黒木と呼ばれる平衡二分探索木が 2008年に発表されたという記述を見つけた。
→ http://wtnb.mydns.jp/wordpress/archives/4719
赤黒木の性質にあとひとつ制限を加えればよいとかかれている。
Wikipedia と同じように表現してみると、次のようになるのだろうか。
- 全ての赤ノードは、黒ノードの左側の子ノードである。
現時点では下記のサイトで原文の 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"
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"
2009年8月31日月曜日
CentOS on VMware Server - まえがき
PC 故障のためこの一年間 3度も PC を入れ替えて、その度に
- OS インストール
- HDD 内のファイルの移動
- 各ソフトウェアのインストールと再設定
の繰り返し。
そろそろなんとかしたいと思い、VM(Virtual Machine) のゲスト
OS に作業環境を作ってみることにする。
プレインストールされている Windows XP 以外に追加
ライセンスはないし、主に使用しているソフトウェアは
下記ぐらいなので、
- Webブラウザ(Firefox, Internet Explorer)
- eメールクライアント(Thunderbird, Windows Live Mail)
- インスタントメッセンジャー(Pidgin)
- 表計算ソフト(Microsoft Excel 2000)
- アーカイブ形式(.zip, .cab)
- 暗号化ソフト(GnuPG)
Internet Explorer と Windows Live Mail を使うのを止めて
Excel の代わりに OpenOffice.org を使えば、
ゲスト OS を Linux にしても問題なし、
ディストリビュージョンは CentOS を選択。
.cab は普段扱っていたファイルの圧縮が良好だったのと
Windows 上では、解凍ソフトがなくても読み取り専用の
フォルダの様に開けるので、お気に入りだったけれど
Linux で無理に使いつづける理由はない。
まずは Microsoft Virtual PC 2007 SP2 のゲストとして
CentOS のインストールを試してみたけれど
標準オプションのままでは、グラフィカルインストールが
進まないので断念。
Virtual PC 2007 はサービスで動作していないことと、
(自分の環境では)一つのゲスト OS が異常終了すると、
全部のゲストを道連れにしていくことの 2点で不便を
感じていたので、今回は VMware Server 2 を導入してみることにした。
- OS インストール
- HDD 内のファイルの移動
- 各ソフトウェアのインストールと再設定
の繰り返し。
そろそろなんとかしたいと思い、VM(Virtual Machine) のゲスト
OS に作業環境を作ってみることにする。
プレインストールされている Windows XP 以外に追加
ライセンスはないし、主に使用しているソフトウェアは
下記ぐらいなので、
- Webブラウザ(Firefox, Internet Explorer)
- eメールクライアント(Thunderbird, Windows Live Mail)
- インスタントメッセンジャー(Pidgin)
- 表計算ソフト(Microsoft Excel 2000)
- アーカイブ形式(.zip, .cab)
- 暗号化ソフト(GnuPG)
Internet Explorer と Windows Live Mail を使うのを止めて
Excel の代わりに OpenOffice.org を使えば、
ゲスト OS を Linux にしても問題なし、
ディストリビュージョンは CentOS を選択。
.cab は普段扱っていたファイルの圧縮が良好だったのと
Windows 上では、解凍ソフトがなくても読み取り専用の
フォルダの様に開けるので、お気に入りだったけれど
Linux で無理に使いつづける理由はない。
まずは Microsoft Virtual PC 2007 SP2 のゲストとして
CentOS のインストールを試してみたけれど
標準オプションのままでは、グラフィカルインストールが
進まないので断念。
Virtual PC 2007 はサービスで動作していないことと、
(自分の環境では)一つのゲスト OS が異常終了すると、
全部のゲストを道連れにしていくことの 2点で不便を
感じていたので、今回は VMware Server 2 を導入してみることにした。
2009年5月25日月曜日
部分 xhtml をとりあえず表示する xsl
- 部分 xhtml の先頭に一行追加(xml 宣言がある場合はその次の行)
<?xml-stylesheet type="text/xsl" href="transform.xsl"?>
- transform.xsl
<?xml version="1.0" encoding="utf-8"?> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns="http://www.w3.org/1999/xhtml"> <xsl:output method="html" encoding="utf-8" omit-xml-declaration="no" doctype-public="-//W3C//DTD XHTML 1.1//EN" doctype-system="http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"/> <xsl:template match="/"> <html xmlns="http://www.w3.org/1999/xhtml" lang="ja"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title></title> <style type="text/css"> /* @import url("./style.css");*/ * { font-size:100%; font-family:Meiryo, MSPGothic, Sans-Serif; } p, pre { font-size:85%; } dd { margin:0; } </style> </head> <body> <xsl:apply-templates select="node()" /> </body> </html> </xsl:template> <xsl:template match="node()"> <xsl:copy> <xsl:apply-templates select="@*|node()" /> </xsl:copy> </xsl:template> <xsl:template match="@*"> <xsl:copy /> </xsl:template> </xsl:stylesheet>
2009年1月12日月曜日
<a> button
<style type="text/css">
a.button {
display:inline-block;
border:solid 1px gray;
vertical-align:middle;
background-color:#eee;
padding:0.25em 0.5em;
}
</style>
<div>
<a class="button" href="javascript:alert('Button A');">Button A</a>
<a class="button" href="javascript:alert('Button B');">Button B</a>
</div>
登録:
投稿 (Atom)

.png)