問題
図の2分探索木に1と0の二つの要素を順に追加した AVL 木として、適切なものはどれか。（図中の各木の選択肢ア〜エから選ぶ）
選択肢
- 1ア
- 2イ
- 3ウ
- 4エ
正解
3. ウ
詳しい解説を見る解説を閉じる
解説
AVL木は、全ノードで左右部分木の高さの差が1以内に保たれる平衡2分探索木である。元の木（根5、左3〔子2,4〕、右7〔子6〕）に、まず1を2分探索木として追加すると 5→3→2 とたどりノード2の左に1が付く。続いて0を追加すると 5→3→2→1 とたどり1の左に0が付き、この部分が左に2段連なって平衡が崩れる。崩れた0,1,2の並びに対し中央の1を持ち上げる回転で再平衡すると、ノード3の左の子が1（その左に0、右に2）となる。根5・右7〔子6〕は変わらず、全ノードで高さの差が1以内に収まる。これに一致するのはウである。よってウが正解。（出典: 令和7年度 春期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習