データ構造（探索木・区間・文字列）

細かい話題を束ねた概念ページ。各節は元は独立ページだった。

平衡探索木 (Balanced Search Tree)

二分探索木は素朴に構築すると探索の worst case が $\mathcal{O}(n)$ に退化するため、木を平衡（balance）させて高さを $\mathcal{O}(\log n)$ に抑える各種データ構造の総称。

主な木

• Red-Black Tree — 探索・挿入・削除をいずれも worst case $\mathcal{O}(\log n)$ で行える。実用的なバランス木の代表。
• B-Tree / B+Tree — RDBMS のインデックスで使われる。ノードを大きく取りブロックデバイス（HDD等）と相性が良く、worst case でも検索 $\mathcal{O}(\log N)$。
• Splay Tree / Heap — アクセス局所性を利用した自己調整木。
• Red-Green Trees — 永続性（immutable な赤ノード＋可変な緑ノード）を持つ木。Rust の構文木ライブラリ rowan で採用される。

ポイント

• 平衡条件をどう維持するか（回転・分割・マージ）が各データ構造の差別化点。永続性が要る用途では Red-Green のように構造共有を前提に設計する。

関連: data-structures / data-structures / _moc-cs

セグメント木 (Segment Tree)

区間に対するクエリ（区間和・区間最小など）と一点更新を $\mathcal{O}(\log N)$ で処理する木構造。競技プログラミングの主力データ構造。

要点

• 配列を完全二分木に乗せ、各内部ノードに子区間の集約値を持たせる
• モノイド で抽象化でき、結合則を満たす任意の演算（和・min・max・gcd 等）に適用可能
• 遅延評価 (lazy propagation) により区間更新も $\mathcal{O}(\log N)$ で扱える

空間分割木（関連）

• 四分木 (Quadtree) — 2 次元空間を再帰 4 分割し、衝突判定などを高速化する。モートン符号（Z オーダー曲線）で領域をインデックス化する。

関連する探索テクニック

• 01-BFS — 辺コストが 0 か 1 のグラフで deque を使い最短路を線形時間で求める。セグ木とは別だが競プロ頻出の最短路高速化。

関連: data-structures / competitive-programming / _moc-cs

Trie と文字列探索 (Aho-Corasick)

Trie (トライ木)

接頭辞 (prefix) を共有して文字列集合を格納する木。「重複する部分列を共有する」という発想で、辞書引きや前方一致検索を高速に行える。多くの文字列アルゴリズムの土台となる。

Aho-Corasick

複数のパターン文字列を入力テキストから一括かつ高速に探索するアルゴリズム。計算量 $\mathcal{O}(N+M)$。

• Trie を構築し、各ノード（例: abc）からその最長 suffix を表すノード（bc → c → root）へ failure link を張る
• マッチに失敗したときこのリンクを辿ることでバックトラックなしに探索を継続できる

関連: ハッシュ

• Zobrist hashing — 集合や盤面状態をハッシュ化する手法。要素ごとに乱数を割り当て XOR で集約することで、増減を差分更新できる。ゲーム木探索の局面ハッシュなどで使う。

関連: data-structures / game-tree-search / _moc-cs