目錄

• • 寫在前面
  • 跳表概要
  • 查找步驟
  • 插入步驟
  • 刪除步驟
  • 完整代碼

寫在前面

關于跳表的一些知識可以參考這篇文章,最好是先看完這篇文章再看詳細的思路->代碼的復現步驟:
Redis內部數據結構詳解(6)——skiplist
關于跳表的插入、刪除基本操作其實也就是鏈表的插入和刪除，所以如果不熟悉的話還得先回顧鏈表的插入以及刪除是怎樣的，可以參考：
【數據結構基礎筆記】【鏈表】
相關代碼以及其他語言的寫法或者其他思路可以參考：
1206. 設計跳表
代碼參考鏈接：
https://leetcode-cn.com/problems/design-skiplist/solution/can-kao-redisshi-xian-by-bakezq/
https://www.iteye.com/blog/kenby-1187303

跳表概要

跳表采用隨機法決定鏈表中哪些節點應該增加向前指針以及在該節點中應增加多少個指針。
跳表結構的頭節點需要有足夠的指針域，以滿足可能構造最大級數的需求，而尾節點不需要指針域。
跳表在原有的有序鏈表上增加了多級索引，通過索引來實現快速查找。
1、首先在最高級索引上查找最后一個小于當前查找元素的位置
2、調到次高級索引繼續查找，直到調到最底層為止，如果查找元素存在的話，此刻已經十分接近要查找的元素的位置了。

查找步驟

你需要了解的內容：

1、指定head為左上角
2、初始化prevs數組(轉折點數組)
3、查找只有 right 和 down 兩個方向
4、maxlevel是當前跳表的最大層數，并非一開始人為限制的MAXLEVEL。maxlevel可能會隨著插入新的結點時的產生隨機層數而更新。
但是總是有：maxlevel <= MAXLEVEL

以下面的圖為例：從中你應該能清楚了解到prevs數組的含義。

從從頂層向下遍歷到最底層：


根據這樣的思路可以寫出這樣的代碼：

