Open Data Structures: An Introduction（開放資料結構導論）

引用

Morin, P. (2013). Open Data Structures: An Introduction. AU Press. Free official edition: https://opendatastructures.org/

章節概要

第1章：引言

開篇一章先解釋效率為何重要：通過粗略估算說明，在一百萬個未排序元素中進行一百萬次查詢會耗費過長時間；隨後定義貫穿全書的介面：Queue、Stack 與 Deque、List、USet（無序集合）和 SSet（有序集合）。本章複習所需的數學知識（對數、階乘、漸近記號，以及涉及期望和指示變數的隨機化），確定 w 位字 RAM 計算模型，並用"分期還房貸與一次性買房""購買火災保險"的類比區分最壞情況、均攤和期望執行時間。它還說明書中的 Java 程式碼經過簡化（沒有 public、private 等關鍵字），並給出全書所有資料結構的彙總表。

第2章：基於陣列的列表

本章在底層陣列之上實現 List 和 Queue。先講 ArrayStack 及其擴容與縮容的均攤分析，再給出使用批次陣列複製的最佳化版本、迴圈的 ArrayQueue、兩端都能快速操作的 ArrayDeque，以及由兩個堆疊構成、在一側不足時重新平衡的 DualArrayDeque。最後介紹 RootishArrayStack：它把元素存放在大小遞增的塊中，只浪費約 √n 的空間，並討論瞭如何計算平方根。

第3章：連結串列

連結串列以放棄常數時間依索引存取為代價，換來在已知結點旁常數時間的插入和刪除。本章實現單鏈結串列（用於堆疊和佇列操作）、帶啞結點的雙鏈結串列，以及 SEList——一種在每個結點中存放小塊元素的節省空間的列表，並對塊的分散與聚集進行均攤分析。

第4章：跳錶

跳錶利用隨機拋硬幣構建多層連結串列。本章實現每次操作期望時間為 O(log n) 的 SSet，以及支援依索引存取的 SkiplistList，然後分析期望的查詢路徑長度和空間。

第5章：雜湊表

第一部分實現採用乘法雜湊的拉鏈法雜湊表，以及線性探測雜湊表，分析線性探測並介紹表格雜湊。第二部分說明如何為基本型別、複合物件、陣列和字串構造雜湊碼。作者提到，程式碼中的"隨機"常數是用大氣噪聲生成的。

第6章：二叉樹

在定義二叉樹術語之後，本章編寫遞迴和非遞迴的遍歷方法，以及一個不平衡的 BinarySearchTree，包括查詢、插入和刪除。章末討論預告了後續幾章獲得 O(log n) 效能的三種途徑：隨機化、均攤和最壞情況下的平衡。

第7章：隨機二叉搜尋樹

本章先證明由隨機排列構建的二叉搜尋樹期望查詢路徑長度為對數級，再利用這一結論設計 Treap（樹堆），通過賦予隨機優先順序使樹在插入和刪除後仍保持隨機形態。

第8章：替罪羊樹

替罪羊樹通過偶爾把整棵子樹重建為完全平衡的子樹來保持平衡。本章實現重建操作，並證明更新操作的均攤代價為 O(log n)，而查詢由於高度受限，在最壞情況下也是 O(log n)。

第9章：紅黑樹

這是技術性最強的一章。它先介紹 2-4 樹，再把紅黑樹實現為對 2-4 樹的模擬（採用左傾變體），並逐一分析插入和刪除的各種情況。本章解釋了紅黑樹為何被 Java 集合框架等庫採用：高度為對數級、最壞情況下 O(log n) 的更新，以及均攤常數次的旋轉。

第10章：堆

本章開發兩種優先佇列：BinaryHeap，用 Eytzinger 佈局把完全二叉樹存放在陣列中；以及 MeldableHeap，一種隨機化的堆，其合併操作還支援把兩個堆融合在一起。

第11章：排序演算法

