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

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

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

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

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

・ 入力で与えられる t1, t2, ..., tN の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい
・ 左右の部分木の高さの差は常に 1 以下

先行順について

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

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

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

木構造について

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

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

・ ノードの値
・ 親ノードの情報
・ 左の子ノードの情報
・ 右の子ノードの情報

AVL 木について

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

これまでの二分探索木の特徴に加えて、全てのノードが持つ左右の部分木は高さの差が 1 以下を保ち続けるという特徴があります。

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

・ 二分探索木のアルゴリズムに従ってノードを木に挿入する
・ 挿入した葉から根までノードを遡って以下の操作を行う
    ・ 現在のノードの左右部分木の高さの差が 2 以上の場合
        ・ 回転操作を用いて左右部分木の高さを 1 以下にする
    ・ 1 つ親のノードに移る