二分探索木の回転（複合） Ruby編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
N 個の整数 t1, t2, ..., tN と整数 ai と回転方向 ri が 2 組与えられます。
ri = 0 の時は左回転を、ri = 1 の時は右回転を表します。
次のルールに従って二分探索木を作成した後、値が ai であるノードを ri の方向に回転し、木のノードを先行順で訪問した結果を出力してください。
なお、値が ai であるノードは ri の方向に回転できることが保証されています。
全てのノードについて、以下が成り立つ
・ 入力で与えられる t1, t2, ..., tN の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい
木構造について
木構造は、ノード同士が関係性を持つことで作ることができます。
この問題で各ノードが持つべき情報は以下の通りです。
・ ノードの値
・ 親ノードの情報
・ 左の子ノードの情報
・ 右の子ノードの情報
- 入力される値
-
N
t1 t2 ... tN
a1 r1
a2 r2
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
作成した木の N 個のノードの値 ti を先行順で訪問した結果を出力してください。
訪問先にノードがある場合、訪問したノードの値 ti を1行ずつ出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ N ≦ 100
・ 1 ≦ ti ≦ 1000
・ ai ∈ t
・ ri = 0 または、ri = 1
・ ti ≠ tj (i ≠ j)
- 入力例1
-
5
1 2 3 4 5
3 0
1 0
- 出力例1
-
2
1
4
3
5
- 入力例2
-
7
4 2 5 3 1 6 7
6 0
4 1
- 出力例2
-
2
1
4
3
5
7
6
