C++常用查找演算法總結

查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，例如編譯程序中符號表的查找，欄位的查找，等等。

1、查找演算法總結

(1). 最容易理解的查找演算法，順序查找法

說明：順序查找適合於存儲結構為順序存儲或鏈接存儲的線性表。

基本思想：順序查找也稱為線形查找，屬於無序查找演算法。從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等於k的結點，表示查找失敗。

複雜度分析：

查找成功時的平均查找長度為：（假設每個數據元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 當查找不成功時，需要n+1次比較，時間複雜度為O(n);

所以，順序查找的時間複雜度為O(n)。

代碼實現：

//順序查找

(2).二分查找

說明：元素必須是有序的，如果是無序的則要先進行排序操作。

基本思想：也稱為是折半查找，屬於有序查找演算法。用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束髮現表中沒有這樣的結點。

複雜度分析：最壞情況下，關鍵詞比較次數為log2(n+1)，且期望時間複雜度為O(log2n)；

註：折半查找的前提條件是需要有序表順序存儲，對於靜態查找表，一次排序後不再變化，折半查找能得到不錯的效率。但對於需要頻繁執行插入或刪除操作的數據集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。——《大話數據結構》

代碼實現：

(3).數表查找

5.1 最簡單的樹表查找演算法——二叉樹查找演算法。

基本思想：二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小於右分支的值，然後在就行和每個節點的父節點比較大小，查找最適合的範圍。 這個演算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。

二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

1）若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

2）若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

3）任意節點的左、右子樹也分別為二叉查找樹。

二叉查找樹性質：對二叉查找樹進行中序遍歷，即可得到有序的數列。

不同形態的二叉查找樹如下圖所示：

有關二叉查找樹的查找、插入、刪除等操作的詳細講解，請移步淺談演算法和數據結構: 七 二叉查找樹。

複雜度分析：它和二分查找一樣，插入和查找的時間複雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間複雜度。原因在於插入和刪除元素的時候，樹沒有保持平衡（比如，我們查找上圖（b）中的「93」，我們需要進行n次查找操作）。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是平衡查找樹設計的初衷。

下圖為二叉樹查找和順序查找以及二分查找性能的對比圖：

基於二叉查找樹進行優化，進而可以得到其他的樹表查找演算法，如平衡樹、紅黑樹等高效演算法。

5.2 平衡查找樹之2-3查找樹（2-3 Tree）

2-3查找樹定義：和二叉樹不一樣，2-3樹運行每個節點保存1個或者兩個的值。對於普通的2節點(2-node)，他保存1個key和左右兩個自己點。對應3節點(3-node)，保存兩個Key，2-3查找樹的定義如下：

1）要麼為空，要麼：

2）對於2節點，該節點保存一個key及對應value，以及兩個指向左右節點的節點，左節點也是一個2-3節點，所有的值都比key要小，右節點也是一個2-3節點，所有的值比key要大。

3）對於3節點，該節點保存兩個key及對應value，以及三個指向左中右的節點。左節點也是一個2-3節點，所有的值均比兩個key中的最小的key還要小；中間節點也是一個2-3節點，中間節點的key值在兩個跟節點key值之間；右節點也是一個2-3節點，節點的所有key值比兩個key中的最大的key還要大。

Definition of 2-3 tree

2-3查找樹的性質：

1）如果中序遍歷2-3查找樹，就可以得到排好序的序列；

2）在一個完全平衡的2-3查找樹中，根節點到每一個為空節點的距離都相同。（這也是平衡樹中「平衡」一詞的概念，根節點到葉節點的最長距離對應於查找演算法的最壞情況，而平衡樹中根節點到葉節點的距離都一樣，最壞情況也具有對數複雜度。）

性質2）如下圖所示：

複雜度分析：

2-3樹的查找效率與樹的高度是息息相關的。

距離來說，對於1百萬個節點的2-3樹，樹的高度為12-20之間，對於10億個節點的2-3樹，樹的高度為18-30之間。

對於插入來說，只需要常數次操作即可完成，因為他只需要修改與該節點關聯的節點即可，不需要檢查其他節點，所以效率和查找類似。下面是2-3查找樹的效率：

analysis of 2-3 tree

5.3 平衡查找樹之紅黑樹（Red-Black Tree）

2-3查找樹能保證在插入元素之後能保持樹的平衡狀態，最壞情況下即所有的子節點都是2-node，樹的高度為lgn，從而保證了最壞情況下的時間複雜度。但是2-3樹實現起來比較複雜，於是就有了一種簡單實現2-3樹的數據結構，即紅黑樹（Red-Black Tree）。

