01 / 導讀
導讀
引用
Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
章節概要
全書474頁，包含九章正文、一章附錄、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實作一種結構。
