http://www.kt.rim.or.jp/~kbk/zakkicho/07/zakkicho0707.html#D20070704-4
ネタニマジレ(ry
ま、読みはともかく、あれ見て、 AVL 木を使って似たようなことをやろうと思ったけど面倒なのでやってない。誰かやってくれないかなー。
ちなみに、 STL の map は赤黒木。 Haskell の Data.Map は AVL 木。 glib の binary balanced tree も AVL 木。あとツリーっぽいデータコンテナを持ってるのって何があったかなー。
AVL木と赤黒木だと、赤黒木の方が条件が緩いので構築しやすいと言われているし、実際に評価をしてみても挿入は赤黒木の方が速いようなんだけど(回転が起こりづらいからだろう)、実装としては AVL 木の方がずっと楽なんですよね。速度もそれほど差はなく、条件が厳しいぶん、探索速度としては AVL 木の方が上なので、そっちの方がいいとオレは思うんだけどなーとか思ったり思わなかったり。というかなあ、赤黒木は(とくに削除では)いろんな場合が多すぎて面倒くさい。
ところで確認のために glib の g_tree のコードを見てみたけど、確かに AVL 木ですね。でもなんで while で実装してるのかが謎。再帰で書いた方が楽だと思うし、 そのせいで MAX_GTREE_HEIGHT という定数(40)に深さが限定されてんのね。うーん、これはアリなのか……。
深さが一定以上になるといきなりマシンが落ちるという状態を避けたい、とか？ 明示的にハンドリングしたいという意味ではありか。ま、そもそも平衡木で深さが40ってかなりありえないノード数だからいいんですけど。
関係ないけど、
Rails無しのRubyをどう使えばいいのだろう．
は「Rubyって tDiary を動かすのに必要なヤツだっけ？」に並ぶ名台詞だと思いました。むかし tDiary、いま rails。