1.跳表的基本概念

跳表的本質(zhì)是一種查找結(jié)構(gòu)，一般查找問題的解法分為兩個大類：一個是基于各種平衡樹，一個是基于哈希表，跳表比較的特殊，它獨成一派。跳表是基于有序鏈表的基礎(chǔ)上發(fā)展而來的，普通鏈表查找只能一個一個往下跳，而跳表能一次跳過好幾個結(jié)點，這就是它查找效率高的原因。 例如：
如果只有一層那么查找就是逐個遍歷，效率就是O(n)

如果為兩個相鄰結(jié)點添加第二層指向

甚至是添加第三層的指向

每層的結(jié)點個數(shù)呈現(xiàn)2:1的對應(yīng)關(guān)系，查找就是從最高層開始，依次往下查找，這個過程類型二分查找，效率可以來到O(log n)。但是如果嚴(yán)格維持這種2:1的對應(yīng)關(guān)系，插入刪除節(jié)點都需要重新調(diào)整，插入刪除效率直接就降到O(n)。所以跳表采用隨機化結(jié)點的層數(shù)，來控制查找插入刪除的時間復(fù)雜度近似為O(log n)。怎么計算可以參考博客。

2.跳表的結(jié)構(gòu)

跳表的結(jié)點有多層，通過vector<SkiplistNode*> 來存儲下一個結(jié)點的指針。初始化跳表時是帶頭結(jié)點的，它的層數(shù)要求是最高的，它開始只有它自己，默認給一層，后面插入的時候如果有結(jié)點的層數(shù)高于它，需要調(diào)整。

struct SkiplistNode
{	int _data;vector<SkiplistNode*> _nextV;SkiplistNode(int data,int level):_data(data),_nextV(level,nullptr){}
};class Skiplist
{typedef SkiplistNode Node;
private:Node* _head;int _maxLevel = 32;double _p = 0.25;public:Skiplist(){_head = new Node(-1,1);}
};int main()
{Skiplist list;	return 0;
}

3.跳表的增刪改查

看看自己的代碼有沒有問題可以在leetcode上提交代碼：題目鏈接
1）跳表的查找： 跳表中的元素是有序的，在理解跳表查找前先來看一下一個有序的單鏈表是如何查找元素的。

查找有序單鏈表，cur表示當(dāng)前結(jié)點，如果cur的值data等于待查找的值target說明找到了。可如果cur 的下一個結(jié)點的值data大于target，說明target目標(biāo)值不在鏈表中，或者是鏈表遍歷到結(jié)尾還是找不到也說明target目標(biāo)值不在鏈表中，這就是有序單鏈表的查找過程。
有了有序單鏈表的查找的基礎(chǔ)，來看跳表的查找就簡單了。

1、cur表示當(dāng)前結(jié)點、next表示下一個結(jié)點、data表示結(jié)點的數(shù)據(jù)。
2、要從最高層找起，直到遍歷到最低的那一層。
3、如果target 等于 cur的 data說明找到了。
4、如果target 大于 next 的 data，向右找。但是要保證next 不能為NULL。如找19而當(dāng)前cur 的data是7，它的next 是NULL。不代表找不到，而是要到下一層找。
5、如果next的date 大于target 說明target可能在cur 和 next之間，往下一層找。

bool search(int target)
{Node* cur = _head;int level = cur->_nextV.size() -1;while(level >= 0){if(cur->_nextV[level] && cur->_nextV[level]->_data < target){cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_data > target){level--;}else {return true;}}return false;
}

2）跳表的插入： 類比單鏈表的從中間的某個位置插入。需要找到前一個位置prev。跳表要找的是prevV，前結(jié)點指針列表。

1、找到prevV
2、創(chuàng)建一個結(jié)點newNode，先讓newNode->_nextV[i] 逐個指向 prevV[i]->_nextV[i]指向的結(jié)點。再讓prevV[i]->_nextV[i]指向newNode。
3、這里創(chuàng)建newNode層數(shù)是隨機的，需要根據(jù)概率計算。這里參照radis中給定的概率和最大層數(shù)。
4、如果插入節(jié)點的層數(shù)高于頭結(jié)點，需要調(diào)整頭結(jié)點的層數(shù)。

