Advanced Data Structures（高度なデータ構造）

引用

Brass, P. (2008). Advanced Data Structures. Cambridge University Press.

章の要約

本書は474ページで、内容の9章、付録の章、500を超える文献リスト、著者索引と事項索引からなる。Cambridgeは、応用アルゴリズムの特別な話題としてのデータ構造の考え方、解析、実装を詳しく検討する本であり、C言語のコード例が数多く含まれると説明している。

第1章：Elementary Structures

スタック、キュー、両端キュー、ノードの動的割り当て、配列ベースの構造のシャドウコピー。本書でもっとも初歩的な話題で、以降で使う配列ベースとノードベースの実装の準備になる。

第2章：Search Trees

探索木の二つのモデル、一般的な性質と変換、探索木の高さ、基本的な検索・挿入・削除の操作。さらに葉から根への復帰、重複キー、区間のクエリ、最適探索木の構築、木のリストへの変換、木の削除を扱う。

第3章：Balanced Search Trees

単一の系統としてはもっとも長い章。高さ平衡木と重み平衡木、(a, b)木とB木、赤黒木とほぼ最適な高さの木、トップダウンの再平衡化、既知の位置で定数時間更新ができる木、フィンガー木とレベルリンク、部分再構築と償却解析、スプレー木、スキップリスト、平衡木の結合と分割。

第4章：Tree Structures for Sets of Intervals

区間木、セグメント木、区間の和集合・重み付き区間の和・区間制限付き最大和クエリのための木、さらに直交領域木、高次元セグメント木、その他の構成要素の体系、範囲カウントと半群モデル、kd木。

第5章：Heaps

ヒープとして使う平衡探索木と配列ベースのヒープから始め、ヒープ順序木と半順序木、左傾ヒープ、スキューヒープ、二項ヒープ、キーの変更、フィボナッチヒープ、最適な計算量のヒープ、両端ヒープと多次元ヒープ、定数時間更新のヒープ関連構造へと進む。

第6章：Union-Find and Related Structures

分割の類を併合するユニオン・ファインド、コピー付きユニオン・ファインドと動的セグメント木、リストの分割、根向き木の問題、線形順序の維持。

第7章：Data Structure Transformations

構造を動的にする、また永続的にするための一般的な手法。

第8章：Data Structures for Strings

トライと圧縮トライ、問い合わせに誤りを許す辞書、接尾辞木と接尾辞配列。

第9章：Hash Tables

基本的なハッシュ表と衝突解決、ユニバーサルハッシュ族、完全ハッシュ関数、ハッシュ木、拡張可能ハッシュ、メンバーシップテスターとブルームフィルタ。

第10章：Appendix

ポインタマシンと他の計算モデル、外部メモリモデルとキャッシュオブリビアスなアルゴリズム、データ構造の命名、線形漸化式の解法、非常にゆっくり増加する関数。

主要概念

第1～3章：基本構造と平衡構造

• シャドウコピーとノード割り当て：基本構造の実装手法。
• 平衡の基準：高さ平衡、重み平衡、(a, b)木、赤黒木は、木を浅く保つ異なる方法である。
• 償却解析、スプレー木、スキップリスト：明示的な平衡化に代わる適応的・確率的な手法。

第4～6章：区間、ヒープ、ユニオン・ファインド

• セグメント木、区間木、領域木：区間や多次元の点集合に対する問い合わせのための構造。
• ヒープの変種：左傾、スキュー、二項、フィボナッチヒープ。
• ユニオン・ファインド：分割の類を効率的に併合する。

第7～9章：変換、文字列、ハッシュ

• 動的化と永続化：更新能力を加える、あるいは古い版を保持する一般的な変換。
• トライ、接尾辞木、接尾辞配列：文字列集合のための構造。
• ユニバーサル・完全ハッシュ、ブルームフィルタ：保証付きまたは近似的な所属判定を行うハッシュ系の構造。

批判的分析

長所

• アルゴリズムの話題としてのデータ構造。 Cambridgeは、本書をこの主題を、オブジェクト指向プログラミングを例示するための些末な題材としてではなく、アルゴリズムの重要な話題として扱った最初の本と位置づけている。
• 標準的な講義を超える幅広さ。 区間・範囲構造、長いヒープの章、ユニオン・ファインドの変種、永続化と動的化、文字列構造、複数のハッシュ法が一冊にまとまり、500を超える文献が文献をたどる手がかりになる。
• コードと図。 Software Engineering Notesの書評者Igor Gveroは、本書を、コンピュータ科学のむずかしい主題を混乱させずによく説明しようとする、図とコードがぎっしり詰まった本と評している。出版社は、C言語のコード例が数多くあると述べている。
• 教科書としても参考書としても。 SIGACT Newsの書評は、大学院のデータ構造の講義の主教材または補助教材として適しており、実装者の座右の参考書にもなると評価した。

短所

• 入口が不均一。 第1章は入門的だが、第2章以降は、目次に償却解析、最適探索木、半群モデル、キャッシュオブリビアスなアルゴリズムといった、アルゴリズムの講義を前提とする用語が現れる。
• 命令型への偏り。 コード例はCで書かれており、不変データ向けの構造は目次にないため、関数型の実装には別の本が必要である。
• 穏やかな連なりというより参考書。 第3章と第5章はそれぞれ十数の変種を並べており、通読するより選んで読む必要がある場合がある。

コースにおける位置づけ

Brassは、このコースの中で大学院レベルの、幅広さを重視した本である。WengrowのA Common-Sense Guide to Data Structures and AlgorithmsとBhargavaのGrokking Algorithmsは、正式なコンピュータ科学の背景がないプログラマーにとってやさしい出発点になる。Goodrich、Tamassia、GoldwasserのData Structures and Algorithms in Javaは第二課程の教科書で、MorinのOpen Data Structuresは各構造を厳密なインターフェース、実装、実行時間の上界の証明とともに示す。どちらもBrassの前の準備として妥当である。

OkasakiのPurely Functional Data Structuresは、遅延評価をもつ関数型言語における永続的な構造という、別の分野を扱い、Brassの永続化の第7章とよく組み合わさる。

本書の使い方

スタック、キュー、木、ハッシュ、漸近解析をすでに学び、Cのコードを読める読者に向く。大学院の講義、実装者の独学、標準ライブラリの構造では足りないときの参考書として使える。

実践的な進め方は次のとおり。

• 中核： 第2章と第3章（探索木と主な平衡木の系統）、続いて第5章（ヒープ）と第9章（ハッシュ表）。
• 選択的な話題： 幾何やデータベースに関心があれば第4章、ユニオン・ファインドを使うグラフアルゴリズムには第6章、文字列処理には第8章。
• 技法： 第7章は、それが変換する構造を学んだ後に。
• 付録： 章をまたいで計算量の上界を比較する前に、ポインタマシンと他の計算モデルを扱う10.1節を読む。

本書の叙述は実装の細部を軸にしているので、各章で少なくとも一つの構造をCで実装するとよい。