DS高阶：跳表
一、skiplist
1.1 skiplist的概念
skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。skiplist是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》
skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一个有序的链表，查找数据的时间复杂度是O(N)。
1.2 skiplist的优化思路分析
假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图b所 示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半。（多层链表的启发思路）以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图c，这样搜索效率就进一步提高了。
skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。
skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是 插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了。
1.3 随机出层数的含义
插入节点时随机出一个层数究竟是什么意思呢？？？难道直接random任意数就可以了吗？？
答：虽然是随机，但是也有规则的限制。这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图：
一个节点的平均层数（也即包含的平均指针数目），计算如下：
现在很容易计算出： 当p=1/2时，每个节点所包含的平均指针数目为2； 当p=1/4时，每个节点所包含的平均指针数目为1.33。
时间复杂度：logN
具体的分析可以看下面的文章：Redis内部数据结构详解(6)——skiplist
2、skiplist的模拟实现
力扣有一道设计跳表的题. - 力扣（LeetCode）设计跳表
基本的调表需要实现4个函数：构造函数、搜索、插入、删除。下面我们来一个个分析。
2.1 skiplist的基本结构
struct SkiplistNode
{
int _val;//存储对应的值
vector<SkiplistNode*> _nextV;//存放对应的next指针集合
SkiplistNode(const int&val, size_t level = 1) //level表示需要开辟的层数 不传就是默认开满
:_val(val)
{
_nextV.resize(level, nullptr);
}
};
class Skiplist
{
typedef SkiplistNode Node;
public:
private:
Node* _head;//虚拟头节点
const size_t _maxLevel = 32; //用缺省参数去初始化
const double _p = 0.25;//用缺省参数去初始化
};2.2 skiplist的默认构造
Skiplist()
{
srand((unsigned int)time(nullptr));//为了方便后面的随机取层数,先弄一个随机种子
_head = new Node(-1);//默认开一层，用默认构造初始化
}给虚拟头节点申请一块空间，一开始默认就开一层。为了能够方面后面利用rand函数随机取层数，所以在这个地方先用了一个时间种子
我们默认开的是一层，因为在数据量小的时候其实我们可以根据插入的情况去调整_head的层数，如果是数据量特别大的话，也可以一次性就把他开到满
2.3 skiplist的搜索
bool search(int target)
{
//要不断往下走
Node* cur = _head;
int level = _head->_nextV.size() - 1;//从后往前去找
while (level >= 0)
{
//如果我比你大 我就跳过去->更新cur
//如果我比你小或者你为空 我就往下走 --level
if (cur->_nextV[level] == nullptr || target < cur->_nextV[level]->_val) --level;
else if (target > cur->_nextV[level]->_val) cur = cur->_nextV[level];
else return true;
}
return false; //循环结束都没有找到，说明找不到。
}我们要从高层一直找到底层，所以要从_nextV的后面开始找。
1、如果你为空，或者我比你小，那就得往下走 ->--level
2、如果我比你大，就可以直接跳到你的位置->更新cur=cur->_nextV[level]
3、如果找到了就返回true，如果循环结束了都找不到，那就返回false
2.4 找到prevV指针数组
为什么要单独去封装这个函数呢？
因为不管是插入，还是删除，我们都需要去找前驱节点的集合，这样才能去改变连接关系，所以为了提高代码的复用性，封装这样的一个函数，去找到待插入位置或者是待删除位置的前驱节点集合。
vector<Node*> FindPrevNode(int num) //帮助我们找到前驱指针集合
{
//最终我们要返回待插入位置或者是待删除位置的前驱指针集合 一开始的时候默认是head、
Node* cur = _head;
int level = _head->_nextV.size() - 1;
vector<Node*> prevV(level+1, _head);
while (level >= 0)
{
if (cur->_nextV[level] == nullptr || num < cur->_nextV[level]->_val)
{
//更新level的层的前一个节点 往下跳之前保存前驱节点
prevV[level] = cur;
--level;
}
else//(num >= cur->_nextV[level]->_val)
cur = cur->_nextV[level];
}
return prevV;
}当我们需要往后面跳之前，保存当前的cur进去prevV数组中，这样我们返回的数组就是待插入节点对应的前驱节点集合了！
2.5 随机层数的生成函数
我们在插入节点之前，要随机生成一个层数，所以要先实现一个生成层数的函数
2.5.1 C语言rand( )版本
size_t RandomLevel() //C语言版本
{
size_t level = 1;//初始的层数
while (rand() <= RAND_MAX * _p && level < _maxLevel) ++level; //RAND_MAX是随机数的最大值
return level;
}2.5.2 C++11随机数库
size_t RandomLevel() //需要的时候去搜 C++11的随机数库即可 头文件chrono和random
{
//类似随机数种子，但是只用一次是最好的 所以设置成staic 这样就只会调用一次了
static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());//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;
}std::chrono::system_clock::now().time_since_epoch().count() 类似一个时间戳，相当于是随机种子，但是由于只需要初始化一次，所以我们将他变成static变量，这样就只要初始化一次即可！
关于C++11的random库用法，还是比较复杂的，大家可以参考一些相关的文章。
2.6 skiplist的增加
void add(int num) //插入节点
{
vector<Node*> prevV = FindPrevNode(num); //右值引用
size_t n = RandomLevel(); //表示需要开多少层
//如果n超过了_head的最大层数，那么就要调整一下
if (n > _head->_nextV.size())
{
_head->_nextV.resize(n, nullptr);
prevV.resize(n, _head);//不够的地方也要更新过去
}
Node* newnode = new Node(num, n);//申请对应的新节点 然后根据prevV数组去建立连接
for (size_t i = 0; i < n; ++i) //连接前后节点，首先要先连后面的 再连前面的
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}一个很关键的地方就是，我们随机生成了一个层数后，有可能我们的_head的层数都没这个多，所以我们必须利用resize去初始化一下，否则会出现越界访问。
中间插入的逻辑就类似链表的指定位置插入，先让自己的后继指向前驱的后继，然后再让前驱指向自己，必须按照这个顺序，否则会丢失节点
2.7 skiplist的删除
bool erase(int num)
{
//首先 有可能没有这个数 所以要看看是不是真的没有
vector<Node*> prevV = FindPrevNode(num);
if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num) return false;
//有的话，就要去删除然后重新连接
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;
else break;
}
_head->_nextV.resize(i + 1);
return true;
}有可能我们找不到这个数，这个时候就没什么可以删的了。
在删除这个节点之前，我们要先记录这个节点，然后去改变被删除节点的连接关系，类似链表的指定位置删除。
如果我们删除的恰好是最高层的节点，这个时候可以整体对头结点的层数降个高度，这样就提高了查找效率。
三、skiplist跟平衡搜索树和哈希表的对比
1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。但是skiplist在平衡树面前优势明显。
skiplist的优势是：
a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33；
2. skiplist相比哈希表而言，就没有那么大的优势了：
哈希表的优势如下：
a、哈希表平均时间复杂度是O(1)，比skiplist快。
b、哈希表空间消耗略多一点。
skiplist优势如下：
a、遍历数据有序
b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
c、哈希表扩容有性能损耗。
d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。