vector<Node*> _search(int key) {Node* cur = &head;vector<Node*> prevs(MAX_LEVEL);//從頂層向下遍歷，注意這里的maxlevel是當前跳表的最大層數，并非一開始人為限制的MAXLEVEL。//maxlevel可能會隨著插入新的結點時的產生隨機層數而更新。for(int i = maxlevel- 1;i >= 0;i--){//在當前層中比較，直到查找元素小于keywhile(cur->level[i] && cur->level[i]->val < key)cur = cur->level[i];//每層找到一個最靠近的點，作為向下的轉折點prevs[i] = cur;}return prevs; }bool search(int target) {//獲取第一層(最底層)最靠近key且val小于key的節點Node* prev = _search(target)[0];return prev->level[0] && prev->level[0]->val == target; }

插入步驟

插入步驟：
1、通過查找子函數獲取最底層鏈表中<=num值的最近的節點，賦給prevs
2、隨機產生該節點的層數
首先，每個節點肯定都有第1層指針（每個節點都在第1層鏈表里）。
如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p。
節點最大的層數不允許超過一個最大值，記為MaxLevel。

static int random_level() {int level = 1;while (rand() < SKIPLIST_P_VAL && level < MAX_LEVEL) level++;return level; }

randomLevel()的偽碼中包含兩個參數，一個是p，一個是MaxLevel。在Redis的skiplist實現中，這兩個參數的取值為：

p = 1/4
MaxLevel = 32

3、更新當前的跳表中的最大層數maxlevel，在新生成的層里，將prevs[]初始化為head結點：
如下圖：當我們插入的數為2，隨機出來的層數為5，那么新的一層中小于這個num的節點一定是頭結點。

4、生成一個新的結點，值為num，層數為level
5、對于每一層來說，由于新插入了一個結點，于是原本的索引關系就得發生改變：
將原本prevs的在本層的后繼作為cur在本層的后繼，再將cur作為prevs的后繼：
以第0層為例

由于這里的prevs[i]都是head結點，所以可以比較方便的看出關系，整理之后就是下面的樣子：
代碼：

void add(int num) {//1、通過查找子函數獲取最底層鏈表中<=num值的最近的節點。auto prevs = _search(num);//2、隨機產生該節點的層數int level = random_level();//3、更新當前的跳表中的最大層數maxlevel,并且if(level > maxlevel){for(int i = maxlevel; i < level; i++)prevs[i] = &head;maxlevel = level;}Node* cur = new Node(num,level);//for(int i = level -1; i >= 0; i--){cur->level[i] = prevs[i]->level[i];prevs[i]->level[i] = cur；} }

刪除步驟

1、通過查找子函數獲取最底層鏈表中<= num值的最近的節點，賦給prevs
2、特殊情況處理：如果prevs在原鏈表中不存在(是指向空的節點) 或者 最近的節點的值不等于num（沒有值為num的節點），返回錯誤
3、否則，說明存在值為nums的結點，且為prevs[0]->level[0]
4、接下來就是要通過修改節點之間的后繼關系將值為num的前繼后繼節點相連。
prevs的后繼為需要刪除的del節點，則將del的后繼連接到prevs后面，作為新的prevs的后繼
5、將空間釋放
6、刪除掉一個結點可能需要更新當前最大層數（如果刪除的結點是之前層數最多的話）
判斷方法：如果頭結點maxlevel-1層的結點沒有后繼，說明本層已經沒有其他節點了

bool erase(int num) {//1、通過查找子函數獲取最底層鏈表中<= num值的最近的節點，賦給prevsauto prevs = _search(num);//2、特殊情況處理：如果prevs在原鏈表中不存在(是指向空的節點) 或者 最近的節點的值不等于num（沒有值為num的節點），返回錯誤if (!prevs[0]->level[0] || prevs[0]->level[0]->val != num)return false;//3、否則，說明存在值為nums的結點，且為prevs[0]->level[0] Node * del = prevs[0]->level[0];//4、接下來就是要通過修改節點之間的后繼關系將值為num的前繼后繼節點相連。for (int i = 0; i < maxlevel; i++)//prevs的后繼為需要刪除的del節點，則將del的后繼連接到prevs后面，作為新的prevs的后溪if (prevs[i]->level[i] == del)prevs[i]->level[i] = del->level[i];//將空間釋放delete del;//刪除掉一個結點可能需要更新當前最大層數（如果刪除的結點是之前層數最多的話）//如果頭結點maxlevel-1層的結點沒有后繼，說明本層已經沒有其他節點了。while (maxlevel > 1 && !head.level[maxlevel - 1])maxlevel--;return true; }

完整代碼

將成員數據和函數進行了私有公有的劃分：

class Skiplist { private://定義結點struct Node {int val;vector<Node *> level;Node(int val, int size = MAX_LEVEL) : val(val), level(size) {}};//定義隨機結點層數的參數static const int SKIPLIST_P_VAL = RAND_MAX / 4, MAX_LEVEL = 32;//定義頭結點Node head;//定義當前最大層數int maxlevel = 1;//定義search子函數vector<Node*> _search(int key) {Node* cur = &head;vector<Node *> prevs(MAX_LEVEL);// through every level, from top to bottomfor (int i = maxlevel - 1; i >= 0; i--) {// through elements in the current level with smaller valuewhile (cur->level[i] && cur->level[i]->val < key)cur = cur->level[i];prevs[i] = cur;}return prevs;}//定義隨機產生層數子函數static int random_level() {int level = 1;while (rand() < SKIPLIST_P_VAL && level < MAX_LEVEL) level++;return level;}public://初始化跳表的時候也需要初始化headSkiplist() : head(INT_MIN, MAX_LEVEL) {}bool search(int target) {Node* prev = _search(target)[0];return prev->level[0] && prev->level[0]->val == target;}void add(int num) {auto prevs = _search(num);int level = random_level();if (level > maxlevel) {for (int i = maxlevel; i < level; i++)prevs[i] = &head;maxlevel = level;}Node * cur = new Node(num, level);for (int i = level - 1; i >= 0; i--) {cur->level[i] = prevs[i]->level[i];prevs[i]->level[i] = cur;}}bool erase(int num) {auto prevs = _search(num);if (!prevs[0]->level[0] || prevs[0]->level[0]->val != num)return false;Node * del = prevs[0]->level[0];for (int i = 0; i < maxlevel; i++)if (prevs[i]->level[i] == del)prevs[i]->level[i] = del->level[i];delete del;while (maxlevel > 1 && !head.level[maxlevel - 1])maxlevel--;return true;} };/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj = new Skiplist();* bool param_1 = obj->search(target);* obj->add(num);* bool param_3 = obj->erase(num);*/

總結

以上是生活随笔為你收集整理的详细讲解设计跳表的三个步骤(查找、插入、删除)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。