當我們在電腦中查找文件的時候，我們一般習慣先打開相應的磁盤，再打開文件夾以及子文件夾，最后找到我們需要的文件。這其實就是一個檢索路徑。如果把所有的文件展開，這個查找路徑其實是一個樹狀結構，也就是一個非線性結構，而不是一個所有文件平鋪排列的線性結構。

樹狀結構：文件組織例子

我們都知道，有層次的文件組織肯定比散亂平鋪的文件更容易找到。這樣熟悉的一個場景，是不是會給你一個啟發：對于零散的數據，非線性的樹狀結構是否可以幫我們提高檢索效率呢？

另一方面，我們也知道，在數據頻繁更新的場景中，連續存儲的有序數組并不是最合適的存儲方案。因為數組為了保持有序必須不停地重建和排序，系統檢索性能就會急劇下降。但是，非連續存儲的有序鏈表倒是具有高效插入新數據的能力。因此，我們能否結合上面的例子，使用非線性的樹狀結構來改造有序鏈表，讓鏈表也具有二分查找的能力呢？

一、樹結構是如何進行二分查找的？

之前就和大家分享過，因為鏈表并不具備“隨機訪問”的特點，所以二分查找無法生效。當鏈表想要訪問中間的元素時，我們必須從鏈表頭開始，沿著指針一步一步遍歷，需要遍歷一半的節點才能到達中間節點，時間代價是 O(n/2)。而有序數組由于可以“隨機訪問”，因此只需要 O(1) 的時間代價就可以訪問到中間節點了。

那如果我們能在鏈表中以 O(1) 的時間代價快速訪問到中間節點，是不是就可以和有序數組一樣使用二分查找了？你先想想看該怎么做，然后我們一起來試著改造一下。

直接記錄和訪問中間節點

既然我們希望能以 O(1) 的時間代價訪問中間節點，那將這個節點直接記錄下來是不是就可以了？因此，如果我們把中間節點 M 拎出來單獨記錄，那我們的第一步操作就是直接訪問這個中間節點，然后判斷這個節點和要查找的元素是否相等。如果相等，則返回查詢結果。如果節點元素大于要查找的元素，那我們就到左邊的部分繼續查找；反之，則在右邊部分繼續查找。

對于左邊或者右邊的部分，我們可以將它們視為兩個獨立的子鏈表，依然沿用這個邏輯。如果想用 O(1) 的時間代價就能訪問這兩個子鏈表的中間節點，我們就應該把左邊的中間節點L 和右邊的中間節點 R，單獨拎出來記錄。

并且，由于我們是在訪問完了 M 節點以后，才決定接下來該去訪問左邊的 L 還是右邊的R。因此，我們需要將 L 和 M，R 和 M 連接起來。我們可以讓 M 帶有兩個指針，一個左指針指向 L，一個右指針指向 R。這樣，在訪問 M 以后，一旦發現 M 不是我們要查找的節點，那么，我們接下來就可以通過指針快速訪問到 L 或者 R 了。

將 M 節點改為帶兩個指針，指向 L 節點和 R 節點

對于其余的節點，我們也可以進行同樣的處理。下面這個結構，你是不是很熟悉？沒錯，這就是我們常見的二叉樹。你可以再觀察一下，這個二叉樹和普通的二叉樹有什么不一樣？

二叉檢索樹結構

沒錯，這個二叉樹是有序的。它的左子樹的所有節點的值都小于根節點，同時右子樹所有節點的值都大于等于根節點。這樣的有序結構，使得它能使用二分查找算法，快速地過濾掉一半的數據。具備了這樣特點的二叉樹，就是二叉檢索樹（Binary Search Tree），或者叫二叉排序樹（Binary Sorted Tree）。

講到這里，不知道你有沒有發現，盡管有序數組和二叉檢索樹，在數據結構形態上看起來差異很大，但是在提高檢索效率上，它們的核心原理都是一致的。那么，它們是如何提高檢索效率的呢？核心原理又一致在哪里呢？接下來，我們就從兩個主要方面來看。

• 將數據有序化，并且根據數據存儲的特點進行不同的組織。對于連續存儲空間的數組而言，由于它具有“隨機訪問”的特性，因此直接存儲即可；對于非連續存儲空間的有序鏈表而言，由于它不具備“隨機訪問”的特性，因此，需要將它改造為可以快速訪問到中間節點的樹狀結構。
• 在進行檢索的時候，它們都是通過二分查找的思想從中間節點開始查起。如果不命中，會快速縮小一半的查詢空間。這樣不停迭代的查詢方式，讓檢索的時間代價能達到
  O(log n) 這個級別。

