跳表 | 基本概念 | 代码实现

1.跳表的基本概念

跳表的本质是一种查找结构，一般查找问题的解法分为两个大类：一个是基于各种平衡树，一个是基于哈希表，跳表比较的特殊，它独成一派。跳表是基于有序链表的基础上发展而来的，普通链表查找只能一个一个往下跳，而跳表能一次跳过好几个结点，这就是它查找效率高的原因。 例如：
如果只有一层那么查找就是逐个遍历，效率就是O(n)

如果为两个相邻结点添加第二层指向

甚至是添加第三层的指向

每层的结点个数呈现2:1的对应关系，查找就是从最高层开始，依次往下查找，这个过程类型二分查找，效率可以来到O(log n)。但是如果严格维持这种2:1的对应关系，插入删除节点都需要重新调整，插入删除效率直接就降到O(n)。所以跳表采用随机化结点的层数，来控制查找插入删除的时间复杂度近似为O(log n)。怎么计算可以参考博客。

2.跳表的结构

跳表的结点有多层，通过vector<SkiplistNode*> 来存储下一个结点的指针。初始化跳表时是带头结点的，它的层数要求是最高的，它开始只有它自己，默认给一层，后面插入的时候如果有结点的层数高于它，需要调整。

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表示当前结点，如果cur的值data等于待查找的值target说明找到了。可如果cur 的下一个结点的值data大于target，说明target目标值不在链表中，或者是链表遍历到结尾还是找不到也说明target目标值不在链表中，这就是有序单链表的查找过程。
有了有序单链表的查找的基础，来看跳表的查找就简单了。

1、cur表示当前结点、next表示下一个结点、data表示结点的数据。
2、要从最高层找起，直到遍历到最低的那一层。
3、如果target 等于 cur的 data说明找到了。
4、如果target 大于 next 的 data，向右找。但是要保证next 不能为NULL。如找19而当前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，前结点指针列表。

1、找到prevV
2、创建一个结点newNode，先让newNode->_nextV[i] 逐个指向 prevV[i]->_nextV[i]指向的结点。再让prevV[i]->_nextV[i]指向newNode。
3、这里创建newNode层数是随机的，需要根据概率计算。这里参照radis中给定的概率和最大层数。
4、如果插入节点的层数高于头结点，需要调整头结点的层数。

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;// rand的区间范围为[0,RAND_MAX]while(rand() <= RAND_MAX*_p && level < _maxLevel) { level++;}return level;
}

3）跳表的删除：
1、要到前结点列表prevV
2、根据当前结点的层数，循环指向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];// 当前节点的层数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说明最高结点删除了，调整头结点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;
}