赤黒木を実装
最近、業務委託で参画させていただいてる会社の方から新たな言語を使うときは
まず赤黒木を作ってみるといいよと聞きGoで実装してみましたー
red-black-treeコマンドに引数で数字を渡すと赤黒木として表示させる実装になってます
赤黒木について
赤黒木は「平衡木」というデータ構造のひとつで、ツリー構造のうち、根ノードから子を持たない末端の葉ノードまでの深さがなるべく等しくなるような構造になります。
ざっくりとした特徴でいえば
- 二分木の一種ですが、ノードを赤と黒で色分けする
- 根から葉までがほぼ同じ数のノードを経由するため探索する際の平均の計算時間を短縮することができる
- ノードの挿入や削除時に深さのバランスが保たれるようバランス(回転)と呼ばれる操作で、ツリーの再構築を行う
赤黒木の実装に次の条件を満たす必要がある
- 各ノードは赤または黒に区分される
- あるノードが赤ならばその子ノードは必ず黒である。黒の子ノードには制限はない
- 根ノードから末端の葉ノードまでの黒ノードの個数（黒深さ）はどの経路でも同じ
- 根ノードは黒である
実装
lispで書かれてますがこちらを参考にGoで実装しました
http://www.geocities.jp/m_hiroi/clisp/clispb03.html
実装コードはこちら
https://github.com/fujimisakari/red-black-tree
実装自体は、引数から取得した数字(ノード)配列を 「ツリーへ挿入 → 回転」 を再帰的に繰り返しいくだけなのでアルゴリズムを理解できていれば実装自体の難しさはないと思います。
自分の場合は回転させるとなぜ深さのバランスが整っていくのかを理解するのが大変でした。
回転させるパターンはいくつもあるのでコードを書く前に紙でいろんな条件を書いて回転させてみないと理解が進みませんでした。
ツリー構造出力を実装する際の空白スペース幅の計算が結構苦労しました。
いろんな方法で実装してみましたが、根ノードから末端の葉ノードへ再帰で進め行く経路毎に親ノードと子ノードの情報(数字)を保存して
出力時はその情報から空白スペース幅を計算して実装する方法が一番シンプルで良さげでした。