高阶数据结构之跳表

跳表也是一种查找结构，能够快速的查找到数据。

其地位和二叉搜索树、哈希表类似，因此我们来学习跳表这个结构把。

跳表概念

跳表作为一种查找结构，能够设置为 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;
};