「AP過去問 令和7年度春期 午前 問6」の版間の差分
編集の要約なし |
編集の要約なし |
||
| 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日 (水) 18:56時点における版
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 の範囲に収まるように挿入・削除時に回転操作を行うことで、常に木の高さを制御し、探索の効率を保つことを目的としています。
AP過去問 令和7年度春期 午前 問5前の問題へ
AP過去問 令和7年度春期 午前 問7次の問題へ