說到這里，你可能會問，二叉檢索樹的檢索時間代價一定是 O(log n) 嗎？其實不一定。

二、二叉檢索樹的檢索空間平衡方案

我們先來看一個例子。假設，一個二叉樹的每一個節點的左指針都是空的，右子樹的值都大于根節點。那么它滿足二叉檢索樹的特性，是一顆二叉檢索樹。但是，如果我們把左邊的空指針忽略，你會發現它其實就是一個單鏈表！單鏈表的檢索效率如何呢？其實是 O(n)，而不是 O(log n)。

退化成鏈表的二叉檢索樹

為什么會出現這樣的情況呢？

最根本的原因是，這樣的結構造成了檢索空間不平衡。在當前節點不滿足查詢條件的時候，它無法把“一半的數據”過濾掉，而是只能過濾掉當前檢索的這個節點。因此無法達到“快速減小查詢范圍”的目的。

因此，為了提升檢索效率，我們應該盡可能地保證二叉檢索樹的平衡性，讓左右子樹盡可能差距不要太大。這樣無論我們是繼續往左邊還是右邊檢索，都可以過濾掉一半左右的數據。

也正是為了解決這個問題，有更多的數據結構被發明了出來。比如：AVL 樹（平衡二叉樹）和紅黑樹，其實它們本質上都是二叉檢索樹，但它們都在保證左右子樹差距不要太大上做了特殊的處理，保證了檢索效率，讓二叉檢索樹可以被廣泛地使用。比如，我們常見的C++ 中的 Set 和 Map 等數據結構，底層就是用紅黑樹實現的。

這里，我就不再詳細介紹 AVL 樹和紅黑樹的具體實現了。為了保證檢索效率，我們其實只需要在數據的組織上考慮檢索空間的平衡劃分就好了，這一點都是一樣的。

三、跳表是如何進行二分查找的？

除了二叉檢索樹，有序鏈表還有其他快速訪問中間節點的改造方案嗎？我們知道，鏈表之所以訪問中間節點的效率低，就是因為每個節點只存儲了下一個節點的指針，要沿著這個指針遍歷每個后續節點才能到達中間節點。那如果我們在節點上增加一個指針，指向更遠的節點，比如說跳過后一個節點，直接指向后面第二個節點，那么沿著這個指針遍歷，是不是遍歷速度就翻倍了呢？

同理，如果我們能增加更多的指針，提供不同步長的遍歷能力，比如一次跳過 4 個節點，甚至一半的節點，那我們是不是就可以更快速地訪問到中間節點了呢？

這當然是可以實現的。我們可以為鏈表的某些節點增加更多的指針。這些指針都指向不同距離的后續節點。這樣一來，鏈表就具備了更高效的檢索能力。這樣的數據結構就是跳表（Skip List）。

一個理想的跳表，就是從鏈表頭開始，用多個不同的步長，每隔 2^n 個節點做一次直接鏈接（n 取值為 0，1，2……）。跳表中的每個節點都擁有多個不同步長的指針，我們可以在每個節點里，用一個數組 next 來記錄這些指針。next 數組的大小就是這個節點的層數，next[0]就是第 0 層的步長為 1 的指針，next[1]就是第 1 層的步長為 2 的指針，next[2]就是第 2 層的步長為 4 的指針，依此類推。你會發現，不同步長的指針，在鏈表中的分布是非常均勻的，這使得整個鏈表具有非常平衡的檢索結構。

理想的跳表

舉個例子，當我們要檢索 k=a6時，從第一個節點 a1開始，用最大步長的指針開始遍歷，直接就可以訪問到中間節點 a5。但是，如果沿著這個最大步長指針繼續訪問下去，下一個節點是大于 k 的 a9，這說明 k 在 a5和 a9之間。那么，我們就在 a5和 a9之間，用小一個級別的步長繼續查詢。這時候，a5的下一個元素是 a7，a7依然大于 k 的值，因此，我們會繼續在 a5和 a7之間，用再小一個級別的步長查找，這樣就找到 a6了。這個過程其實就是二分查找。時間代價是 O(log n)。

四、跳表的檢索空間平衡方案

