[高阶数据结构七]跳表的深度剖析
1.前言
跳表是一种查找结构，它有着与红黑树、AVL树和哈希表相同的作用，那么已经学习了红黑树和哈希表这种效率高的数据结构，那么为什么还需要学习跳表呢？--请听我娓娓道来。
本章重点：
本章着重讲解跳表的概念，跳表的实现原理，跳表的模拟实现，以及有了红黑树和哈希表之后，为什么还要学习跳表这种数据结构。
2.跳表的概念
跳表是在有序链表的基础上发展而来的。且看下面发展历程。
有序链表的查找和搜索的效率都是O（N）的。
但是0（N）明显时间复杂度较慢，于是乎，就有大佬相出了，那么能不能相邻的节点上升一层，增加一个指针，让指针指向下下个节点？这样当我们查找时，原来需要比较全部的节点，现在由于上升了一层，那么就变成了一半了。
如下图：
依次重复上述步骤，再上升
发现只有两个节点了，那么就不需要上升了。
skiplist 正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常 类似二分查找 ，使得查找的时间复杂度就降低到了O （LogN）。
设计一个东西，最终都是要考虑它的时间复杂度的，那么按照上述的设计思路，他的时间复杂度如何呢？他的效率如何呢？
SKipList效率分析
其中p代表效率，maxlevel代表的是层数
根据前面的随机层函数，我们其实可以很清晰的观察出，产生越高的节点层数，概率越低。
具体分析过程如下：
- 节点层数至少为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)。
因此通过综合分析，跳表的平均时间复杂度是0（LogN）的。这个过程比较复杂，需要有一定的数学功底，有兴趣想知道怎么来的老铁，可以阅读以下文章：
3.跳表的模拟实现
通过了解了跳表的原理，那么就能够很清楚的知道跳表是如何来的了。
那么对于跳表中的层数应该如何把控呢？---用一个vector，只不过我们平常用的vector是水平来看的，现在把vector竖过来看，发现那就是层数了，每一层里面存放的是指向下一个位置的节点。
基本框架：
struct SkiplistNode
{
int _val;
vector<SkiplistNode*> _nextV;
SkiplistNode(int val, int level)
:_val(val)
, _nextV(level, nullptr)
{}
};
class Skiplist {
typedef SkiplistNode Node;
public:
Skiplist() {
//最开始第一个数插入的时候先给1层
srand((unsigned int)time(0));//生成随机数的种子
_head = new Node(-1, 1);
}
private:
Node* _head;//头结点
size_t _maxlevel = 32;//最大层数
double _p = 0.25;//增加一层必须满足的概率
};这里把最大层数和概率都设置了，如果后续想改成别的，直接修改即可。
跳表需要实现的函数--查找，删除，增加。
搜索函数，即查找：
bool search(int target) {
Node* cur = _head;
int level =(int) cur->_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;//没有这个值
}搜索的规则，_val比它（目标值）小，向右走；_val比它（目标值）大，向下走。这里一定要用的是cur->next来进行比较，否则的话，一旦走到了空又要重新走，这就严重影响效率 了。
增加函数：
vector<SkiplistNode*> FindPrev(int num)
{
//当cur->nextv[level]->val>num时，
//那么此时prev[level]=cur->next[level]
Node* cur = _head;
int level = (int)cur->_nextV.size() - 1;
//找到的前节点最大的层数就是level+1,前一个位置的指针放入prevV
vector<Node*> prevV(level + 1, nullptr);
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;
}
void add(int num) {
//在插入之前应该把这个位置的每前一层的节点都记录一下，方便后续连接
vector<Node*> prevV = FindPrev(num);
int level = RandLevel();
Node* newnode = new Node(num, level);
//如果插入的值是大于头结点的层数，那么头结点扩容到对应的层数
if (level > _head->_nextV.size())
{
_head->_nextV.resize(level, nullptr);
//由于之前prevV对应的是没变化之前的头结点的层数，所以这里
//也需要改变一下
prevV.resize(level, _head);
}
//开始每一层的连接
for (int i = 0; i < level; i++)
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}解释：在插入之前，一定要找到插入这个值所在位置的所有前一层的节点，后续才方便插入。
删除函数：
bool erase(int num) {
//在删除之前也需要找到删除位置的值的每一层的前一个结点
vector<Node*> prevV = FindPrev(num);
//有可能num不在表中，那么就删除失败
if (prevV[0]->_nextV[0] == nullptr ||
prevV[0]->_nextV[0]->_val != 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 level = (int)_head->_nextV.size() - 1;
while (level >= 0)
{
if (_head->_nextV[level] == nullptr)
level--;
else break;
}
_head->_nextV.resize(level + 1);
return true;
}
}删除之前也同理，需要找到要删除节点的所有的前一层的节点值是谁，然后把删除值的前一个节点和后一个节点进行链接上即可。
完整代码如下：
SkipList/SkipList · 青酒余成/初识数据结构 - 码云 - 开源中国 (gitee.com)
4.跳表与红黑树、哈希表的对比
首先与红黑树进行对比：
从时间效率上来看：两种都是差不多的。
从空间效率上来看：红黑树要维护三叉链和节点的颜色，相比与跳表有点浪费空间；
从实现角度上来看：跳表的增删查改代码明显比红黑树的增删查改代码要简单的多。
其次与哈希表进行对比：
严格意义上来说，跳表在哈希表面前就有点cuo了。
但是跳表还是有一定的优势的：1.跳表是有序的；2.跳表的空间消耗低，哈希表要存放指针和表空间；3.哈希表在极端情况下，性能会严重退化，可能需要把红黑树挂接到表空间里面。
5.总结
跳表就讲解到这里啦，后续有疑问的小伙伴欢迎后台TT我。