教程名稱：算法導論
教程目錄：
1.課程簡介及算法分析
2.漸近符號、遞歸及解法
3.分治法（1）
4.快排及隨機化算法
5.線性時間排序
6.順序統(tǒng)計、中值
7.哈希表
8.全域哈希和完全哈希
9.二叉搜索樹
10.平衡搜索樹
樹的結構，如果不能保持平衡，那么其搜索性能會大大打折扣，而本節(jié)課介紹了幾種經(jīng)典的平衡樹，如AVL，2-3-4tree，紅黑樹等等，然后著重講了紅黑樹，接下來就紅黑樹的基本性質，作一些簡短的總結。
首先，紅黑樹除了具有BST的基本性質外，還額外擁有以下的五大基本性質：
1）每個結點有一個色域，一個結點要么為黑結點，要么為紅結點
2）根節(jié)點為黑結點
3）每個葉子結點都為黑結點（無鍵值）
4）每個紅結點的父親都為黑結點，即不可能出現(xiàn)兩個紅色結點相連的情況
5）從根節(jié)點到任意葉節(jié)點的路徑中的黑色結點數(shù)目相等，這個數(shù)目也稱為黑高度
由以上5點性質，可以保證紅黑樹的高度為O（lgn），證明如下：
將紅黑樹的所有紅結點，都與其父節(jié)點（由性質四得其父節(jié)點必定為黑）合并，可以得到一顆2-3-4 tree（即每個結點的子節(jié)點數(shù)目為2~4個），由數(shù)據(jù)結構知識可得，原紅黑樹的葉子結點個數(shù)為帶鍵值結點個數(shù)n+1，假設整棵樹高度為h，那么葉子結點數(shù)應為h^2~h^4,因此有h^2<=n+1<=h^4,即此時樹高度最高也只有l(wèi)og n+1，即樹的黑高度為log n+1,根據(jù)性質3，樹最高情況也不過是紅黑相間的時候，因此其高度最高只有2log n+1 ，即樹的高度為O（lgn）。
紅黑樹的查詢操作和普通BST一樣，而刪除和插入操作則相對復雜，因為我們要保證紅黑樹的5大性質，為什么需要保證這五大性質呢？因為這五大性質是紅黑樹為平衡樹的保證，能夠保證紅黑樹的高度為Olgn，這樣紅黑樹的基本操作（刪，插，查）都可以保證在Olgn的時間復雜度內(nèi)完成。
接下來簡單介紹一下插入操作是如何完成的,刪除操作思路類似:
插入操作的原理就是插入一個紅結點，然后通過向上重染色和旋轉的方式維持紅黑樹的性質
這里有三種情況
case1 xa0直線型 且祖父結點為黑，父節(jié)點和父親兄弟結點為紅 將祖父結點的黑傳遞到兩個紅子節(jié)點 xa0 每次向上傳 xa0 xa0 xa0遞2個結點，樹高度2lgn 所以操作為O（lgn）
case2 xa0zigzag Z型 父親兄弟結點為黑 旋轉為case3 xa0 O（1）的旋轉
case3 xa0zigzig直線型 旋轉
由以上三種情況可得，插入的時間復雜度為重染色的Olgn+不超過3次的O(1)的旋轉操作
這里值得一提的是，在實際的運用中，雖然向上重染色理論上花費的時間多于旋轉，但是當多個用戶并發(fā)查詢訪問紅黑樹的時候，重染色并不會影響查詢，因為用戶并不關心每個結點的顏色，但是旋轉需要鎖定該子樹及其結點，可能會影響并發(fā)查詢的操作。
最后，就AVL和紅黑樹做一下比較，就平衡程度而言，AVL是追求的絕對平衡，任意葉子結點的深度不會多于其他葉子結點深度+1，而紅黑樹只要求局部平衡，其紅黑性保證了其平衡性，因此在維護平衡方面，紅黑樹只需要不超過3次旋轉即可，這一點是AVL樹所做不到的，但查詢方面，由于AVL是絕對平衡，因此效率會略高于紅黑樹，實際應用中這一點并不明顯，就統(tǒng)計性能而言，紅黑樹會優(yōu)于AVL，而C++ STL中的set、multiset、map、multimap等，都是紅黑樹的一種變體。
值得一提的是，平衡樹都是動態(tài)的數(shù)據(jù)結構，其優(yōu)勢在于動態(tài)操作下，也能保持優(yōu)越的查詢效率，如果是靜態(tài)數(shù)據(jù)，那么使用hash表效率會更高一些。
11.擴充的數(shù)據(jù)結構、動態(tài)有序統(tǒng)計和區(qū)間樹
本節(jié)課主要講了如何構造自己想要的數(shù)據(jù)結構，或者擴充已有數(shù)據(jù)結構的功能，以實現(xiàn)想要的特定功能
比如設計一個動態(tài)結構，滿足功能尋找第k大的數(shù)
其做法是維護每個結點的子結點個數(shù)來推導其秩，而不維護其秩，因為動態(tài)操作會使得其難以維護
紅黑樹的插入操作 1.樹插入 2.rebalance
構造自己需要的擴充數(shù)據(jù)結構的基本流程
1.選擇一個基本的數(shù)據(jù)結構 例如紅黑樹
2.決定要添加到結點的基本信息 xa0例如實現(xiàn)查詢第k大數(shù)功能，應添加的基本信息為所有子樹結點之和，而非直接保存該結點鍵值的秩
3 維持 插入+旋轉/刪除+旋轉
4 封裝為函數(shù)，實現(xiàn)其功能
12.跳躍表
跳躍表是一種簡單又有趣的動態(tài)搜索數(shù)據(jù)結構，其主要優(yōu)點在于其易于實現(xiàn)，而且很好的保證了其具有高效的性能，即2*O（lgn）的搜索性能
在此之前我想首先談談鏈表，鏈表的優(yōu)點在于其插入和刪除只需要常數(shù)項的時間（加上查找該元素需要額外的O（n）時間），但是其查找效率只有O（n），這里順帶補充一下鏈表類的問題，以下先給出兩個BAT公司面試時熱衷于考的兩個鏈表經(jīng)典問題：
1.如何快速查找單向鏈表倒數(shù)第m個元素
2.如何快速判斷一個單向鏈表是否存在環(huán)
對于鏈表類問題，其核心思想不外乎兩點，1是開雙指針（甚至多指針），2是開雙鏈表（甚至多鏈表），其實以上兩個問題開雙指針便能巧妙地解決，第一個問題，先開一個指針走m步，然后再開一個指針同步走，當前一個指針走到鏈表末端時，后一個指針就正好指向倒數(shù)第m個元素了，第二個問題，開一個快指針和一個慢指針，快指針每次移動兩步，慢指針每次移動一步，如果存在環(huán)，那么快指針一定會追到慢指針，可以想象兩個人在操場賽跑，快的人跑了很久之后會超慢的人一圈。
接下來我們繼續(xù)談跳躍表，其實跳躍表用到的就是第二個思路，開雙鏈表甚至多個鏈表
首先考慮建立兩個鏈表L1和L2，L1為快表，即只保存部分元素，L2為慢表保存全部元素，注意，以下提到的鏈表均為排好序的鏈表
當我們要搜索某一元素時，我們先走快表，因為快表只保留了部分元素，所以是跳躍前進的，直到快表走過該元素，我們再退回快表前一個結點換到慢表繼續(xù)走，這樣效率顯然比在慢表上進行線性查找要好一些，這里的快慢表就像美國地鐵的快慢線地鐵一樣，快線的地鐵只在幾個站停頓，而慢線會在所有站停頓，乘客可以先乘快線到一個最接近目的地的前一個站，再轉乘慢線到達該地
那么問題來了？
如何建表L1和 L2呢？L2無疑是一條包含所有結點的單向鏈表，那么L1應該設置多少個結點最為合理呢，直觀上感受L1應該是均勻分布最好，那么是以怎樣的密度分布最合適呢？
我們不難得出查找時間上界為|L1|+|L2|/|L1|+換乘的常數(shù)，這里|L1|表示L1的長度（最壞情況就是L1走到末端后，走回一個節(jié)點然后進入L2，因為L2可以看做被L1分成了L1個段，所以每段長度為|L2|/|L1|，所以為|L1|+|L2|/|L1|+換乘的常數(shù)），因為L2長度為n（包括整個鏈表），換乘即鏈表L1向下走到L2的時間，為常數(shù)，所以我們的目標是要使得|L1|+n/|L1|最小，即|L1|為sqrt（n）時最優(yōu)（可以求導得出或者通過其他數(shù)學方法，證明略），此時時間消耗為2*sqrt（n），即每隔sqrt（n）設立一個快表的結點，共sqrt（n）個快表結點
什么？sqrt（n）還不過癮？
那么我們還能做怎樣的優(yōu)化呢？答案是加更多的鏈表，我們看看三條鏈表應是多少,直覺告訴我們是3*n的1/3次方
其實，可以證明k條鏈表的時候為k*n的1/k次方
因為n是常數(shù)，那么k多大比較合適呢？lgn！ 讓我們看看k取lgn的時候為多少，即lgn*n^(1/lgn)為多少，即求lgn*n^logn（2），還記得我們計算遞歸時間復雜度時的換底公式嗎？這里n^logn(2)即2^logn(n)即2^1，即2，所以整個時間復雜度為2*lgn，這是一個非常好的性能。
這種情況下的跳躍表稱為理想跳躍表，每一層數(shù)量減少一半，總共lgn層鏈表，從最上級鏈表開始搜，搜不到就向下，最多下logn層，每層最多搜2個元素，所以搜索復雜度為O（2lgn）
那么問題又來了，如何動態(tài)維護這樣一個跳躍表呢？
先看刪除功能,刪除功能只要從上級鏈表搜到之后，就可以直接刪除，并向下將所有鏈表的該結點都刪除，這個比較簡單，那么插入呢？
插入（x） 先search（x）在底表的位置然后插入該元素，是否結束了呢？不，因為在某一段連續(xù)插入若干個結點后，這一段會變得非常長，整個跳躍表的平衡結構無疑會被打破，那么如何維護理想線段表的結構呢？
1.保持每段之間的理想距離，如果距離過大，就從中間分割，然后將中點上升一層結點
這個方法從直觀上看非常巧妙，但是實行起來卻有一定難度，因為你必須實時記錄每一段的長度
2.采用我們最喜歡的隨機化算法，拋硬幣 如果正面，就把這個結點提升一個level（即把該結點也加入上一級的鏈表中），再拋硬幣（看是否持續(xù)提升level），因為兩個相鄰鏈表的長度之比為1:2，而硬幣出正面的概率也是50%，事實證明這樣做是可行的，這里值得一提的是，老師在這節(jié)課發(fā)了兩個硬幣給同學，一個利用拋硬幣產(chǎn)生隨機數(shù)，一個利用拋硬幣決定當前插入結點是否需要提升level，在課堂上直接做起了實驗，整個課程氛圍也很好，也讓同學們都對該算法有了直觀的理解，這一種教學方式很值得借鑒
注意，這里需要考慮一個特殊情況，就是當我們插入的元素為最小的元素時，如果它沒有提升一個level，那么上級鏈表的開頭就不是第一個元素，這樣也會打亂整個跳躍表的理想結構，因此我們需要打個補?。杭窗岩粋€負無窮值插到所有鏈表頭，這樣就算插入了一個最小的元素也能保證每個表是以負無窮開始，即每個鏈表都可以從最左邊開始。
在課堂上，通過實驗表明算法2似乎在平均情況下可以得到一個很好的跳躍表，其實不僅僅是平均情況可以得到一個好的跳躍表，在絕大多數(shù)情況都可以得到一個好的跳躍表.
可以證明，得到一個好的跳躍表的概率P>=1-O(1/n^a) xa0這里a是一個介于0到1的參數(shù)，與n有關，在課堂的最后，老師花了盡20分鐘的時間來證明，具體證明方式我們這里略過（其實是我根本沒看懂其證明過程 逃~~）
13.平攤分析，表的擴增，勢能方法
先通過表的擴增這一例子來引入今天的主題——平攤分析和勢能分析
一個哈希表的大小應該為多少比較合適？
theta（n）比較合適
可是萬一我們不知道n是多大呢
使用動態(tài)表解決 xa0溢出就建立一個大小翻倍的空間，然后復制過去
這樣做插入的最壞時間復雜度為n
讓我們看看平均的時間復雜度，每次基本插入操作為1，空間溢出時需要開一個更大一倍的空間，并復制當前的元素過去，所以空間溢出時所需要的時間為2的i次方（i為第幾次溢出）
所以其真實的時間消耗為n+sigma(2^i) xa0 0<=i<=lg(n+1) xa0即3n
因此其實插入的時間復雜度為O（1）
盡管有時會有巨大開銷，但是會被平均的開銷平攤掉，這就是平攤分析
平攤分析：平均操作復雜度不高，盡管有些操作會有較高的復雜度
三種類型的平攤方法：
1.聚集分析
2.記賬方法（accounting）
3.勢能分析
2.3它們?yōu)槊恳粋€操作分配了特點的平攤代價
記賬方法：
想象自己擔任了一個會記
對第i個操作收費為ci
收益?zhèn)€虛構的平攤代價
每一步運算需要花費1$
未用到的余款就被存到銀行，用于償付以后的操作
如每次插入收費為3，插入消耗1，剩下的2存入銀行為表翻倍時做準備，要始終保證銀行的金額為正
即提前平攤，總能支付擴充表的費用，這樣某一個高開銷的操作會被平攤掉
勢能方法：
算法分析里最漂亮的產(chǎn)物之一
剛開始數(shù)據(jù)結構狀態(tài)為D0
操作i的代價為ci
操作i可以看作把數(shù)據(jù)結構由Di-1轉化為Di
定義勢能函數(shù)
將數(shù)據(jù)結構的集合定位實數(shù)值
D0 = 0 初始的勢為0
所有Di >=0，我們不能讓勢低于0
定義平攤代價為Ai，對勢能Di有Ai=Ci+Di-Di-1
Di-Di-1 部分是勢能的改變量，如果其>=0 那么Ai>ci 我收取的費用超過了實際的花費，即操作i儲存了后面數(shù)據(jù)結構所需的功
如果勢能的改變量<0，即我們用存儲的勢能轉化為能量來幫助完成操作i
記賬方法考慮的是平攤代價
而勢能分析考慮的是銀行存款（存儲勢能）
有sigmaAi=sigma（ci+Di-Di-1）=sigma（ci+Dn-D0）
D0為0，Dn大于等于0，所以左邊大于右邊，是實際代價的一個上界
我們再次以表的擴增為例感受一下勢能分析
我們的勢能函數(shù)為2i-2^ceil（lgi） xa0
如何推導出這樣的勢能函數(shù)的？
定義勢能函數(shù)難度低于定義平攤代價
第i個操作的平攤代價Ai=Ci+Di-Di-1= xa0i+2i-2^ceil（lgi）-（2i-2-2^ceil（lgi-1））（剛好i是2的冪）
case1 i-1是2的冪，那么Ai=i+2-2（i-1）+（i-1）=3
case2 i-1不是2的冪 那么Ai=1+2i-2^ceil（lgi）-（2i-2-2^ceil（lgi-1））=3
這樣得到的平攤代價也為3
不關注實時性能只關注聚集性能
14.競爭性分析，自組織表
15.動態(tài)規(guī)劃，最長公共子序列
16.貪婪算法，最小生成樹
17.最短路徑算法：Dijkstra算法，廣度優(yōu)先搜索
18.最短路徑算法：Bellman和差分約束系統(tǒng)
19.最短路徑算法：點的最短路徑
20.高級課題 并行算法（一）
21.高級課題 并行算法（二）xa0
22.高級課題 緩存參數(shù)無關算法
