赤黒木の実装 C編（paizaランク A 相当）

N 個の整数 t₁, t₂, ..., t_N が与えられます。

次のルールに従って 赤黒木を作成し、木のノードを先行順で訪問した結果を出力してください。

全てのノードについて、以下が成り立つ

・ 入力で与えられる t1, t2, ..., tN の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい
・ すべてのノードは「赤」か「黒」の色を持つ
・ 根ノードは必ず「黒」
・ あるノードからその子孫の葉までの「黒ノード数」は全て同じ
・ ノードの色は「赤」が連続しない
・ 全てのはノードは「黒」

先行順について

先行順とは、根から順に左部分木、右部分木を訪問する操作方法です。

先行順は再帰を用いた以下のアルゴリズムによって実装できます。

・ 訪問したノードを出力する
・ 左の子がある場合、左の子を訪問する
・ 右の子がある場合、右の子を訪問する
・ 親ノードに戻る

木構造について

木構造は、ノード同士が関係性を持つことで作ることができます。

この問題で各ノードが持つべき情報は以下の通りです。

・ ノードの値
・ ノードの色（「赤」または「黒」）
・ 親ノードの情報
・ 左の子ノードの情報
・ 右の子ノードの情報

赤黒木について

赤黒木は二分探索木のうちの 1 種類です。

これまでの二分探索木の特徴に加えて、全てのノードはノードの情報に「赤」、「黒」のどちらかを持ち、あるノードからその子孫の葉までの「黒ノード数」は全て同じという特徴があります。

赤黒木は以下のアルゴリズムによって実装できます。

・ 二分探索木のアルゴリズムに従ってノードを「赤」として木に挿入する
・ 対象の親ノードも「赤」の場合
    ・ 祖父が存在しない場合は「黒」とみなす
    ・ 対象の叔父（親の親の反対側の子）ノードも「赤」の場合
        ・ 親ノードと叔父ノードを「黒」に変更、祖父ノードを「赤」に変更
        ・ 祖父ノードを新たな対象ノートして同様の処理を継続する
    ・ 対象の叔父（親の親の反対側の子）ノードが「黒」の場合
        ・ 親ノードが祖父ノードの左の子の場合
            ・ 対象ノードが親ノードの右の子の場合
                ・ 親ノードを左回転する、祖父ノードを右回転する
                ・ 回転後の親ノードを「黒」、回転後の子ノードを「赤」に変更
            ・ 対象ノードが親ノードの左の子の場合
                ・ 祖父ノードを右回転する
                ・ 回転後の親ノードを「黒」、回転後の子ノードを「赤」に変更
        ・ 親ノードが祖父ノードの右の子の場合
            ・ 対象ノードが親ノードの左の子の場合
                ・ 親ノードを右回転する、祖父ノードを左回転する
                ・ 回転後の親ノードを「黒」、回転後の子ノードを「赤」に変更
            ・ 対象ノードが親ノードの右の子の場合
                ・ 祖父ノードを左回転する
                ・ 回転後の親ノードを「黒」、回転後の子ノードを「赤」に変更
・ 根ノードを「黒」に変更