本章介紹歸併排序、快速排序和堆排序，證明基於比較的排序的下界，然後介紹適用於整數的計數排序和基數排序，並把快速排序與隨機搜尋樹、堆排序與 BinaryHeap 聯絡起來。

第12章：圖

用鄰接矩陣和鄰接表兩種方式表示圖並比較其代價，隨後介紹廣度優先搜尋和深度優先搜尋，包括非遞迴的深度優先搜尋。

第13章：整數資料結構

本章回到 w 位整數鍵的 SSet 問題，依次構建 BinaryTrie（操作時間 O(w)）、藉助雜湊在 O(log w) 時間內查詢的 XFastTrie，以及把 XFastTrie 中的樣本與普通 SSet 結合、使所有操作期望時間為 O(log w) 的 YFastTrie。

第14章：外存查詢

最後一章放棄"所有資料都能裝入記憶體"的假設。它以實測的記憶體、固態硬碟和機械硬碟存取時間來說明外存模型的動機，引入塊儲存，並實現 B 樹的查詢、插入、刪除，以及對分裂與合併的均攤分析。

核心概念

第1章：引言

• 介面與實現：介面（List、USet、SSet）規定有哪些操作；資料結構是實現這些操作的一種方式。
• 均攤時間與期望時間：均攤界對一系列操作的代價取平均，期望界則對資料結構自身的隨機選擇取平均。
• 字 RAM 模型：對 w 位字的基本操作耗時為常數、且 w 至少為 log n 的計算模型。

第2–3章：基於陣列的列表與連結串列

• 可變大小的底層陣列：陣列容量加倍和減半，使末端新增和刪除的均攤代價保持為常數。
• 迴圈陣列：下標對陣列長度取模，使佇列或雙端佇列可以在任一端增長。
• 節省空間的結構：RootishArrayStack 和 SEList 把浪費的空間降到約 √n 或 n 的一小部分。

第4章：跳錶

• 隨機層級：每個元素以二分之一的機率被提升到上一層連結串列，從而使期望查詢路徑為對數長度。

第5章：雜湊表

• 拉鏈法：陣列的每個槽位存放一個列表，其中是雜湊到該位置的元素。
• 線性探測：元素直接存放在陣列中，衝突時向後掃描到下一個空槽位。
• 雜湊碼：把任意物件轉換為整數的函式，其組合方式保證相等的物件得到相等的雜湊碼。

第6–9章：二叉搜尋樹

• 二叉搜尋樹性質：每個結點的值大於其左子樹中的值、小於其右子樹中的值。
• Treap：同時也是關於隨機優先順序的堆的搜尋樹，從而保持隨機的形態。
• 部分重建：把不平衡的子樹從頭重建，這是替罪羊樹背後的思想。
• 作為 2-4 樹的紅黑樹：給結點著色，使二叉樹編碼一棵 2-4 樹，從而保證高度至多為 2 log n。

第10–11章：堆與排序

• 隱式二叉樹：把完全二叉樹存放在陣列中，父結點與子結點的位置可通過算術計算得到。
• 比較下界：任何基於比較的排序在最壞和平均情況下都需要大約 n log n 次比較。

第12–14章：圖、整數與外存

• 鄰接表：為每個頂點儲存其出鄰居列表的圖表示方式。
• 二進位制鍵上的字典樹：從根到葉的路徑拼出整數鍵各個二進位制位的樹。
• B 樹：結點大小與磁碟塊相匹配的平衡搜尋樹，使讀取塊的次數最少。

評析

優點

• 介面、實現與證明並重。 每種資料結構都對照一小組介面之一引入，給出完整實現，並以明確的定理加以分析；大多數小節以一段簡短的執行時間總結結束。1.7 節的彙總表讓讀者可以一眼比較全部結構。
• 覆蓋面超出一般的入門課程。 除了列表、雜湊表、搜尋樹和堆之外，本書還講解跳錶、Treap、替罪羊樹、可合併堆、X-fast 與 Y-fast 字典樹以及 B 樹，從而展示了達到同樣界限的幾種途徑（隨機化、均攤、最壞情況平衡）。
• 對三種性能保證的細緻處理。 最壞情況、均攤和期望時間的區別在第1章通過具體類比建立起來，並貫穿全書，幫助學生理解諸如紅黑樹儘管複雜卻仍被各種庫採用的原因。
• 開放且可改編。 前言說明本書像開源專案一樣運作：LaTeX 和 Java 原始檔以知識共享署名許可釋出在 GitHub 上，並提供 Java、C++ 和虛擬碼三個版本。每章的討論部分都提供歷史背景和參考文獻。