基本思想：紅黑樹的思想就是對2-3查找樹進行編碼，尤其是對2-3查找樹中的3-nodes節點添加額外的信息。紅黑樹中將節點之間的鏈接分為兩種不同類型，紅色鏈接，他用來鏈接兩個2-nodes節點來表示一個3-nodes節點。黑色鏈接用來鏈接普通的2-3節點。特別的，使用紅色鏈接的兩個2-nodes來表示一個3-nodes節點，並且向左傾斜，即一個2-node是另一個2-node的左子節點。這種做法的好處是查找的時候不用做任何修改，和普通的二叉查找樹相同。

Red black tree

紅黑樹的定義：

紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時滿足：

下圖可以看到紅黑樹其實是2-3樹的另外一種表現形式：如果我們將紅色的連線水平繪製，那麼他鏈接的兩個2-node節點就是2-3樹中的一個3-node節點了。

1-1 correspondence between 2-3 and LLRB

紅黑樹的性質：整個樹完全黑色平衡，即從根節點到所以葉子結點的路徑上，黑色鏈接的個數都相同（2-3樹的第2）性質，從根節點到葉子節點的距離都相等）。

複雜度分析：最壞的情況就是，紅黑樹中除了最左側路徑全部是由3-node節點組成，即紅黑相間的路徑長度是全黑路徑長度的2倍。

下圖是一個典型的紅黑樹，從中可以看到最長的路徑(紅黑相間的路徑)是最短路徑的2倍：

a typic red black tree

下圖是紅黑樹在各種情況下的時間複雜度，可以看出紅黑樹是2-3查找樹的一種實現，它能保證最壞情況下仍然具有對數的時間複雜度。

紅黑樹這種數據結構應用十分廣泛，在多種編程語言中被用作符號表的實現，如：

5.4 B樹和B+樹（B Tree/B+ Tree）

平衡查找樹中的2-3樹以及其實現紅黑樹。2-3樹種，一個節點最多有2個key，而紅黑樹則使用染色的方式來標識這兩個key。

維基百科對B樹的定義為「在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序並允許以O(log n)的時間複雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多於2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B樹為系統最優化大塊數據的讀和寫操作。B-tree演算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在資料庫和文件系統。

B樹定義：

B樹可以看作是對2-3查找樹的一種擴展，即他允許每個節點有M-1個子節點。

根節點至少有兩個子節點

每個節點有M-1個key，並且以升序排列

位於M-1和M key的子節點的值位於M-1 和M key對應的Value之間

其它節點至少有M/2個子節點

下圖是一個M=4 階的B樹:

可以看到B樹是2-3樹的一種擴展，他允許一個節點有多於2個的元素。B樹的插入及平衡化操作和2-3樹很相似，這裡就不介紹了。下面是往B樹中依次插入

6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

的演示動畫：

B+樹定義：

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

如下圖，是一個B+樹:

B Plus tree

下圖是B+樹的插入動畫：

B和B+樹的區別在於，B+樹的非葉子結點只包含導航信息，不包含實際的值，所有的葉子結點和相連的節點使用鏈表相連，便於區間查找和遍歷。

B+ 樹的優點在於：

但是B樹也有優點，其優點在於，由於B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。

下面是B 樹和B+樹的區別圖：

Different between B tree and B plus tree

B/B+樹常用於文件系統和資料庫系統中，它通過對每個節點存儲個數的擴展，使得對連續的數據能夠進行較快的定位和訪問，能夠有效減少查找時間，提高存儲的空間局部性從而減少IO操作。它廣泛用於文件系統及資料庫中，如：

有關B/B+樹在資料庫索引中的應用，請看張洋的MySQL索引背後的數據結構及演算法原理這篇文章，這篇文章對MySQL中的如何使用B+樹進行索引有比較詳細的介紹，推薦閱讀。

樹表查找總結：

二叉查找樹平均查找性能不錯，為O(logn)，但是最壞情況會退化為O(n)。在二叉查找樹的基礎上進行優化，我們可以使用平衡查找樹。平衡查找樹中的2-3查找樹，這種數據結構在插入之後能夠進行自平衡操作，從而保證了樹的高度在一定的範圍內進而能夠保證最壞情況下的時間複雜度。但是2-3查找樹實現起來比較困難，紅黑樹是2-3樹的一種簡單高效的實現，他巧妙地使用顏色標記來替代2-3樹中比較難處理的3-node節點問題。紅黑樹是一種比較高效的平衡查找樹，應用非常廣泛，很多編程語言的內部實現都或多或少的採用了紅黑樹。

除此之外，2-3查找樹的另一個擴展——B/B+平衡樹，在文件系統和資料庫系統中有著廣泛的應用。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！