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

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

次のルールに従って赤黒木を作成してください。

さらに、M 個の値 a_i が 与えられます。 a_i が木に含まれる場合、赤黒木を先行順で走査したときに a_i を訪問する順番を、木に含まれない場合、 -1 を出力してください。

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

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

先行順について

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

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

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

木構造について

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

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

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

赤黒木について

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

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

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

・ 二分探索木のアルゴリズムに従ってノードを「赤」として木に挿入する
・ 対象の親ノードも「赤」の場合
    ・ 対象の叔父（親の親の反対側の子）ノードも「赤」の場合
        ・ 親ノードと叔父ノードを「黒」に変更、祖父ノードを「赤」に変更
    ・ 対象の叔父（親の親の反対側の子）ノードが「黒」の場合
        ・ 祖父ノードを対象ノードと逆方向に回転、回転後に対象ノードの兄弟となったノードを「赤」に変更
・ 根ノードを「黒」に変更