赤黒木の罠

レポートの参考データとして、単純な二分探索木と赤黒木で挿入結果がどうなるか比較しようと思い立ったところまでが前回のお話。

とりあえずこことかここらへんを参考にCでゴリゴリと実装しはじめたはいいものの、ポインタと再帰が頭の中で複雑に絡まり合ってなかなかまともに動かない。ここの時点で金曜日の朝6時。ゲームやって寝る。

そして金曜夕方5時に起床。赤黒木が怖いのでゲームやってると数学ガールが届く。マックに行って適当なものを食べながら数学ガールを読みながら赤黒木のことを考える。と、ここで色々と考えていたことの線が繋がりはじめる。赤黒木の挿入はバックトラックを伴う場合があるから、末尾再帰で書こうとすると大変なことになる（それまで末尾再帰で書こうとしていた）から、末尾呼出じゃない再帰で処理すればいいんじゃないか、と。ひととおり考えがまとまったところで足早に席を立ち、帰宅。

で、新しい方法で書き直しはじめて3時間くらいで小さい赤黒木ならばまともに挿入されることが確認できるようになった。←いまここ