?????????Hello大家好！很高興我們又見面啦！給生活添點passion，開始今天的編程之路！

我的博客：<但凡.

我的專欄：《編程之路》、《數據結構與算法之美》、《題海拾貝》、《C++修煉之路》

歡迎點贊，關注！

目錄

1、跳表引入

? ? ? ? 1.1、背景

????????1.2、跳表的基本原理

2、跳表模擬實現

? ? ? ? 2.1、跳表節點

? ? ? ? 2.2、跳表框架

? ? ? ? 2.3、 查詢

????????2.4、 查找前置節點

? ? ? ? 2.5、添加節點

? ? ? ? 2.6、刪除節點

3、跳表的性能分析

---

1、跳表引入

? ? ? ? 1.1、背景

????????跳表（Skip List）由美國計算機科學家威廉·普（William Pugh）于1989年提出，目的是解決有序鏈表查詢效率低的問題。傳統鏈表查詢時間復雜度為O(n)，而跳表通過引入多層索引結構，將查詢、插入和刪除操作的時間復雜度優化至O(log n)，同時保持了較高的空間效率。普的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》奠定了跳表在數據結構領域的地位，成為平衡樹的輕量級替代方案。

---

????????1.2、跳表的基本原理

????????跳表的核心思想是通過概率性構建多層索引加速查找。每一層都是有序鏈表，底層包含所有元素，上層逐步稀疏。稀疏與稠密是通過設置概率不同有所差別。每一個跳表的分布都是隨機生成的。查找時從最高層開始，若當前節點的下一個節點值小于目標值，則向右移動；否則向下移動到下一層繼續搜索。插入和刪除操作通過調整相鄰節點的指針實現，并動態維護索引層數。

---

2、跳表模擬實現

? ? ? ? 2.1、跳表節點

? ? ? ? _val存儲每個節點存儲的值，_nextV指向下一個節點。

struct SkiplistNode
{int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};

? ? ? ? 2.2、跳表框架

? ? ? ? 對于跳表類的私有成員變量，有三個，_head是跳表的頭，這個節點不存儲值。_maxlevel存儲最高層高，_p是晉升概率，也就是層高加一的概率。后面會詳細說。

class Skiplist
{typedef SkiplistNode Node;
public:Skiplist(){srand(time(0));_head = new Node(-1, 1);}private:Node* _head;size_t _maxLevel = 32;double _p = 0.5;
};

? ? ? ? 2.3、 查詢

? ? ? ? 我們先來說查找，一會在介紹怎么添加節點、

? ? ? ? 對于查找的過程來說，我們從頭結點開始查找，如果下一個節點的值小于我們想要查找的target，我們就直接跳到下一個節點那。如果下一個節點的值大于我們想要查找的taget，我們就得下降層數。如果層數下降到-1（0層是最低層）也沒有找到target值，就跳出循環返回false。

????????我們拿一個跳表模擬一下查找的過程：

bool search(int target)
{Node* cur = _head;int level = _head->_nextV.size() - 1;while (level >= 0){if (cur->_nextV[level] && cur->_nextV[level]->_val < target){cur = cur->_nextV[level];}//        走到最后一個節點else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target){--level;}else{return true;}}return false;
}

????????2.4、 查找前置節點

? ? ? ? 首先我們先新建一個前置節點，然后把他初始化為level層，其實就是讓他的層數和跳表中最高節點的層數相等。我們把這個前置節點的存儲的值都初始化為_head。因為如果我們要查找的某個值都比跳表中的所有值都小，那么他的前置節點就是head。

? ? ? ? 在循環的過程中，每次調整level我們就記錄一下前置節點：

? ? ? ? 后序刪除和添加節點的時候我們都得先找到前置節點。

vector<Node*> FindPrevNode(int num)
{Node* cur = _head;int level = _head->_nextV.size() - 1;vector<Node*> prevV(level + 1, _head);while (level >= 0){if (cur->_nextV[level] && cur->_nextV[level]->_val < num){cur = cur->_nextV[level];}else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num){prevV[level] = cur;--level;}}return prevV;
}

? ? ? ? 2.5、添加節點

?????????再添加節點的操作中，因為我們要控制每個跳表節點的高度都是隨機的，所以說我們得先說一下生成隨機層高的函數：

? ? ? ? 隨機數生成部分：

??generator是靜態的默認隨機數引擎

? ? ? ?用當前系統時間作為種子(time_since_epoch().count())，確保每次程序運行時種子不同static關鍵字保證在整個程序運行期間只初始化一次

? ?distribution:靜態的均勻實數分布，范圍[0.0, 1.0)用于生成0到1之間的隨機浮點數。

? ? ? ? p是晉升概率，也就是我們層數++的概率。

????????節點層數至少為1。而大于1的節點層數，滿足一個概率分布。

????????節點層數恰好等于1的概率為1-p。

????????節點層數大于等于2的概率為p，而節點層數恰好等于2的概率為p(1-p)。

????????節點層數大于等于3的概率為p^2，而節點層數恰好等于3的概率為p^2*(1-p)。

????????節點層數大于等于4的概率為p^3，而節點層數恰好等于4的概率為p^3*(1-p)。

int RandomLevel()
{static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());static std::uniform_real_distribution<double> distribution(0.0, 1.0);size_t level = 1;while (distribution(generator) <= _p && level < _maxLevel){++level;}return level;
}

? ? ? ? 接下來我們看添加節點操作。首先我們找到應該插入位置的前置節點，然后依次設置每一層的節點鏈接。

void add(int num)
{vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);if (n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);prevV.resize(n, _head);}for (size_t i = 0;i < n;i++){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}
}

? ? ? ? 2.6、刪除節點

? ? ? ? 最后需要注意我們得調整一下頭結點的層數。

bool erase(int num)
{vector<Node*> prevV = FindPrevNode(num);if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){//該節點不存在return false;}else{Node* del = prevV[0]->_nextV[0];for (size_t i = 0;i < del->_nextV.size();i++){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;//如果刪除了最高層節點，就把頭結點層數降一下int i = _head->_nextV.size() - 1;while (i >= 0){if (_head->_nextV[i] == nullptr)--i;elsebreak;}_head->_nextV.resize(i+1);return true;}
}

?

3、跳表的性能分析

????????時間復雜度：查詢、插入、刪除均為O(log n)，依賴隨機層數分布。

????????空間復雜度：平均O(n)，索引節點數量約為n/2 + n/4 +... ≈ n。

? ? ? ? 時間復雜度都是由查詢操作卡著，而查詢操作其實是從上到下遍歷一遍。跳表的高度通常為O(log n)，其中n是節點數量。

????????優勢：實現簡單，無需復雜平衡操作；適合高并發場景（如Redis的有序集合）。

????????跳表作為一種高效動態數據結構，兼具實用性與靈活性，是算法設計中的經典案例。

? ? ? ? 好了，今天的內容就分享到這，我們下期再見！?

?