赤黒木(続)

結局LLRBではなく純正赤黒木を作ることにした。というかJavaのTreeMapの実装をそのまま移植したともいう。
テストができてないが、とりあえずいいだろう。

一つ前の記事で、メモリ効率と書いたが、よく考えればそんなものどうでもよくて、重要な点は順序があることだった。実装してて気づいた。馬鹿か俺は(カカシ風)
この赤黒木はSchemeのAPIにもするつもりではあるが、元々は組み込みの文字セットを実装するためのものである。なので、ハッシュテーブルのようにオーダーがなくなるようなものではなく、データの挿入時にオーダーが保たれるものじゃないと困るわけだ。(範囲等の関係で)

正直赤黒木の中身がどうなっているのかいまいち理解してないが、(2-3-4木を二分木で表現したものということくらいしか・・・)、単に使うだけなら問題あるまい。問題が出たら直せばいいわけだし。
木の回転とバランスが命だということは実装(コピー)してて気づいたが・・・