概要

情報技術の基礎として理解しておきたい データ構造 のうち、配列、スタック、キュー、リスト、ハッシュ、木構造、ヒープを整理する。

配列の番地計算、リストのつなぎ替え、ヒープの修復を具体的なデータで追う。速さを比較するときは探す・挿入する・次の一件を取り出すという操作を分けて考える。

この記事の構成

• 配列
  配列：複数の類似データを連続的に集約したデータ型の総称。
• スタック/キュー
  スタック：後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。
• 線形リスト
  参照のつなぎ替えを追い、挿入位置の探索と挿入そのもののコストを区別。
• ハッシュ
  ハッシュ関数：キーを一定の計算ルールでハッシュ値に変換する関数のこと。
• 木構造の分類
  木構造の分類と各項目の特徴を整理。
• ヒープ
  根を取り出した後の修復を追い、優先度付きキューに適する理由を確認。

配列

• 配列
  複数の類似データを連続的に集約したデータ型の総称。

• 静的配列
  作成時に要素数を決め、後から長さを変更しない配列。

• 動的配列
  要素の追加や削除に応じて長さを変更できる配列。
  異なるデータ型を格納できるかどうかは使用するプログラム言語の型システムによる。

• 添字から直接アクセスできる理由
  要素が4 byteずつ連続して並び、先頭アドレスが1000で、添字が0から始まる配列を考える。添字3の要素の先頭は \(1000+4\times3=1012\) と計算できる。前の要素を順に読まなくても位置が分かるので、固定長要素の配列では添字アクセスを \(O(1)\) と扱える。

  一方、 [A, B, C, D] のBの直前にXを挿入して順序を保つなら、後方の要素をずらす必要がある。アクセスが速いという性質と途中への挿入が速いという性質は別である。

スタック/キュー

• スタック
  後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。
  スタックにデータを入れることをpush、データを出すことをpopという。

• キュー
  先入れ先出し（FIFO：First In First Out）のデータ構造のこと。
  キューにデータを入れることをenqueue、データを出すことをdequeueという。

• 同じ三つのデータでも取り出す順序が変わる
  A、B、Cの順に入れた場合、スタックからはC、B、A、キューからはA、B、Cの順に取り出す。スタックは「直前の操作を先に取り消す」履歴、キューは「先に受け付けた仕事から処理する」待ち列に対応する。

  ただし緊急度の高い仕事を先に取り出したいなら、単純なキューの到着順では目的を満たさない。その場合は優先度付きキューが候補になる。構造の名前から選ぶより次に何を取り出す必要があるかを先に決めるとよい。

線形リスト

※ 線形リストは単にリストとも呼ばれる。

• 線形リスト
  順序付けされた関連データを集約したデータ構造のこと。

  各ノードはデータ値を保持するデータ部と次または前のノードを参照するポインタ部で構成される。リスト全体を管理する構造が先頭ノードや末尾ノードへの参照を別に保持する場合もある。

• 単方向リスト
  ポインタ部に次データへのポインタのみ保持するリスト。

• 双方向リスト
  ポインタ部に次データと前データへのポインタを保持するリスト。

• 環状リスト
  末尾ノードの次データへのポインタが先頭ノードを指すリスト。

• 挿入が定数時間になるのは位置が分かっている場合
  単方向リストA→B→CでAの直後にXを挿入する。まずXの次をBに設定し、その後Aの次をXに変えると、A→X→B→Cになる。他の要素を移動する必要はない。

  ここで \(O(1)\) なのは Aへの参照をすでに持っている状態でのつなぎ替え である。先頭から「値がAの要素」を探す時間まで含めると、探索は最悪 \(O(n)\) になる。配列と比べる際には位置を探す処理とデータを変更する処理を分ける必要がある。

ハッシュ

• ハッシュ関数
  キーを一定の計算ルールでハッシュ値に変換する関数のこと。
  ハッシュテーブルではハッシュ値を格納位置を決めるために使う。

  例えば\(h(x) = x \bmod n\) では複数の \(x\) が同じハッシュ値になる。このように異なるキーが同じハッシュ値になることを衝突という。
  暗号学的ハッシュ関数に求められる一方向性はハッシュテーブルの定義そのものではない。

• ハッシュテーブル（ハッシュ表）
  キー（key）と値（value）を対応付けて格納するデータ構造。
  キーのハッシュ値から格納位置を求め、その位置でキーを照合して値を探索する。

  • 例 : ハッシュ関数を \(h(x) = x \bmod n\) とし、異なるキー \(a\)、\(b\) のハッシュ値が一致する条件を考える。

    → 「ハッシュ値が一致する」ことより、次のように置ける。
    \(a = a^{\prime} \times n + m\)
    \(b = b^{\prime} \times n + m\)
    （\(a^{\prime}, b^{\prime}\) は整数、\(m\) は共通するハッシュ値）

    よって
    \(a - b = n (a^{\prime} - b^{\prime})\)

    また、\(a^{\prime}\ -\ b^{\prime}\) は整数である。

    よって
    \(a - b\) が \(n\) の倍数であることが条件となる。

