木構造とグラフ
配列やリスト、スタックやキューは、データが一直線に並ぶ「線形データ構造」でした。しかし現実のデータは、親子関係や路線図、SNSの交友関係のように多方向に分岐し、ときに循環します。こうした複雑なつながりをモデル化する「木構造」と「グラフ構造」を学びましょう。
1. 木構造（Tree Structure）：階層関係のモデル
木構造（Tree）は、根から枝分かれする樹木のように、データが階層的に繋がるデータ構造です。
木構造は、主に以下の要素で構成されます。
- ルート（根：Root）： 木の最上部に位置する唯一の出発点ノード。
- ノード（節・要素：Node）： データを持つ個々の箱。
- エッジ（枝・辺：Edge）： ノード同士を結ぶ線。
- リーフ（葉：Leaf）： 下にこれ以上子供を持たない末端のノード。
応用としての「二分探索木（Binary Search Tree）」
木構造の特別なルールとして、「左側の子孫の値 ≦ 親の値 ≦ 右側の子孫の値」という制約をかけたものを二分探索木と呼びます。 この木構造を使うと、ルートから「左右のどちらに進むか」を判定するだけで、目的のデータを O(log N) で検索・挿入できます。
2. グラフ構造（Graph Structure）：網の目のネットワーク
木構造は「親子関係」しか表せませんが、上下のない横同士の自由なつながりや循環する関係も表現できるのがグラフ構造（Graph）です。
グラフは、頂点（ノード／バーテックス：Vertex）と、頂点間を結ぶ辺（エッジ：Edge）の集合として定義されます。
- 無向グラフ： 辺に矢印（向き）がないグラフです。繋がりは双方向です。（例：Facebookの友達関係、双方向の道路網）
- 有向グラフ： 辺に矢印（向き）があり、一方通行の繋がりを表現できます。（例：Twitter/Xのフォロー関係、一方通行の道路網、ウェブページのリンク構造）
現実世界への応用：最短ルート探索やSNS
グラフ構造は、私たちの生活の裏側で驚くほど使われています。 最も身近な例が地図アプリの乗換案内やカーナビです。駅や交差点を「頂点」、路線や道路を「辺」としてグラフを構築し、ダイクストラ法などのアルゴリズムで最短ルートを一瞬で算出しています。
Googleの初期の検索技術「ページランク（PageRank）」も、ウェブページを頂点、リンクを有向辺とする巨大グラフの中で、どのページが価値あるかを数学的に分析する仕組みでした。
次のセクションでは、データ構造の上に成り立つアルゴリズムの代表例として、バラバラのデータを規則正しく並び替える「ソートアルゴリズム」について学びます。