不知道你有沒有注意到，我在前面強調了一個詞，那就是“理想的跳表”。為什么要叫它“理想”的跳表呢？難道在實際情況下，跳表不是這樣實現的嗎？的確不是。當我們要在跳表中插入元素時，節點之間的間隔距離就被改變了。如果要保證理想鏈表的每隔 2^n 個節點做一次鏈接的特性，我們就需要重新修改許多節點的后續指針，這會帶來很大的開銷。

所以，在實際情況下，我們會在檢索性能和修改指針代價之間做一個權衡。為了保證檢索性能，我們不需要保證跳表是一個“理想”的平衡狀態，只需要保證它在大概率上是平衡的就可以了。因此，當新節點插入時，我們不去修改已有的全部指針，而是僅針對新加入的節點為它建立相應的各級別的跳表指針。具體的操作過程，我們一起來看看。

首先，我們需要確認新加入的節點需要具有幾層的指針。我們通過隨機函數來生成層數，比如說，我們可以寫一個函數 RandomLevel()，以 (1/2)^n 的概率決定是否生成第 n 層。這樣，通過簡單的隨機生成指針層數的方式，我們就可以保證指針的分布，在大概率上是平衡的。

在確認了新節點的層數 n 以后，接下來，我們需要將新節點和前后的節點連接起來，也就是為每一層的指針建立前后連接關系。其實每一層的指針鏈接，你都可以看作是一個獨立的單鏈表的修改，因此我們只需要用單鏈表插入節點的方式完成指針連接即可。

這么說，可能你理解起來不是很直觀，接下來，我通過一個具體的例子進一步給你解釋一下。

我們要在一個最高有 3 層指針的跳表中插入一個新元素 k，這個跳表的結構如下圖所示。

假設我們通過跳表的檢索已經確認了，k 應該插入到 a6和 a7兩個節點之間。那接下來，我們要先為新節點隨機生成一個層數。假設生成的層數為 2，那我們就要修改第 0 層和第 1層的指針關系。對于第 0 層的鏈表，k 需要插入到 a6和 a7之間，我們只需要修改 a6和 a7的第 0 層指針；對于第 1 層的鏈表，k 需要插入到 a5和 a7之間，我們只需要修改 a5和 a7的第 1 層指針。這樣，我們就完成了將 k 插入到跳表中的動作。

通過這樣一種方式，我們可以大大減少修改指針的代價。當然，由于新加入節點的層數是隨機生成的，因此在節點數目較少的情況下，如果指針分布的不合理，檢索性能依然可能不高。但是當節點數較多的時候，指針會趨向均勻分布，查找空間會比較平衡，檢索性能會趨向于理想跳表的檢索效率，接近 O(log n)。

因此，相比于復雜的平衡二叉檢索樹，如紅黑樹，跳表用一種更簡單的方式實現了檢索空間的平衡。并且，由于跳表保持了鏈表順序遍歷的能力，在需要遍歷功能的場景中，跳表會比紅黑樹用起來更方便。這也就是為什么，在 redis 這樣的系統中，我們經常會利用跳表來代替紅黑樹作為底層的數據結構。

五、總結

首先，對于數據頻繁變化的應用場景，有序數組并不是最適合的解決方案。我們一般要考慮采用非連續存儲的數據結構來靈活調整。同時，為了提高檢索效率，我們還要采取合理的組織方式，讓這些非連續存儲的數據結構能夠使用二分查找算法。

數據組織的方式有兩種，一種是二叉檢索樹。一個平衡的二叉檢索樹使用二分查找的檢索效率是 O(log n)，但如果我們不做額外的平衡控制的話，二叉檢索樹的檢索性能最差會退化到 O(n)，也就和單鏈表一樣了。所以，AVL 樹和紅黑樹這樣平衡性更強的二叉檢索樹，在實際工作中應用更多。

除了樹結構以外，另一種數據組織方式是跳表。跳表也具備二分查找的能力，理想跳表的檢索效率是 O(log n)。為了保證跳表的檢索空間平衡，跳表為每個節點隨機生成層級，這樣的實現方式比 AVL 樹和紅黑樹更簡單。

無論是二叉檢索樹還是跳表，它們都是通過將數據進行合理組織，然后盡可能地平衡劃分檢索空間，使得我們能采用二分查找的思路快速地縮減查找范圍，達到 O(log n) 的檢索效率。

除此之外，我們還能發現，當我們從實際問題出發，去思考每個數據結構的特點以及解決方案時，我們就會更好地理解一些高級數據結構和算法的來龍去脈，從而達到更深入地理解和吸收知識的目的。并且，這種思考方式，會在不知不覺中提升你的設計能力以及解決問題的能力。