図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。

選択肢

• ア根3、左の子1（左の子0、右の子2）、右の子5（左の子4、右の子6（さらに右の子7））
• イ根4、左の子2（左の子1（左の子0）、右の子3）、右の子6（左の子5、右の子7）
• ウ根5、左の子3（左の子1（左の子0、右の子2）、右の子4）、右の子7（左の子6）
• エ根5、左の子3（左の子1（左の子0、右の子2）、右の子4）、右の子6（右の子7）

正解と解説

正解：ウ 根5、左の子3（左の子1（左の子0、右の子2）、右の子4）、右の子7（左の子6）

AVL木は各節点で左右部分木の高さの差を1以内に保つ平衡2分探索木である。まず1を追加しても各節点の高さの差は1以内に収まるため回転は起きないが、続けて0を追加すると2を根とする部分木で左に偏り高さの差が2になる。左の左に偏った形なので1を軸に右回転し、1が親、0と2がその左右の子になる。結果として根5の左部分木が「1を親に0と2」を左にもつ形へ整い、他の部分は変わらない。

選択肢ごとの解説

• ア根が3に変わっているが、この追加では根を回転させる必要はない。
• イ根が4になる形で、元の木からの回転結果と一致しない。
• ウ正解。2の位置で右回転が1回起き、1が0と2の親になる形に整う。
• エ回転後の右部分木の形が元の木と食い違っており、追加操作で変化しないはずの部分が崩れている。

同じ分野の他の問題

• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5
• 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当て…2023年度 春期 午前 問5