みんなのデータ構造
ラムダノート
著者：Pat Morin
訳者：堀江慧、陣内佑、田中康隆
訳者まえがき
本書の読み方
訳者謝辞
なぜこの本を書いたのか
謝辞
C++版のまえがき
第1章 イントロダクション
1.1 効率の必要性
1.2 インターフェース
1.3 数学的背景
1.4 計算モデル
1.5 正しさ、時間計算量、空間計算量
1.6 コードサンプル
1.7 データ構造の一覧
1.8 ディスカッションと練習問題
第2章 配列を使ったリスト
2.1 ArrayStack：配列を使った高速なスタック操作
2.2 FastArrayStack：最適化されたArrayStack
2.3 ArrayQueue：配列を使ったキュー
2.4 ArrayDeque：配列を使った高速な双方向キュー
2.5 DualArrayDeque：2つのスタックから作った双方向キュー
2.6 RootishArrayStack：メモリ効率に優れた配列スタック
2.7 ディスカッションと練習問題
第3章 連結リスト
3.1 SLList：単方向連結リスト
3.2 DLList: 双方向連結リスト
3.3 SEList：空間効率の良い連結リスト
3.4 ディスカッションと練習問題
第4章 スキップリスト
4.1 基本的な構造
4.2 SkiplistSSet：効率的なSSet
4.3 SkiplistList：効率的なランダムアクセスList
4.4 スキップリストの解析
4.5 ディスカッションと練習問題
第5章 ハッシュテーブル
5.1 ChainedHashTable: チェイン法を使ったハッシュテーブル
5.2 LinearHashTable：線形探索法
5.3 ハッシュ値
5.4 ディスカッションと練習問題
第6章 二分木
6.1 BinaryTree：基本的な二分木
6.2 BinarySearchTree：バランスされていない二分探索木
6.3 ディスカッションと練習問題
第7章 ランダム二分探索木
7.1 ランダム二分探索木
7.2 Treap: 動的ランダム二分探索木の一種
7.3 ディスカッションと練習問題
第8章 スケープゴート木
8.1 ScapegoatTree：部分的に再構築する二分探索木
8.2 ディスカッションと練習問題
第9章 赤黒木
9.1 2-4 木
9.2 RedBlackTree：2-4 木をシミュレートする二分木
9.3 要約
9.4 ディスカッションと練習問題
第10章 ヒープ
10.1 BinaryHeap：二分木を間接的に表現する
10.2 MeldableHeap：つなぎ合わせられるランダムなヒープ
10.3 ディスカッションと練習問題
第11章 整列アルゴリズム
11.1 比較に基づく整列
11.2 計数ソートと基数ソート
11.3 ディスカッションと練習問題
第12章 グラフ
12.1 AdjacencyMatrix：行列によるグラフの表現
12.2 AdjacencyLists：リストの集まりとしてのグラフ
12.3 グラフの走査
12.4 ディスカッションと練習問題
第13章 整数を扱うデータ構造
13.1 BinaryTrie：二分トライ木
13.2 XFastTrie：Ologlogn
時間での検索
13.3 YFastTrie：Ologlogn
時間のSSet
13.4 ディスカッションと練習問題
第14章 外部メモリの探索
14.1 BlockStore
14.2 B木
14.3 ディスカッションと練習問題
参考文献
索引