01 / 経典教科書推薦
経典教科書推薦
対象読者
標準的なデータ構造の教科書を終え、既知の構造とその解析を幅広く知りたい大学院生や学部上級生。区間木や併合可能なヒープなどの特殊な構造を選択・実装する必要があり、そのトレードオフを丁寧に知りたい研究者やシステムプログラマにも役立つ。
前提知識
学部のデータ構造とアルゴリズムの授業、漸近解析への習熟、C言語または類似の言語の実用的な知識。
扱う内容
スタックやキューなどの基本構造、探索木とその操作、高さ平衡木・重み平衡木・赤黒木・B木・スプレー木を含む平衡探索木、区間木・セグメント木・範囲木などの区間集合のための木構造、左傾ヒープ・スキューヒープ・二項ヒープ・フィボナッチヒープ・ペアリングヒープを含むヒープ、Union-Find と関連構造、トライ・接尾辞木・接尾辞配列などの文字列用データ構造、ユニバーサルハッシュや完全ハッシュを含むハッシュ表を扱う。
使い方
トピックごとに選んで読み、各章から少なくとも一つの構造を実装して、示された計算量の上界と照らし合わせて検証する。自分のプロジェクトで重要な構造については、文献ノートをたどって原論文に当たるとよい。
版と出典
初版のみ。Cambridge University Press より2008年9月にハードカバーで刊行（ISBN 9780521880374）、のちに電子版とペーパーバック版も出ている。本レコードの書誌情報は Cambridge Core の製品ページに基づく。