書接前文，
前文書《紅黑樹是怎么來的》我們講了通過紅黑樹（本質上是 2-3 樹或者 2-3-4 樹思想）來維護二叉搜索樹的平衡性，從紅黑樹的實作來看，雖然相對于 2-3 樹來說是簡化了不少，但仍然是相當復雜的，
有沒有更加簡單的實作方案呢？
源于二分思想
在前文《二叉搜索樹的本質》中我們通過將有序陣列的二分查找鏈表化，最終得到二叉搜索樹，
這次，我們還是從有序陣列的二分查找開始，看看能否發明什么新的資料結構，
和以前不同的是，這次我們先將有序陣列鏈表化：
如圖，現在我們考慮如何在該鏈表中查找元素 40，
最簡單的做法是從表頭開始往后遍歷，時間復雜度 O(n)——顯然不是我們想要的，
我們的初步想法是：能否在這個鏈表上執行二分搜索？
對于陣列來說，我們可以通過地址偏移立即定位到中間元素（15），然后發現 40 比 15 大，繼續對 15 后面的元素執行二分查找即可，
鏈表的困境在于，它沒法通過地址偏移來快速定位元素，
不過我們并不死心——有沒有什么奇技淫巧來模擬鏈表上的二分查找？
既然對于鏈表，只能通過指標來遍歷元素，那我們能否通過給節點 1、15、60（頭尾以及二分查找涉及到的中間元素）之間建立額外的指標來實作快速跳轉呢？
如圖：
我們建立了一個額外的鏈表（1→15→60），且該鏈表的每個節點都有一個額外指標指向下一層的同名節點，
有什么用呢？
再來看看如何查找元素 40，
我們可以先查上面（第二層）那個鏈表，只需兩步就走到元素 15，發現 40 介于 15 和 60（15 的下一個元素）之間，于是我們通過 15 的“下降”指標來到第一層鏈表同名節點 15，然后在第一層鏈表中繼續往后查找，
如圖：
和直接在原始鏈表上遍歷不同，通過添加一層“索引”鏈表，我們能和二分查找一樣“直達”中間元素，搜索效率一下子提升了一倍，
那么，這個查詢能否再優化一下呢？
上圖中，15 以后的搜索仍然是線性的，我們同樣可以對 1-15、15-60 之間的兩段子鏈表再次建立“索引鏈表”：
乍看有點小復雜，實際上它仍然是對二分查找的模擬，
我們從上層往下層看，
第三層相當于執行第一次二分，標的元素是 15，然后根據實際情況到 1-15 或者 15-60 區間去查找，
第二層則是在第三層（第一次二分查找）的基礎上做的第二次二分，得到更細粒度的查找區間，
所以說，如果我們從最上層索引鏈表往最下層方向逐層查找，就相當于模擬有序陣列一次次的二分查找，
妙哉！
我們看看建立兩層索引后元素 40 的查找路徑：
和一層相比，查找路徑要短很多，
和普通鏈表相比，這種鏈表通過索引“跳過”了一些節點，以提升搜索效率，因而我們給它起個“望文生義”的名字就叫跳表（skiplist），
由于跳表本質上是對二分法的模擬，所以其搜索時間復雜度同二分搜索一樣是 O(logn)，
資料結構
跳表的節點（最底層除外）除了要指向后繼節點（如果是雙向鏈表還要指向前驅節點），還需要指向下層同名節點，所以節點結構初步定義如下：
class Node {
key: number
val: unknown
// 后繼節點
next: Node | null
// 下層節點（比普通鏈表多出來的指標）
down: Node | null
public constructor(key: number, val: unknown) {
// ......
}
}
上圖中節點 15 表示如下：
// 第三層的 node15
const node15_l3: Node = {
key: 15,
val: 15,
next: node60_l3,
down: node15_l2,
}
// 第二層的 node15
const node15_l2: Node = {
key: 15,
val: 15,
next: node30_l2,
down: node15_l1,
}
// 第一層的 node15
const node15_l1: Node = {
key: 15,
val: 15,
next: node20_l1,
down: null,
}
我們分析一下上面的資料結構定義有沒有什么問題，
首先說明一點，通過建立索引鏈表來提升搜索速度屬于典型的用空間換時間，
不過，我們為同一個元素（如上例中的 15）在每一層都建立了一個獨立的物件——這是不是過于鋪張浪費了？
我們分析一下上面三個 object 的特點，看看有沒有什么優化空間：
- 三個節點的 key、val 都是一樣的；
- 最大的不同在于 next 指標，三個節點的 next 都不一樣；
- 由圖可知，上層節點總是逐層下潛的（即第 n 層節點的 down 指標總是指向第 n - 1 層的同名節點）；
所以我們可以嘗試將同一元素的各層節點合而為一：
class Node {
public key: number
public val: unknown
// 該節點各層的后繼節點指標陣列
public nexts: (Node | null)[]
public constructor(key: number, val: unknown) {
// ......
}
}
如上，我們將 next 和 down 兩個指標合入到 nexts 指標陣列中，nexts[i] 表示該節點在第 i + 1 層的后繼節點，
改造后圖示如下：
如上圖，我們做了四方面的改造：
- 各層的同名節點（同 key）合并成一個節點；
- 引入 nexts 指標陣列，node.nexts[i] 表示節點 node 在第 i + 1 層的后繼節點；
- 為編碼上的方便，引入哨兵節點 head（不表示任何實際節點）；
- 不再對尾節點（圖中的 60）建立索引（沒有必要，編程中用 null 值判斷即可）；
最后我們定義出完整的資料結構：
class SkipList {
// 表頭指標，為方便處理，表頭不表示實際節點， 作為哨兵存在
protected head: Node
// 跳表中元素個數
protected length: number
// 跳表層數
protected level: number
public constructor() {
// 創建表頭
this.head = new Node(-Infinity, undefined)
this.length = 0
this.level = 0
}
}
查找元素
我們看看如何查找節點 40，
任何查找都從表頭 head 且從最上層開始，到第一層為止：
- 取 head.nexts[2]，是 15，小于 40，則取 node15 繼續比較；
- 取 node15.nexts[2]，是 null，說明不能再往后找了，則下降到第二層（nexts 下標 1）；
- 取 node15.nexts[1]，是 30，小于 40，則取 node30 繼續比較；
- 取 node30.nexts[1]，是 null，說明不能再往后找了，則下降到第一層（nexts 下標 0）；
- 取 node30.nexts[0]，是 40，找到，回傳并結束；
如圖：
代碼如下：
class SkipList {
// ......
/**
* 根據 key 查找 value 并回傳，如果沒找到則回傳 undefined
* @param key
*/
public search(key: number): unknown {
if (!this.length) {
return
}
// 從 head 開始找
let node = this.head
// 從最高層開始往下搜索，直到搜到第一層
for (let i = this.level - 1; i >= 0; i--) {
// 如果當前節點該層存在后繼節點，且該后繼節點的 key 小于等于目標 key，則跳到該后繼節點
while (node.nexts[i] && node.nexts[i].key <= key) {
node = node.nexts[i]
}
// 從 node 進入到下一層繼續查找
}
return node.key === key ? node.val : undefined
}
}
超簡單有沒有！
索引層數
在講插入之前，我們先思考一個問題：鏈表中的某個元素應該有多少層（或者說需要給它建多少層索引）？
前面我們通過二分法推匯出多層索引的概念，但如果在實際操作中，每次插入一個元素后都用二分法思想去確定元素的索引層數，可能一次插入會導致大范圍的索引重建（比如原本通過二分法拿到標的節點是 a，插入新元素后再次二分拿到的標的很可能不再是 a），
我們也可以采用類似 B 樹的裂變思想，比如我們規定第 n 層兩個節點之間所囊括的 n - 1 層元素數量不可超過 x，一旦超過就觸發裂變以生成新的索引（裂變可能是級聯的），不過其實作起來也比較復雜，
跳表的設計采用了一種簡單粗暴但很有效的方法：概率法，
思想是這樣的：我們規定第 n 層的元素數量是其下一層（n - 1）數量的 1/N，換句話說，一個元素有 1/N 的概率會向上建一層索引，
以 N = 4 為例，
假設我們想插入元素 22——該元素需要建立幾層索引呢？
有 3/4 的概率不建立任何索引（也就是只有最底下一層），
有 1/4 的概率建立 1 層索引，
有 1/4 * 1/4 即 1/16 的概率建 2 層索引，
有 1/4 * 1/4 * 1/4 即 1/64 的概率建 3 層索引，
依此類推，
如此得到的資料結構本質上是一棵 N 叉樹（這里是 4 叉樹），
我們通過如下代碼計算一個新節點的層數資訊：
class SkipList {
// 最大層數限制
protected static readonly MAX_LEVEL = 32
// 上層元素數是下層數量的 1/N（相當于 N 叉樹）
protected static readonly N = 4
// ......
/**
* 隨機生成 level 層數
* 從最底層開始，每增加一層的概率為 1/N
*/
protected randomLevel(): number {
let level = 1
while (Math.round(Math.random()*10000000) % SkipList.N === 0) {
level++
}
return Math.min(level, SkipList.MAX_LEVEL)
}
}
這里我們通過將生成的亂數對 N 取模和 0 比較來模擬 1/N 的概率（比如 N = 4，則取模后為 0-3），
插入元素
我們看如何插入元素 22，
首先要確定 22 在原始鏈表（第一層鏈表）中的位置，該程序實際就是搜索程序，時間復雜度 O(logn)，
搜索程序如圖：
我們找到應該在 20 和 25 兩個節點之間插入 22，
假如我們通過 randomLevel() 得到層數是 5，插入后整個跳表長這樣：
觀察上圖發現：
- 每層都有 next 指標指向該新節點，具體來說就是搜索路徑上各層最右搜索節點（15、15、20）的 next 指標指向新節點；
- 新層（最高兩層）的前驅節點都是 head；
- 新節點的各層 next 指標指向該層前驅節點的 next 原值；
經上面分析發現，整個插入程序中，關鍵是找出每層的前驅節點，代碼如下：
class SkipList {
/**
* 搜索關鍵字 key，回傳其搜索路徑上經過的每層的前驅節點陣列
* 即每層回傳其左邊相鄰節點
* @param key - 關鍵字
* @returns 關鍵字 key 在每層的前驅節點陣列
*/
private searchPrevNodes(key: number): Node[] {
// 記錄每層走到的最右邊的位置（也就是目標節點的前驅節點）
const prevNodes: Node[] = []
// 從 head 開始
let node = this.head
// 從最上層開始往下找
for (let i = this.level - 1; i >= 0; i--) {
// 如果當前節點該層存在后繼節點，且該后繼節點的 key 小于 key，則跳到該后繼節點
while (node.nexts[i] && node.nexts[i].key < key) {
node = node.nexts[i]
}
// 下沉之前記錄該節點作為本層訪問到的最右節點
prevNodes[i] = node
}
// 如果一個都沒有（串列為空，this.level = 0 時），將 head 加入進去
if (!prevNodes.length) {
prevNodes[0] = this.head
}
return prevNodes
}
}
元素插入邏輯代碼如下：
class SkipList {
// ......
/**
* 將 { key, val } 插入到跳表中
*/
public insert(key: number, val: unknown) {
// 獲取搜索路徑上的各層前驅節點
const prevNodes = this.searchPrevNodes(key)
// 創建新節點
const newNode: Node = { key, val, prev: null, nexts: [] }
// 計算新節點的索引層數
const level = this.randomLevel()
// 逐層處理 next 指標
for (let i = 0; i < level; i++) {
// prevNodes 里面僅有原先 this.level 層的最右 node，而新 level 可能高于原 level，
// 該情況下，超出的層在 prevNodes 里面沒有對應節點，則直接取 head
const leftNode = prevNodes[i] ?? this.head
// 變更 next 指標
newNode.nexts[i] = leftNode.nexts[i]
leftNode.nexts[i] = newNode
}
if (level > this.level) {
this.level = level
}
this.length++
}
}
插入程序的平均時間復雜度是 O(logn)，
洗掉元素
考慮洗掉節點 22，洗掉后整個跳表結構如下：
跳表元素的洗掉本質就是插入的逆操作：將該節點從各層抹除，即將該節點各層的前驅節點的 next 指標指向該節點在該層的后繼節點，
插入程序中可能產生新的層（head 層數隨之增長），而洗掉則可能造成層數減少（head 層數收縮），
通過觀察圖示不難發現，洗掉后和插入前的結構竟然是一模一樣的，如此的穩定性真讓人嘆為驚奇，
不同于其他平衡樹，跳表的插入和洗掉不但完全互逆，而且也沒有復雜的遞回重建程序——這正是跳表這種概率型資料結構的簡單性之精華所在，
洗掉代碼如下：
class SkipList {
// ......
public delete(key: number) {
// 獲取搜索路徑上的各層前驅節點
const prevNodes = this.searchPrevNodes(key)
// 待洗掉的節點就是第一層前驅節點的該層 next 指標所指向的節點
const current = prevNodes[0].nexts[0]
if (!current || current.key !== key) {
return
}
// 從下往上，處理各層的 next 指標
// 需要處理的層：待刪節點的索引層數
for (let i = 0; i < current.nexts.length; i++) {
prevNodes[i].nexts[i] = current.nexts[i]
current.nexts[i] = null
// 如果該層的前驅節點是 head，且調整后其 next 指向 null/undefined，說明該層不再有有效節點，需要將層數減 1
if (!this.head.nexts[i]) {
this.level--
}
}
this.length--
}
}
簡單性的源頭
對比紅黑樹的插入和洗掉實作，你會驚于跳表的實作是如此簡單，為何？
我們假設不使用概率來決定新節點的索引層數，就很可能需要采用類似 B 樹的方案，通過限制兩索引節點之間所轄節點數來決定索引的分裂與合并，比如規定任何兩索引節點之間所轄節點數必須在 N/2 到 N 之間，小于 N/2 則謀求合并，超過 N 則分裂，如此必然會帶來復雜的級聯分裂與合并邏輯，
相反，跳表采用了簡單粗暴但同樣有效的概率法，在插入元素的時候，通過概率計算得出索引層數，而更新索引（插入和洗掉）僅影響該節點在各層的前驅節點，影響非常小，更新程序例外簡單，
所以說，這種資料結構的概率性帶來了其簡單性，
總結
- 我們通過有序陣列的二分查找思想推匯出鏈式資料結構的二分法：多級索引；
- 通過概率決定每個元素的索引層數，在理論正確性的前提下保證了實作的簡單性；
- 插入和洗掉操作的關鍵是找出目標節點在每層的前驅節點；
- 插入和洗掉操作是完全互逆的，表明跳表具備很好的動態穩定性；
- 跳表和紅黑樹的各項操作具備同級別的時間復雜度，但比紅黑樹實作起來更加簡單，范圍查詢也更加直觀高效（直接定位到起始節點，然后直接在第一層順序遍歷即可），所以現在很多專案都采用了跳表這種資料結構（如 Redis、Lucene、LevelDB 等）；
另外，分級索引是人類資訊檢索領域的一個重要思想，圖書檢索、書本目錄、檔案系統、域名（DNS 查詢）、ip 地址、作業系統頁表等等的設計都體現了該思想，
本文完整代碼參見 github: https://github.com/linzier/algo-ts，
左手技術，右手歷史，歡迎關注公眾號”編碼胡同“，訂閱最新文章，為講解的簡單性，本文使用的是單向鏈表，github 中實作的是雙向鏈表，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556933.html
標籤：其他
上一篇：【筆者感悟】筆者的作業感悟【二】
下一篇：返回列表