令和7年度 春期 午前 問6

✓ これが正解ウ5(3(1(0, 2), 4), 7(6, −))

解説

1、0を加えると節点2で偏りが出て、右回転で釣り合いを取ります。

AVL 木は、どの節点でも左右の部分木の高さの差が 1 以下に保たれる 2 分探索木です。初期の木に 1 を加えると値 2 の左に 1 が付き、ここでは高さの差はまだ範囲内に収まっています。続けて 0 を加えると、値 2 の左部分木の高さが 2、右が 0 になり、高さの差が 2 に開いてしまいます。開きが値 2 の左の左に生じているので、値 2 を回転軸として右方向に回転させ、値 1 を新しい親、その左を 0、その右を 2 とする形に組み替えれば、全ての節点で高さの差が 1 以下に戻ります。他の位置は動かないので、上位の 5 の下では左が 3(1(0,2), 4)、右が 7(6,−) となる木が答えです。

ほかの選択肢はなぜ違うのか

• ア3(1(0, 2), 5(4, 6(−,…：3(1(0,2), 5(4, 6(−,7))) の形を挙げる肢は、値 5 と 7 まで動かす広い範囲の回転を書いています。挿入で崩れているのは値 2 の周りだけなので、右部分木まで組み替える必要はありません。
• イ4(2(1(0, −), 3), 6(5…：4(2(1(0,−),3), 6(5,7)) の形を挙げる肢は、根を 5 から 4 に置き換え、値 3 を含む位置関係まで並べ直しています。局所の崩れを直せば足りるので、根まで動かすのは過剰です。
• エ5(3(1(0, 2), 4), 6(−…：5(3(1(0,2), 4), 6(−,7)) の形を挙げる肢は、右部分木側の 7(6,−) を 6(−,7) の形に書き換えています。右部分木では釣り合いが崩れていないので、こちらは手を加えないのが正しい姿です。