そこで、たやすく実装できる、程良く効率的なデータ構造を知りたくて、実装がやさしそうな二分探索木の平衡木にしぼって調べることにする。
まったく知識がない赤や黒が出てくるような平衡木は避けて 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 に記事が掲載されているので不明なところを補えるはず。
