演算法導論擬陣

1. 關於演算法導論

概念：

紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick 於1978年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，並且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。

紅黑樹是一種很有意思的平衡檢索樹。它的統計性能要好於平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。

背景和術語：
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當啟始位置的功能，它不是任何節點的兒子；我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。

如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。

由於紅黑樹也是二叉查找樹，它們當中每一個節點都的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途和好處：
紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用(real time application)中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。

紅黑樹在函數式編程中也特別有用，在這里它們是最常用的持久數據結構之一，它們用來構造關聯數組和集合，在突變之後它們能保持為以前的版本。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

紅黑樹是 2-3-4樹的一種等同。換句話說，對於每個 2-3-4 樹，都存在至少一個數據元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得 2-3-4 樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因，盡管 2-3-4 樹在實踐中不經常使用。
屬性：
紅黑樹是每個節點都有顏色特性的二叉查找樹，顏色的值是紅色或黑色之一。除了二叉查找樹帶有的一般要求，我們對任何有效的紅黑樹加以如下增補要求:

1.節點是紅色或黑色。

2.根是黑色。

3.每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

4.從每個葉子到根的所有路徑都包含相同數目的黑色節點。

這些約束強制了紅黑樹的關鍵屬性: 從根到葉子的最長的可能路徑不大於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值都要求與樹的高度成比例的最壞情況時間，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。

在很多樹數據結構的表示中，一個節點有可能只有一個兒子，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性並使演算法復雜。為此，本文中我們使用 "null 葉子" 或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個兒子，盡管其中的一個或兩個可能是空葉子。

操作：
在紅黑樹上只讀操作不需要對用於二叉查找樹的操作做出修改，因為它也二叉查找樹。但是，在插入和刪除之後，紅黑屬性可能變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非常快速的)並且不超過三次樹旋轉(對於插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導致了非常復雜的操作。

2. 《演算法導論》（第三版）目錄

1.1 演算法

1.2 作為一種技術的演算法

2.1 插入排序

2.2 分析演算法

2.3 設計演算法

2.3.1 分治法

2.3.2 分析分治演算法

3.1 漸近記號

3.2 標准記號與常用函數

4.1 最大子數組問題

4.2 矩陣乘法的 Strassen 演算法

4.3 用代入法求解遞歸式

4.4 用遞歸樹方法求解遞歸式

4.5 用主方法求解遞歸式

*4.6 證明主定理

4.6.1 對 b 的冪證明主定理

4.6.2 向下取整和向上取整

5.1 僱傭問題

5.2 指示器隨機變數

5.3 隨機演算法

*5.4 概率分析和指示器隨機變數的進一步使用

5.4.1 生日悖論

5.4.2 球與箱子

5.4.3 特徵序列

5.4.4 在線僱傭問題

6.1 堆

6.2 維護堆的性質

6.3 建堆

6.4 堆排序演算法

6.5 優先隊列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的隨機化版本

7.4 快速排序分析

7.4.1 最壞情況分析

7.4.2 期望運行時間

8.1 排序演算法的下界

8.2 計數排序

8.3 基數排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望為線性時間的選擇演算法

9.3 最壞情況為線性時間的選擇演算法

10.1 棧和隊列

10.2 鏈表

10.3 指針和對象的實現

10.4 有根樹的表示

11.1 直接定址表

11.2 散列表

11.3 散列函數

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 開放定址法

11.5 完全散列

12.1 什麼是二叉樹

12.2 查詢二叉搜索樹

12.3 插入和刪除

12.4 隨機構建二叉搜索樹

13.1 紅黑樹的性質

13.2 旋轉

13.3 插入

13.4 刪除

14.1 動態順序統計

14.2 如何擴張數據結構

14.3 區間樹

15.1 鋼條切割

15.2 矩陣鏈乘法

15.3 動態規劃原理

15.4 最長公共子序列

15.5 最優二叉搜索樹

16.1 活動選擇問題

16.2 貪心演算法原理

16.3 赫夫曼編碼

*16.4 擬陣和貪心演算法

*16.5 用擬陣求解任務調度問題

17.1 聚合分析

17.2 核演算法

17.3 勢能法

17.4 動態表

17.4.1 表擴張

17.4.2 表擴張和收縮

18.1 B 樹的定義

18.2 B 樹上的基本操作

18.3 從 B 樹上刪除關鍵字

19.1 斐波那契結構

19.2 可合並堆操作

19.3 關鍵字減值和刪除一個結點

19.4 最大度數的界

20.1 基本方法

20.2 遞歸結構

20.2.1 原型 van Emde Boas 結構

20.2.2 原型 van Emde Boas 結構上的操作

20.3 van Emde Boas 樹及其操作

20.3.1 van Emde Boas 樹

20.3.2 van Emde Boas 樹的操作

21.1 不相交集合的操作

21.2 不相交集合的鏈表表示

21.3 不相交集合森林

*21.4 帶路徑壓縮的按秩合並的分析

22.1 圖的表示

22.2 廣度優先搜索

22.3 深度優先搜索

22.4 拓撲排序

22.5 強連通分量

23.1 最小生成樹的形成

23.2 Kruskal 演算法和 Prim 演算法

24.1 Bellman-Ford 演算法

24.2 有向無環圖中的單源最短路徑問題

24.3 Dijkstra 演算法

24.4 差分約束和最短路徑

24.5 最短路徑性質的證明

25.1 最短路徑和矩陣乘法

25.2 Floyd-Warshall 演算法

25.3 用於稀疏圖的 Johnson 演算法

26.1 流網路

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重貼標簽演算法

*26.5 前置重貼標簽演算法

27.1 動態多線程基礎

27.2 多線程矩陣乘法

27.3 多線程歸並排序

28.1 求解線性方程組

28.2 矩陣求逆

28.3 對稱正定矩陣和最小二乘逼近

29.1 標准型和鬆弛型

29.2 將問題表達為線性規劃

29.3 單純形演算法

29.4 對偶性

29.5 初始基本可行解

30.1 多項式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 實現

31.1 基礎數論概念

31.2 最大公約數

31.3 模運算

31.4 求解模線性方程

31.5 中國余數定理

31.6 元素的冪

31.7 RSA 公鑰加密系統

*31.8 素數的測試

*31.9 整數的因子分解

32.1 樸素字元串匹配演算法

32.2 Rabin-Karp 演算法

32.3 利用有限自動機進行字元串匹配

32.4 Knuth-Morris-Pratt 演算法

33.1 線段的性質

33.2 確定任意一對線段是否相交

33.3 尋找凸包

33.4 尋找最近點對

34.1 多項式時間

34.2 多項式時間的驗證

34.3 NP 完全性與可歸約性

34.4 NP 完全性的證明

34.5 NP 完全問題

34.5.1 團問題

34.5.2 頂點覆蓋問題

34.5.3 哈密頓迴路問題

34.5.4 旅行商問題

34.5.5 子集和問題

35.1 頂點覆蓋問題

35.2 旅行商問題

35.2.1 滿足三角不等式的旅行商問題

35.2.2 一般旅行商問題

35.3 集合覆蓋問題

35.4 隨機化和線性規劃

35.5 子集和問題

A.1 求和公式及其性質

A.2 確定求和時間的界

B.1 集合

B.2 關系

B.3 函數

B.4 圖

B.5 樹

B.5.1 自由樹

B.5.2 有根樹和有序樹

B.5.3 二叉樹和位置樹

C.1 計數

C.2 概率

C.3 離散隨機變數

C.4 幾何分布與二項分布

C.5 二項分布的尾部

D.1 矩陣與矩陣運算

D.2 矩陣的基本性質