データ構造と木構造

要点と定義

データ構造は、データの並べ方や関係付け、追加・検索・削除などの操作を定める仕組みです。配列・リスト・スタック・木など、構造によって操作の手順が変わります。公式シラバスでは、配列、リスト、スタックとキュー、木構造などを扱います。

木構造は、節を枝でつないだ階層構造です。親をもたない節を根、子をもたない節を葉と呼びます。二分木では、一つの節がもつ子は最大二つです。配列の添字を０から始めて完全二分木を表すと、添字ｉの左の子は２ｉ＋１、右の子は２ｉ＋２、親は⌊（ｉ−１）÷２⌋です。例えば添字２の子は５と６です。

最大ヒープは、すべての親の値が子の値以上になる二分木です。この局所的な親子関係から、根が最大値だと分かります。一方、兄弟同士や親子でない節同士の大小関係は決まりません。ヒープを配列で表す方法は、木の関係と値の配置を対応させるのに使えます。

二分探索木では、各節について左部分木の値がその節より小さく、右部分木の値が大きくなります。条件は子だけでなく部分木全体に適用されます。例えば根が８なら、その右部分木に７を置くことはできません。探索時は比較結果に応じて左か右へ進み、条件によって不要な側を調べずに済みます。重複値の扱いは、ここで示された大小条件だけでは決まりません。

スタックは、最後に追加したデータを最初に取り出す後入れ先出しの構造です。追加をプッシュ、取り出しをポップと呼びます。再帰呼出しでは、呼出しごとの処理状態をスタックに積むため、処理は最後の呼出しから先に戻ります。

リストは要素を順につないだ構造です。配列状のリストでは、位置ｉの要素を削除すると後続要素が詰まり、削除前のｉ＋１番目がｉ番目に移ります。ハフマン木の作成では、親が未作成の節から値の小さい二つを選び、合計値をもつ親を作る操作を繰り返します。配列表現では、parentが−１の節を親未作成として扱い、候補が二つ以上ある間に親を作ります。

適用条件と例

最大ヒープに新しい値を加えるときは、まず末尾に置き、親と比べます。子の値が親より大きければ交換し、親の位置へ移動して同じ確認を続けます。例えば[18, 12, 15, 4, 9, 7]の末尾に20を加えると、添字６の親は２です。20と15を交換し、続いて添字２の親である０の18とも交換すると、[20, 12, 18, 4, 9, 7, 15]になります。これで親が子以上という条件が保たれます。

最大値を取り出して昇順に並べるヒープソートでは、根と対象範囲の末尾を交換し、対象範囲を一つ縮めます。次に根から下へヒープを再構成します。各段階で子が二つあるなら大きい方を選び、親より大きい場合に交換します。例えば[60, 30, 45, 15, 5, 10, 20]で根と末尾を交換すると、根は20になります。子の30と45のうち大きい45を選んで交換します。小さい子を選ぶと、もう一方の子より親が小さいままになり、ヒープ条件を満たさないことがあります。子の添字が対象範囲内かも確認します。

二分探索木を確かめるときは、各節から左右の部分木全体の値を確認します。例えば根４の左側に４より小さい値、右側に４より大きい値があり、各部分木でも同じ規則が続くなら条件を満たします。