「AP過去問 令和7年度春期 午前 問6」の版間の差分
(→回答・解説) |
(→回答・解説) |
||
| 78行目: | 78行目: | ||
ノード1をノード2の位置に移動して、ノード2はノード1の右に子として接続します。ノード0はノード1の左側の子の状態になります。 | ノード1をノード2の位置に移動して、ノード2はノード1の右に子として接続します。ノード0はノード1の左側の子の状態になります。 | ||
したがって答えは、 | |||
<span style = "background:linear-gradient(transparent 75%, #7fbfff 75%); font-weight:bold; "> | |||
ウ</span> | |||
が答えです。 | |||
《AVL木の4種類の回転操作》 | |||
不均衡の種類 不均衡の原因 必要な操作 説明 | |||
'''LL型'''（左-左） 左部分木の左に追加 '''右回転'''（Right Rotation） 単純な右回転で修正 | |||
'''RR型'''（右-右） 右部分木の右に追加 '''左回転'''（Left Rotation） 単純な左回転で修正 | |||
'''LR型'''（左-右） 左部分木の右に追加 '''左回転 → 右回転''' 左部分木を左回転してから、親を右回転 | |||
'''RL型'''（右-左） 右部分木の左に追加 '''右回転 → 左回転''' 右部分木を右回転してから、親を左回転 | |||
<yjavascript></script> | |||
<div class="db_table-wrapper"> | |||
<table class="db_table"> | |||
<caption class="db_caption">AVL木の4種類の回転操作</caption> | |||
<thead> | |||
<tr> | |||
<th>不均衡の種類</th> | |||
<th>不均衡の原因</th> | |||
<th>必要な操作</th> | |||
<th>説明</th> | |||
</tr> | |||
</thead> | |||
<tbody> | |||
<tr> | |||
<td>'''LL型'''（左-左）</td> | |||
<td>左部分木の左に追加</td> | |||
<td>'''右回転'''（Right Rotation）</td> | |||
<td>単純な右回転で修正</td> | |||
</tr> | |||
<tr> | |||
<td>'''RR型'''（右-右）</td> | |||
<td>右部分木の右に追加</td> | |||
<td>'''左回転'''（Left Rotation）</td> | |||
<td>単純な左回転で修正</td> | |||
</tr> | |||
<tr> | |||
<td>'''LR型'''（左-右）</td> | |||
<td>左部分木の右に追加</td> | |||
<td>'''左回転 → 右回転'''</td> | |||
<td>左部分木を左回転してから、親を右回転</td> | |||
</tr> | |||
<tr> | |||
<td>'''RL型'''（右-左）</td> | |||
<td>右部分木の左に追加</td> | |||
<td>'''右回転 → 左回転'''</td> | |||
<td>右部分木を右回転してから、親を左回転</td> | |||
</tr> | |||
</tbody> | |||
</table> | |||
</div> | |||
<script></yjavascript> | |||
2025年4月23日 (水) 20:46時点における版
AP過去問 令和7年度春期 午前 問5前の問題へ
AP過去問 令和7年度春期 午前 問7次の問題へ
問6(問題文)
図の2分探索木に1と0の二つの要素を順に追加したAVL木として、適切なものはどれか。
回答・解説
与えられた図の上部にある2分探索木(根が5の木)に対して、1と0をこの順序で挿入し、その後のAVL木(自己平衡二分探索木)として適切なものを選ぶ問題です。
AVL木は、Adelson-Velsky and Landis木の略です。
この名称は、1962年にこのデータ構造を提案したソビエト連邦の数学者、G.M. Adelson-Velsky 氏と E.M. Landis 氏の名前に由来しています。彼らが発表した論文「An algorithm for the organization of information」で紹介されました。
AVL木は、自己平衡二分探索木の最初の一つであり、各ノードにバランス係数(左右の部分木の高さの差)を保持し、その値が -1、0、+1 の範囲に収まるように挿入・削除時に回転操作を行うことで、常に木の高さを制御し、探索の効率を保つことを目的としています。
ノードの左と右の高さを調べて、すべてのノードにおいて-1、0、1となる場合は、バランスが崩れていないと判断できます。
1を追加すると、ノード2の左側にノード1として、追加することになります。なんで？2の左側にっていうのは木構造がそういうルールだからです。すべてのノードの左にはそのノードより小さい数だけが右には大きい数だけがぶら下がる決まりです。
では追加した後のそれぞれの左と右の高さを比べて、その差を見てみましょう。
ノード1は高さ0
ノード2の左は高さ1、右は無いから0で、1-0は1
ノード3の左は高さ2、右は1で2-1は1
ノード5の左は高さ3、右は2で3-2は1
ノード6は高さ0
ノード7は左は高さ1右はは0で1-0で1
すべて -1, 0, 1になってますので、この時点ではバランスが取れているので、1を追加する操作の後になにもやることはないです。
では、つづいて0を追加してみましょう。これはノード1の左に追加することになります。それでまた、高さの差について確認します。
ノード0は高さ0
ノード1の左は高さ1、右は無いから0で、1-0は1
ノード2の左は高さ2、右は無いから0で、2-0は2
ノード3の左は高さ3、右は1で3-1は2
ノード5の左は高さ4、右は2で4-2は2
ノード6は高さ0
ノード7は左は高さ1右はは0で1-0で1
すべて -1, 0, 1にはなっていません。バランスが崩れたので、操作が必要です。
左-左型（LL型）の不均衡なので、「右回転（Right Rotation）」でバランスを取ります。
ノード1をノード2の位置に移動して、ノード2はノード1の右に子として接続します。ノード0はノード1の左側の子の状態になります。
したがって答えは、
ウ
が答えです。
《AVL木の4種類の回転操作》
不均衡の種類 不均衡の原因 必要な操作 説明 LL型（左-左） 左部分木の左に追加 右回転（Right Rotation） 単純な右回転で修正 RR型（右-右） 右部分木の右に追加 左回転（Left Rotation） 単純な左回転で修正 LR型（左-右） 左部分木の右に追加 左回転 → 右回転 左部分木を左回転してから、親を右回転 RL型（右-左） 右部分木の左に追加 右回転 → 左回転 右部分木を右回転してから、親を左回転
| 不均衡の種類 | 不均衡の原因 | 必要な操作 | 説明 |
|---|---|---|---|
| '''LL型'''（左-左） | 左部分木の左に追加 | '''右回転'''（Right Rotation） | 単純な右回転で修正 |
| '''RR型'''（右-右） | 右部分木の右に追加 | '''左回転'''（Left Rotation） | 単純な左回転で修正 |
| '''LR型'''（左-右） | 左部分木の右に追加 | '''左回転 → 右回転''' | 左部分木を左回転してから、親を右回転 |
| '''RL型'''（右-左） | 右部分木の左に追加 | '''右回転 → 左回転''' | 右部分木を右回転してから、親を左回転 |
AP過去問 令和7年度春期 午前 問5前の問題へ
AP過去問 令和7年度春期 午前 問7次の問題へ