AP過去問令和7年度春期午前問6 - 版の履歴

Yo-net: /* 回答・解説 */

2025-04-23T14:06:51Z

回答・解説

← 古い版		2025年4月23日 (水) 23:06時点における版
174行目:		174行目:
	/		/
	X		X

	Y		Y
	/ \		/ \

Yo-net: /* 回答・解説 */

2025-04-23T14:06:23Z

回答・解説

← 古い版		2025年4月23日 (水) 23:06時点における版
166行目:		166行目:
	</div>		</div>
	<script></yjavascript>		<script></yjavascript>


			LL型
			Z
			/
			Y
			/
			X

			Y
			/ \
			X Z

			RR型
			Z
			\
			Y
			\
			X

			Y
			/ \
			Z X

			LR型

			Z
			/
			Y
			\
			X

			X
			/ \
			Y Z

			RL型

			Z
			\
			Y
			/
			X

			X
			/ \
			Z Y

2025年4月23日 (水) 11:51にYo-netによる

2025-04-23T11:51:47Z

← 古い版		2025年4月23日 (水) 20:51時点における版
94行目:		94行目:
	.db_table-wrapper {		.db_table-wrapper {
	width: 100%;		width: 100%;
	~~max-width: 600px;~~
	margin: auto;		margin: auto;
	}		}

Yo-net: /* 回答・解説 */

2025-04-23T11:50:37Z

回答・解説

@@ 91行目: / 91行目: @@
 <yjavascript></script>
    <div class="db_table-wrapper">
      <table class="db_table">

Yo-net: /* 回答・解説 */

2025-04-23T11:49:15Z

回答・解説

← 古い版		2025年4月23日 (水) 20:49時点における版
88行目:		88行目:

	が答えです。		が答えです。


	~~《AVL木の4種類の回転操作》~~

	~~不均衡の種類不均衡の原因必要な操作説明~~
	~~'''LL型'''（左-左）左部分木の左に追加 '''右回転'''（Right Rotation）単純な右回転で修正~~
	~~'''RR型'''（右-右）右部分木の右に追加 '''左回転'''（Left Rotation）単純な左回転で修正~~
	~~'''LR型'''（左-右）左部分木の右に追加 '''左回転 → 右回転''' 左部分木を左回転してから、親を右回転~~
	~~'''RL型'''（右-左）右部分木の左に追加 '''右回転 → 左回転''' 右部分木を右回転してから、親を左回転~~

Yo-net: /* 回答・解説 */

2025-04-23T11:46:43Z

回答・解説

← 古い版		2025年4月23日 (水) 20:46時点における版
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>

Yo-net: /* 回答・解説 */

2025-04-23T11:38:07Z

回答・解説

← 古い版		2025年4月23日 (水) 20:38時点における版
73行目:		73行目:
	すべて -1, 0, 1にはなっていません。バランスが崩れたので、操作が必要です。		すべて -1, 0, 1にはなっていません。バランスが崩れたので、操作が必要です。


			'''左-左型（LL型）'''の不均衡なので、'''「右回転（Right Rotation）」'''でバランスを取ります。


			ノード1をノード2の位置に移動して、ノード2はノード1の右に子として接続します。ノード0はノード1の左側の子の状態になります。

2025年4月23日 (水) 11:30にYo-netによる

2025-04-23T11:30:58Z

@@ 19行目: / 19行目: @@
-AVL木は、'''Adelson-Velsky and Landis木'''の略です。
+　AVL木は、'''Adelson-Velsky and Landis木'''の略です。
-この名称は、1962年にこのデータ構造を提案したソビエト連邦の数学者、'''G.M. Adelson-Velsky''' 氏と '''E.M. Landis''' 氏の名前に由来しています。彼らが発表した論文「An algorithm for the organization of information」で紹介されました。
+　この名称は、1962年にこのデータ構造を提案したソビエト連邦の数学者、'''G.M. Adelson-Velsky''' 氏と '''E.M. Landis''' 氏の名前に由来しています。彼らが発表した論文「An algorithm for the organization of information」で紹介されました。
-AVL木は、'''自己平衡二分探索木'''の最初の一つであり、各ノードにバランス係数（左右の部分木の高さの差）を保持し、その値が -1、0、+1 の範囲に収まるように挿入・削除時に回転操作を行うことで、常に木の高さを制御し、探索の効率を保つことを目的としています。
+　AVL木は、'''自己平衡二分探索木'''の最初の一つであり、各ノードにバランス係数(左右の部分木の高さの差)を保持し、その値が -1、0、+1 の範囲に収まるように挿入・削除時に回転操作を行うことで、常に木の高さを制御し、探索の効率を保つことを目的としています。

2025年4月23日 (水) 09:56にYo-netによる

2025-04-23T09:56:44Z

← 古い版		2025年4月23日 (水) 18:56時点における版
16行目:		16行目:

	=='''回答・解説'''==		=='''回答・解説'''==
			与えられた図の上部にある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 の範囲に収まるように挿入・削除時に回転操作を行うことで、常に木の高さを制御し、探索の効率を保つことを目的としています。

2025年4月23日 (水) 09:22にYo-netによる

2025-04-23T09:22:16Z

← 古い版		2025年4月23日 (水) 18:22時点における版
8行目:		8行目:

	=='''問6(問題文)'''==		=='''問6(問題文)'''==
			図の2分探索木に1と0の二つの要素を順に追加したAVL木として、適切なものはどれか。


	ア		[[ファイル:AP R7 1Spring AMQ6 Fig1.png\|400px\|\|none\|]]

	イ

	ウ

	エ

AP過去問 令和7年度春期 午前 問6 - 版の履歴

Yo-net: /* 回答・解説 */

Yo-net: /* 回答・解説 */

2025年4月23日 (水) 11:51にYo-netによる

Yo-net: /* 回答・解説 */

Yo-net: /* 回答・解説 */

Yo-net: /* 回答・解説 */

Yo-net: /* 回答・解説 */

2025年4月23日 (水) 11:30にYo-netによる

2025年4月23日 (水) 09:56にYo-netによる

2025年4月23日 (水) 09:22にYo-netによる

AP過去問令和7年度春期午前問6 - 版の履歴