高阶数据结构之跳表
跳表也是一种查找结构，能够快速的查找到数据。
其地位和二叉搜索树、哈希表类似，因此我们来学习跳表这个结构把。
跳表概念
跳表作为一种查找结构，能够设置为 key 或者 key/value 型的结构。
它的最初思路是这样的：每隔两个节点就升高一层，增加一个指针，让指针指向下下个节点
其思路生成的结构会是这个样子
这个思路其实和二分查找很类似，从如果你查找的数据比当前节点的数据大，就去访问该节点相连的所有节点，首先从最大的开始访问，如果比最大的大，就直接到最大的节点去，如果小，就去对比小一点的节点。
这个思路查找数据的时间复杂度可以到 O(LogN) ，但是这个思路有一个缺陷，因为每个节点都需要保持这个 2：1的结构，当新节点插入时，就会造成上下相邻两层节点的2：1结构被破坏，为了保持这个结构，就需要花费很多时间去进行修复，时间复杂度就会到 O(N) 级别。
因此真正的跳表并不是这个结构，而是每个节点随机一个层数，这样插入新节点就不需要为了保持结构，而去修复。就不用额外消耗时间了；结构如下：
此外，每一层的指针都需要去连相同层的节点，比如三层的节点的第三层指针一定连着另一个三层节点，如果没有就说明这个跳表中只有一个三层节点。
跳表概念：
- 每插入一个节点，为该节点随机一个层数
- 相同层的指针一定连着相同层的节点
跳表的实现
跳表的搜索
其实跳表的搜索有点类似于二分查找，不过是基于链表的二分查找。
bool search(int target) {
Node* cur = _head;
//从最高层节点遍历，和 target 对比大小
int level = _head->_next.size() - 1;
while (level >= 0)
{
//如果下一层存在，并且值比target 小，则往右走
if (cur->_next[level] && cur->_next[level]->_val < target)
{
cur = cur->_next[level];
}
//如果这个最高层的指针为空，说明已经是最后一个最高层节点了，所以需要往下走
//而如果是这一层的节点的数值大于target也往下走
else if (cur->_next[level] == nullptr || cur->_next[level]->_val > target)
{
level--;
}
else {
return true;
}
}
return false;
}
从跳表的结构我们可以将搜索分为两种：向下走和向右走。
向下走可以看做当前层的节点的值比查找的数要大，因此我们查找的数肯定在这个节点的前面，因此需要往更低层走。
而向右走可以看做当前层的节点的值比查找的数要小，因此我们查找的数肯定在这个节点的后面，因此需要往后面走。
代码也是根据这个规则走的，只要没走到0层以下，就一定可以继续走。
跳表的插入
其实跳表的插入很简单，只需要解决一个问题：找到新增节点的前面的所有节点。
这是因为新增节点可能层数比最高层的节点层数多，也可能相同或者更少；
而跳表的结构需要节点的相同层指针相连，比如说四层节点的第四层指针一定连接着某个四层及以上层的节点。
因此考虑到这个，新增节点一定需要找到新增节点的所有前置节点。
找到新增节点的前置节点
这个函数的实现和跳表的搜索类似。
不过我们需要去存储前置节点的指针，为了防止溢出，存储指针的数组的大小是最高层的层数大小，如果新增节点层数更高，更高层的指针也是指向null，不用管理。
vector<Node*> findPreNode(int num)
{
Node* cur = _head;
//从最高层节点遍历，和 target 对比大小
int level = _head->_next.size() - 1;
vector<Node*> preV(level + 1,nullptr);
while (level >= 0)
{
//如果下一层存在，并且值比target 小，则往右走，并且说明新节点在这一层节点的后面，因此cur节点不是新节点的上一个节点
if (cur->_next[level] && cur->_next[level]->_val < num)
{
cur = cur->_next[level];
}
//如果这个最高层的指针为空，说明已经是最后一个最高层节点了，所以需要往下走,
// 而新节点的层数可能大于等于这个最高层，因此cur节点是新节点的上一个节点
//而如果是这一层的节点的数值大于target也往下走，并且说明新节点的位置应该在 cur 节点和 这一层节点之间
else if (cur->_next[level] == nullptr || cur->_next[level]->_val >= num)
{
preV[level] = cur;
level--;
}
}
return preV;
}其实跳表的插入和删除的精髓就在于寻找前置指针，找到前置指针后，修改一下就行了。
插入
void add(int num) {
vector<Node*> preV = findPreNode(num);
int n = getRandLevel();
Node* newNode = new Node(num, n);
if (n > _head->_next.size())
{
_head->_next.resize(n);
preV.resize(n);
}
for (int i = 0; i < n; i++)
{
newNode->_next[i] = preV[i]->_next[i];
preV[i]->_next[i] = newNode;
}
}可以看到，插入的代码其实就是修改指针的指向。
随机获取层数
有一个比较重要的点是跳表获取随机层数了。
我们通过随机数来计算概率。
随机数最大值是 RAND_MAX，用RAND_MAX和概率相乘，即可保证随机的概率。
int getRandLevel()
{
int level = 1;
while (rand() < RAND_MAX * _p && level < maxLevel)
{
level++;
}
return level;
}跳表的删除
跳表的删除也很简单，获取删除节点的前置节点，然后修改指向。
有一点需要注意的是，如果获取的 preV[0] 的指针为nullptr，或者指向的节点的值和 num 不同，就说明 num 这个节点不存在，无法删除。
bool erase(int num) {
vector<Node*> preV = findPreNode(num);
if (preV[0]->_next[0] == nullptr || preV[0]->_next[0]->_val != num)
{
return false;
}
else {
Node* del = preV[0]->_next[0];
for (size_t i = 0; i < preV.size(); i++)
{
preV[i]->_next[i] = del->_next[i];
}
delete del;
}
return true;
}跳表的总代码
#include<iostream>
#include<vector>
using namespace std;
struct SkipNode {
SkipNode(int val,int n)
:_val(val),
_next(n,nullptr)
{
}
int _val;
vector<SkipNode*> _next;
};
class Skiplist {
typedef SkipNode Node;
public:
Skiplist() {
srand(time(0));
_head = new Node(-1, 1);
}
bool search(int target) {
Node* cur = _head;
//从最高层节点遍历，和 target 对比大小
int level = _head->_next.size() - 1;
while (level >= 0)
{
//如果下一层存在，并且值比target 小，则往右走
if (cur->_next[level] && cur->_next[level]->_val < target)
{
cur = cur->_next[level];
}
//如果这个最高层的指针为空，说明已经是最后一个最高层节点了，所以需要往下走
//而如果是这一层的节点的数值大于target也往下走
else if (cur->_next[level] == nullptr || cur->_next[level]->_val > target)
{
level--;
}
else {
return true;
}
}
return false;
}
vector<Node*> findPreNode(int num)
{
Node* cur = _head;
//从最高层节点遍历，和 target 对比大小
int level = _head->_next.size() - 1;
vector<Node*> preV(level + 1,nullptr);
while (level >= 0)
{
//如果下一层存在，并且值比target 小，则往右走，并且说明新节点在这一层节点的后面，因此cur节点不是新节点的上一个节点
if (cur->_next[level] && cur->_next[level]->_val < num)
{
cur = cur->_next[level];
}
//如果这个最高层的指针为空，说明已经是最后一个最高层节点了，所以需要往下走,
// 而新节点的层数可能大于等于这个最高层，因此cur节点是新节点的上一个节点
//而如果是这一层的节点的数值大于target也往下走，并且说明新节点的位置应该在 cur 节点和 这一层节点之间
else if (cur->_next[level] == nullptr || cur->_next[level]->_val >= num)
{
preV[level] = cur;
level--;
}
}
return preV;
}
int getRandLevel()
{
int level = 1;
while (rand() < RAND_MAX * _p && level < maxLevel)
{
level++;
}
return level;
}
void add(int num) {
vector<Node*> preV = findPreNode(num);
int n = getRandLevel();
Node* newNode = new Node(num, n);
if (n > _head->_next.size())
{
_head->_next.resize(n);
preV.resize(n);
}
for (int i = 0; i < n; i++)
{
newNode->_next[i] = preV[i]->_next[i];
preV[i]->_next[i] = newNode;
}
}
bool erase(int num) {
vector<Node*> preV = findPreNode(num);
if (preV[0]->_next[0] == nullptr || preV[0]->_next[0]->_val != num)
{
return false;
}
else {
Node* del = preV[0]->_next[0];
for (size_t i = 0; i < preV.size(); i++)
{
preV[i]->_next[i] = del->_next[i];
}
delete del;
}
return true;
}
private:
Node* _head;
size_t maxLevel = 32;
int _p = 0.25;
};总结
跳表的精髓就在于节点的随机层数以及相同层的指针指向相同层的节点这块，理解之后其实可以发现跳表的实现很简单。
跳表能够做到性能和AVL树、红黑树差不多，并且实现更加简单，空间消耗更低，但是和哈希结构相比就没有这么大的优势了，因为哈希结构能够做到常数级别的查找，而跳表的优势在于a、遍历数据有序，b、空间消耗略小，c、哈希表有性能损耗，d、极端情况下哈希表需要红黑树结构补足。
总的来说跳表是很强大的一个结构，并且实现很简单，这是它的一个巨大优势，但是实际使用中，还是需要根据需求来决定选择什么数据结构。