• ハッシュ値が一致してもキーは一致しない
  ハッシュ値を「整数キーを10で割った余り」とすると、12も22も2になる。格納場所2に候補を集めることはできるが、余りだけではどちらのデータか判別できない。

  チェイン法なら場所2につないだ候補の元のキーを比較して目的の要素を探す。ハッシュ値は候補を絞るための情報であり、キーの一致を確認する処理まで省けるわけではない。特定の場所に衝突が偏ると、この候補比較が長くなり、平均的には速いという利点が失われる。

木構造の分類

• 木構造
  木構造はグラフとして見ると連結で閉路を持たない構造となる。
  根付き木はルート（根）、ノード（節）、ノード間をつなぐエッジ（枝）、リーフ（葉）から構成される。

  ※ 上記は応用数学の「5. グラフ理論」で触れた記載と同じ。
  → 応用情報技術 - 応用数学 > グラフ理論

• \(2\) 分木
  子ノードの数が \(2\) つ以下である木構造。
  実用例としてデータの大小関係を木構造でたどる \(2\) 分探索木や構文・文法を表現する構文木などがある。

• 多分木
  各ノードが任意の数の子ノードを持てる木構造。

• 完全 \(2\) 分木
  最下層以外のノードがすべて埋まり、最下層のノードが左から順に詰められた \(2\) 分木。
  実用例としてバイナリヒープがある。

• AVL木
  各ノードの左右の部分木の高さの差を \(1\) 以下に保つ高さ平衡 \(2\) 分探索木。
  完全 \(2\) 分木とは別の概念となる。

• B木
  一つのノードに複数のキーと子を持てる平衡した多分探索木。
  木の高さを抑えられるため、データベースやファイルシステムの索引などで使われる。

• 二分探索木でも形が偏れば探索が遅くなる
  空の二分探索木へ1、2、3、4をこの順で単純に挿入すると、右の子だけが続く形になる。4を探すには1→2→3→4とたどるため、要素数に比例した比較が必要になる。

  大小関係を守ることと高さを低く保つことは別の条件である。高さが \(O(\log n)\) に保たれる平衡二分探索木なら探索も \(O(\log n)\) になるが、一般の二分探索木にはその保証がない。

ヒープ

• ヒープ
  親子間で一定の大小関係を保つ木構造で、バイナリヒープは完全 \(2\) 分木として構成される。最小ヒープでは各親が子以下、最大ヒープでは各親が子以上となるため、根が全体の最小値または最大値となる。

  全要素から最大値または最小値を取り出す場合に適したデータ構造。

  最小値を求める場合、子要素は親要素以上となるように構成する。
  最大値を求める場合、子要素は親要素以下となるように構成する。

• 最小値を取り出した後並び全体をソートする必要はない
  配列で表した最小ヒープ [2, 5, 3, 9, 7] を考える。親は子以下になっているが、配列全体は昇順ではない。根の2を取り出したら、末尾の7を根へ移して [7, 5, 3, 9] とし、小さい方の子3と交換すると [3, 5, 7, 9] になる。

  修復するのは根から下へたどる一つの経路であり、完全二分木の高さに比例する \(O(\log n)\) の処理で済む。最小値の取得を繰り返す用途に向く一方、任意の値を探すときには二分探索木のように左右のどちらかへ絞れるとは限らない。

まとめ

• スタックは最後に入れたデータを先に取り出すLIFO、キューは先に入れたデータを先に取り出すFIFO。
• 配列は添字によるアクセスに向き、リストは挿入や削除を伴う構造変更に向く。
• ハッシュ表ではキーをハッシュ関数へ渡してハッシュ値を求め、高速な探索に利用。
• 木は閉路を持たない階層的なグラフとして、階層データの表現に使われる。
• ヒープは親子間の大小関係を保つ木構造で、優先度付きキューなどに利用される。
• データ構造のヒープとメモリ領域のヒープは同じ名称でも意味が異なる。

• 配列の直接アクセス、リストのつなぎ替え、ヒープの最小値取得にはそれぞれ異なる前提がある。位置の探索を含むかどうかまでそろえて処理量を比べる。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• Python公式チュートリアル - データ構造（日本語・リスト、スタック、キュー、集合の公式解説）
• NIST Dictionary of Algorithms and Data Structures - Array（英語・配列の公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Hash table（英語・ハッシュ表の公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Tree（英語・木構造の公的用語定義）