局限

• 對入門課程而言數學要求較高。 證明從較早階段（第4章起）就用到機率、指示變數和均攤論證，第9章紅黑樹刪除的討論篇幅很長。沒有學過離散數學的學生可能會感到吃力。
• 程式碼經過簡化而非地道寫法。 Java 範例有意省略存取修飾符和類層次結構；讀者需要檢視配套原始碼才能獲得完整實現，而且本書不講如何使用庫中的集合類。
• 圖和演算法部分較為簡略。 第12章只講表示方式以及廣度優先和深度優先搜尋；最短路徑、最小生成樹等圖演算法都未涉及，AVL 樹等平衡樹也只在討論部分提到。
• 版本細節有些過時。 所讀版本（0.1G）出自 2010 年代初，有些例子（如 32 位 JVM 的字長和磁碟存取時間）反映的是那個時期的情況。書中沒有提供練習答案。

在課程中的定位

在本課程的資料結構書目中，Morin 的書介於淺顯易懂的圖解類書籍（Bhargava 的 Grokking Algorithms 和 Wengrow 的 A Common-Sense Guide to Data Structures and Algorithms）與專門教材（Okasaki 的 Purely Functional Data Structures 和 Brass 的 Advanced Data Structures）之間。不熟悉形式化分析的學生可以先讀一本入門書——這類書通常被認為以很少的數學建立直覺——然後再轉向 Morin，學習證明和完整實現。

Goodrich、Tamassia 和 Goldwasser 的 Data Structures and Algorithms in Java 與本書內容相近；它通常被認為是覆蓋面更廣的傳統教材，在 Java 程式設計和演算法方面內容更多。因此可以把它作為主教材、以 Morin 作為免費且更偏分析的輔助讀物，反之亦可。讀完 Morin 之後，對更進階的搜尋結構感興趣的學生可以繼續讀 Brass，想了解同樣的思想在純函式式環境中如何呈現的學生可以讀 Okasaki。

如何使用本書

本書適合已修完一門程式設計課程並學過一些離散數學的計算機專業二年級學生；第1章複習了後文用到的機率和漸近記號。熟悉 Java 會有幫助但並非必需，因為程式碼採用簡化風格，懂任何類 C 語言的人都能讀懂。

一學期的課程可以以下列內容為核心：第1章、第2章（至少 ArrayStack、ArrayDeque 和 DualArrayDeque）、第3章（單鏈結串列和雙鏈結串列）、第5章、第6章、作為平衡方法的第7章或第8章、第10章和第11章。第4章的跳錶是學習隨機化分析的良好起點。第9章可以只讀到與 2-4 樹的對應關係，完整的刪除情況作為選讀。第12–14章適合較長的課程或自學。

每章末都有練習（全書共 150 多道），請做其中一部分；許多練習要求實現或修改某種結構，而可下載的原始碼便於把自己的版本與書中的實現對照測試。各章的討論部分介紹了每種思想的歷史，並給出延伸閱讀的線索。

版本與來源

本導讀依據 Open Data Structures (in Java) 第 0.1G 版，閱讀的是作者官方網站 https://opendatastructures.org/ 提供的免費 PDF（ods-java.pdf）；印刷版由 AU Press 於 2013 年出版。內容取材於致謝、前言"Why This Book?"、完整目錄、第1章全文（1.1–1.8 節），以及第2–14章的章節引言、每個小節標題、小結與執行時間表，和各章的"Discussion and Exercises"部分。