數據結構—思路
最近讀了清華大學鄧俊輝老師的數據結構，深感這些數據結構的精妙，在此做簡要總結，重點在於理清思路，不細寫演算法細節，感興趣的可直接查閱書籍。（鄧老師的這本書寫的真好，邏輯清晰，深入淺出，學堂在線還有公開課，強烈推薦。）
一：線性數據結構
1.最簡單的數據結構，就是數組了，理科生應該都懂。各元素依次存放於一段連續地址空間內，數據查找、修改僅需O(1)時間，但是對於數據插入、刪除，則需移動其後所有元素，需O(n)時間。
根據數據抽象性原則，我們可以將數組結構進行推廣，即得到向量。向量是由具有線性次序的元素構成的集合（並不限定各元素屬於同一基本類型），元素循秩訪問。我們定義其常用操作介面，無論採用何種實現方式，均可以方便地相互調用或集成，很好的體現了程序的封裝性。
2.對於需要經常插入、刪除的數據，如果採用向量存儲，明顯效率很低。究其原因，在於「各元素物理地址連續」的約定，也即「靜態存儲」策略。那麼相應的，列表結構儘管要求各元素在邏輯上具有線性次序，但對其物理地址並未做任何限制，也即「動態存儲」策略。列表通過指針或引用等機制，確定各元素實際物理地址。而鏈表，就是一種典型的動態存儲結構。此時，數據的插入、刪除僅需局部操作，變為了O(1)複雜度，但同時，訪問元素則必須沿著鏈表指針，從某端出發逐個掃描，變成了O(n)複雜度。可以看到，向量和列表，對於靜態和動態操作，各有優劣，無法兼顧。
3.在向量和列表基礎上，我們可以實現更為常用的兩種數據結構：棧與隊列。棧，先進後出，定義很簡單，用處極為廣泛。函數運行棧、瀏覽器瀏覽歷史記錄、四則計算等，均可通過棧簡單高效實現。隊列，先進先出，在需要資源管理、分配的場合，銀行排隊系統、計算機進程調度、印表機共享，均可以使用隊列。
二：樹
4.我們已經看到，向量和列表，對於靜態和動態操作，各有優劣，那麼，我們能不能綜合其優點呢？事實上，這就引出了樹。樹元素間並不存在天然的次序關係，但只要施加某種約束（如前序遍歷），也可以確定其次序，因此屬於半線性結構。樹是一種分層結構，而層次化這一特徵幾乎蘊含於所有事物及其聯繫之中，如進化樹、公司結構、域名系統等等，樹結構在演算法理論即實際應用中也扮演著最為關鍵的角色。
5.作為樹的特例，二叉樹並不失一般性。事實上，任何有根有序多叉樹，均可等價轉為二叉樹。對二叉樹的基本操作，有前序、中序、後續以及層次遍歷，可以確定其元素的線性次序。
6.如果二叉樹中序遍歷單調非降，則此樹為二叉搜索樹。分析得知，對二叉搜索樹的查找、插入、刪除操作，複雜度均正比於樹的高度。隨機意義下，二叉樹平均高度為O(logn)，因此效率較高，相較於向量和列表，其靜態與動態操作效率得到了平衡。但是，最壞情況下，每個節點均只有一個孩子，此時樹退化為了列表，查找效率降至O(n)。
7.既然二叉搜索樹性能取決於其高度，那我們自然想到儘可能降低其高度，使兄弟子樹的高度彼此接近。由於包含n個節點的二叉樹，高度不可能小於[log2n]，若恰好高為[log2n]，則稱為理想平衡樹，如完全二叉樹、滿二叉樹均屬此類。然而，葉節點只能出現於最底兩層的限制過於苛刻，此類二叉樹所佔比例極低，從演算法可行性角度來看，應當依照某種相對寬鬆的標準，重新定義。
8.定義任一節點的平衡因子為其左右子樹的高度差，則AVL樹定義為：各節點平衡因子的絕對值均不超過1。AVL樹可實現近乎理想的平衡，其高度在O(logn)內，因此查找、插入、刪除均可在O(logn)時間內完成。但是，在插入、刪除操作之後，節點高度可能發生變化，二叉樹失衡，也就需要重平衡操作，有單旋、雙旋、以及3+4重構幾種方案，可以在Ω(logn)次之內完成更新。但AVL樹幾乎每次插入刪除都要重新平衡，其代價仍然相對較高，實際應用並不廣泛，主要見於教學中。當然，如果場景中插入刪除不頻繁，只是對查找特別有要求，AVL樹還是具有優勢。
9.既然AVL樹對平衡要求仍然較高，會造成動態操作時失衡一直傳遞至根節點，那麼進一步放寬條件，即得到紅黑樹。紅黑樹定義為：樹根及外部節點為黑色；若某節點為紅色，則其孩子必為黑色；任一外部節點到根節點沿途黑節點數目相等，從而巧妙保證了任一節點左、右子樹的高度相差不超過兩倍。紅黑樹插入、刪除之後也可能失衡，需要進行修正，但由於其限制更寬鬆，其分攤意義上僅涉及O(1)個節點。一般工業界把紅黑樹作為一種更通用的平衡搜索樹來用，Java用它來實現TreeMap，C++的std::set/map/multimap等等，著名的linux進程調度Completely Fair Scheduler也用紅黑樹管理進程式控制制塊。
10.評估演算法性能時我們通常假設各元素被訪問概率相等，然而實際上存在極強的「數據局部性」，即剛剛被訪問的元素，極有可能在不久之後再次被訪問；將被訪問的下一元素，極有可能處於不久前被訪問過的某個元素的附近。基於這一原理，通過「即用即前移」的啟發式策略，我們得到了伸展樹。伸展樹在每次訪問某節點後，會通過旋轉使該節點成為樹根，以加速後續該節點的訪問速度。伸展樹單次操作可在分攤O(logn)時間內完成，且不需維護節點高度等額外信息，空間性能更優，實現複雜度低。例如在網路應用中，熱點內容會被大量重複訪問，伸展樹可讓此類重複搜索以很高的效率完成。
11.到目前為止，我們有了適用於不同需求的多種數據結構，很好。但以上分析全部基於數據全部存在於內存中的假設，而從實際應用需求看，問題規模的膨脹遠遠快於存儲能力的增長，通常我們需要將數據全集存放於外存中，計算過程中將內存作為高速緩存，藉助調度演算法，將內存的高速度與外存的大容量結合起來。
連個相鄰存儲級別間的數據傳輸，統稱I/O操作。而各級存儲器訪問速度相差懸殊，應該儘可能減少I/O操作。因此，為減少對外存的一次訪問，我們寧願訪問內存百次、千次甚至萬次。為此，我們可以利用磁碟之類外部存儲器的另一特性：就時間成本而言，讀取物理連續的一千位元組，與讀取單個位元組幾乎沒有區別。因此，我們想到，不妨每次從磁碟上讀取多個節點，然後在內存中多次比較，從而減少成本極高的單次外存操作。因此可將通常的二叉搜索樹，改造成多路搜索樹。
例如，將二叉搜索樹以兩層為間隔，各節點進行合併，改造後每個大節點擁有四個分支，故稱為四路搜索樹。不難想像，多路搜索樹同樣支持查找等操作，然而重要的是，搜索每下降一層，以大節點為單位從外存讀取一組（不再是一個）關鍵碼，而這組關鍵碼物理上彼此相鄰，所需時間與讀取單個關鍵碼幾乎一樣。當然，每組關鍵碼的最佳數目，取決於外存的訪問特性，比如根據旋轉式磁碟扇區的容量和關鍵碼的大小，換算得到每組的最佳規模。而資料庫中常見的m階B-樹(讀B樹，-是連字元，不是減號)，即m路平衡搜索樹（m≥2），為保證磁碟利用率，其要求每個節點分支節點介於[m/2]與m之間。(事實上，適當轉換後，紅黑樹與B-樹相互等價)
B-樹在插入或刪除節點後，節點關鍵碼樹可能不再符合（[m/2],m）約定，稱為上溢或者下溢，相應進行分裂或者合併操作，修復過程可在O(logmN)次內完成。B樹充分利用了磁碟塊的原理，樹高降低，磁碟IO次數減少，因此查找效率大幅提高。
12.B+樹是B-樹的升級版，其更充分的利用了節點的空間，查詢速度更穩定。其改變主要為：非葉子節點不再保存關鍵字記錄指針，只進行數據索引，因此內部節點佔用空間更小，同樣空間可保存更多節點，同時每個數據必須要搜索到葉節點，所有查詢次數一樣。另外，所有數據都在葉子結點，而葉子結點存儲了指向下個葉子結點的指針，因此可以更高效的進行範圍查詢及數據遍歷操作，在資料庫中常用來建立索引。
13.另外，資料庫領域還有R樹，它是為瞭解決高維空間搜索等問題，是B-樹在高維空間的擴展。例如，查找方圓20公里內的餐廳問題。它逐層對空間進行分割，節點越往上，表示的空間越大，查找時若該節點代表空間滿足要求，則子節點全部滿足，反之全部不滿足，不必向下查找，僅有兩者相交時才向下查找，因此效率很高。而KD-樹思想與之相似，在此不做進一步介紹。
三：詞典
14.前面介紹，為了結合向量和列表的優點，相繼引入了多種樹結構，然而其相關操作往往較為複雜，因此我們試圖尋找另外一種簡單直觀的數據結構，這即是跳轉表。
跳轉表內部沿橫向分層，同層之間定義前驅後繼關係，層次不同的節點間組成塔，同樣以高度定義前驅後繼。儘管塔內節點相互重複，但可以加速查找。其查找從頂層開始，若查找不到則相應向下搜索。通過控制各塔高度隨機分佈，可以保證其查找、刪除等操作複雜度均為O(logn)。其原理直觀易懂，代碼實現簡單，在Redis中是有序集合鍵的底層實現之一。
15.散列表，通過適當的散列函數將數據映射到地址空間，其實質與數組相似。若地址既無重複又無浪費，即為完美散列。而散列的衝突及解決，本質就是對空間及時間的取捨。散列技術可在期望常數時間內實現查找、刪除等操作，在資料庫中也可用來做索引，速度極快，但它無法支持範圍查找。
四：總結
本文嘗試把常見數據結構理了一遍，目的在於引出為什麼要有這些結構，每種結構適合於做什麼，其本質有哪些異同點；對於每種數據結構的定義、具體操作並沒有詳述，因為網上資料很多，可對應搜索查看，希望能幫助讀者加深對數據結構的理解。
推薦閱讀：
