図の 2 分探索木に 1 と 0 の二つの要素を順に追加した AVL 木として,適切なものはどれか。
根を 3 とし,左部分木を 1(左に 0,右に 2),右部分木を 5(左に 4,右に 6,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)とする木。
正解は「ウ」です。
2 分探索木に 1 と 0 を順に追加します。まず 1 は,5→3→2 とたどって 2 の左の子として追加されます。この時点では各節点で左右の部分木の高さの差は 1 以下であり,回転は不要です。
次に 0 は,5→3→2→1 とたどって 1 の左の子として追加されます。このとき節点 2 で左部分木の高さが 2 大きくなり,AVL 木の平衡条件(左右の部分木の高さの差が 1 以下)を満たさなくなります。これは左の子の左側が伸びた「左左(LL)型」の不均衡なので,節点 2 を中心に右回転を行います。
その結果,節点 1 が 2 の位置に上がり,1 の左の子が 0,右の子が 2 となります。最終的な木は,根が 5,左部分木が 3(左に 1(その左に 0,右に 2),右に 4),右部分木が 7(左に 6)となり,選択肢ウと一致します。
本文が同じ・似ている問題を表示しています