二分木はにぶんぎでしょう

This entry was posted by on Thursday, 5 July, 2007

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。

Category: Uncategorized
You can follow any responses to this entry via RSS.
Both comments and trackbacks are currently closed.

2 Responses to “二分木はにぶんぎでしょう”

  1. jijixi
    2007/07/04 at 16:49

    Scala の scala.collection.immutable パッケージには色々ありますよ＜ツリーなの
    つ http://www.scala-lang.org/docu/files/api/scala/collection/immutable$content.html

    あと、OCaml の Map とか Set とか。

  2. 向井
    2007/07/05 at 01:19

    ↑は書いてて「OCamlにあったっけ」と思ってました。もう忘れとる。すいませんすいません。 Map のコードを見てみたけど AVL 木ですね。 Scala はまだ見ておりません。
    ありがとうございます。