vector<Node*> findPervV(int num)
{Node* cur = _head;int level = _head->_nextV.size() -1;vector<Node*> prevV(level + 1,nullptr);while(level >= 0){			if(cur->_nextV[level] != nullptr && cur->_nextV[level]->_data < num){cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_data >= num){prevV[level] = cur;level--;}}return prevV;	
}void add(int num)
{int n = randomLevel();int level = _head->_nextV.size() -1;vector<Node*> prevV = findPervV(num);// 調(diào)整頭結(jié)點的層數(shù)if(n > _head->_nextV.size()){_head->_nextV.resize(n,nullptr);prevV.resize(n,_head);}Node* newNode = new Node(num,n);	for(int i = 0;i < n;i++){			newNode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newNode;}
}int randomLevel()
{Node* cur = _head;srand(time(NULL));int level= 1;// rand的區(qū)間范圍為[0,RAND_MAX]while(rand() <= RAND_MAX*_p && level < _maxLevel) { level++;}return level;
}

3）跳表的刪除：
1、要到前結(jié)點列表prevV
2、根據(jù)當(dāng)前結(jié)點的層數(shù)，循環(huán)指向prevV[i]->_nextV[i] = del->_nextV[i]

bool erase(int num)
{vector<Node*> prevV = findPervV(num);if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_data != num){return false;}else{Node* del = prevV[0]->_nextV[0];// 當(dāng)前節(jié)點的層數(shù)for(int i = 0;i < del->_nextV.size();i++){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;int index = _head->_nextV.size() -1;// _head->_nextV[index] == nullptr說明最高結(jié)點刪除了，調(diào)整頭結(jié)點while (index >= 0) {if(_head->_nextV[index] == nullptr) {index--;}else {break;}	}return true;}
}

4）跳表的打印： 這里按照單鏈表的思路打印，如果只看第一層那么跳表就像是有序的單鏈表。注意跳表是帶頭指針的，所以直接從_head->nextV[0]開始。

void print()
{Node* cur = _head->_nextV[0];while(cur != nullptr){			cout << cur->_data << "->";	cur = cur->_nextV[0];}cout << "NULL" << endl;
}

4.完整代碼

#include <vector>
#include <iostream>
#include <time.h>
#include <stdlib.h>using namespace std;struct SkiplistNode
{	int _data;vector<SkiplistNode*> _nextV;SkiplistNode(int data,int level):_data(data),_nextV(level,nullptr){}
};class Skiplist
{typedef SkiplistNode Node;
private:Node* _head;int _maxLevel = 32;double _p = 0.25;public:Skiplist(){_head = new Node(-1,1);}bool search(int target){Node* cur = _head;int level = cur->_nextV.size() -1;while(level >= 0){if(cur->_nextV[level] && cur->_nextV[level]->_data < target){cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_data > target){level--;}else {return true;}}return false;}vector<Node*> findPervV(int num){Node* cur = _head;int level = _head->_nextV.size() -1;vector<Node*> prevV(level + 1,nullptr);while(level >= 0){			if(cur->_nextV[level] != nullptr && cur->_nextV[level]->_data < num){cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_data >= num){prevV[level] = cur;level--;}}return prevV;	}void add(int num){int n = randomLevel();int level = _head->_nextV.size() -1;vector<Node*> prevV = findPervV(num);if(n > _head->_nextV.size()){_head->_nextV.resize(n,nullptr);prevV.resize(n,_head);}Node* newNode = new Node(num,n);	for(int i = 0;i < n;i++){			newNode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newNode;}}int randomLevel(){Node* cur = _head;srand(time(NULL));int level= 1;while(rand() <= RAND_MAX*_p && level < _maxLevel) { level++;}return level;}bool erase(int num){vector<Node*> prevV = findPervV(num);if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_data != num){return false;}else{Node* del = prevV[0]->_nextV[0];for(int i = 0;i < del->_nextV.size();i++){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;int index = _head->_nextV.size() -1;while (index >= 0) {if(_head->_nextV[index] == nullptr) {index--;}else {break;}	}return true;}}void print(){Node* cur = _head->_nextV[0];while(cur != nullptr){			cout << cur->_data << "->";	cur = cur->_nextV[0];}cout << "NULL" << endl;}};int main()
{Skiplist list;	list.add(1);list.add(3);list.add(6);cout << list.search(6) << endl;list.erase(9);list.erase(6);cout << list.search(6) << endl;list.print();return 0;
}