C++跳跃表个人理解

一、概念

跳跃表是一种基于有序链表的扩展，简称跳表，其就是使用关键节点作为索引的一种数据结构。

可以通过以下方式更快查找到有序链表的某一节点：

利用类似索引的思想，提取出链表中的部分关键节点。比如，给定一个长度为7的有序链表，节点值依次是1->2->3->5->6->7->8，那么我们可以取出所有值为奇数节点的作为关键点。

此时如果要插入一个值是4的新节点，不再需要和原节点8,7,6,5,3逐一比较，只需要比较关键节点8,5,3.

确定了新节点在关键节点中的位置（3和5之间），就可以回到原链表，迅速定位到对应的位置，然后进行插入。

 多层关键节点多层索引

对于跳跃表来说，当然不能只会有一层索引节点，那么可以进一步提取索引，在索引层中提取出一层新的索引。

有了二级索引之后，新的节点可以先和2级索引进行比较，确定大体范围；然后再和1级索引比较；最后回到原链表，找到并插入对应位置。

 层级极限是什么？

当节点足够多的时候，不止能提取出二级索引，还可以向高层次提取，保证每一层是上一层节点数的一半。

提取的极限：同一层只有两个节点的时候，因为一个节点没有比较的意义。

怎么从新节点当中选取一部分提到上一层？

当大量的新节点通过逐层比较，最终插入到原链表之后，上层的索引节点会变得不够用。这时候需要从新节点当中选取一部分提到上一层。

使用随机决定新节点是否提升层级，每次向上提升一层的概率是百分之50.

为什么要随机决定新节点是否层级提升？

（1）跳跃表删除和添加节点是不可预测的，很难用一种有效地算法来保证跳跃表的索引部分始终均匀。

（2）采用随机法虽然不能保证索引绝对均匀分布，却可以让大体趋于均匀。

二、时间复杂度分析

跳跃表将新节点（删除节点）和各层索引节点逐一进行比较，确定原链表的插入或者删除位置。时间复杂度为O(logn)。

跳跃表的插入和删除操作需要的时间复杂度和原始链表一样，都为O(1)。

三、跳跃表的特征

一个完整的跳跃表，应该具有以下特征：

1、一个跳表应该有几个层（level）组成。

2、跳表的第一层包含所有的元素。

3、每一层都是一个有序的链表。

4、如果元素x出现在第i层，则所有比i小的层都包含x。

5、每个节点包含key及其对应的value和一个指向同一层链表的下个节点的指针数组（next[i]）。

四、跳跃表和红黑树性能比较

目前，经常使用的平衡数据结构有：B树、红黑树、AVL树等。跳跃表是平衡树一种替代的数据结构，但是和红黑树不相同的是，跳跃表对于平衡的实现是基于一种随机化的算法，跳跃表的插入和删除工作是比较简单的。

1、查询性能：

跳跃表和红黑树的查询时间复杂度都为O(logn)。

2、插入和删除性能：

跳跃表在进行插入和删除操作时，相对来说，更容易调整结构，也就是可能需要在索引层中增加或者删除相应节点。

红黑树在进行插入和删除操作时，就需要进行旋转或者颜色调度操作，相对复杂一些。

3、空间复杂度：

跳跃表的空间复杂度相对高一些，需要额外的空间来存储多层指针。平均情况下O(n)，最糟糕的情况下O(nlogn)。

红黑树空间开销相对跳跃表来说会低。O(n)。

4、应用场景：

如果要在高并发的场景下，频繁进行插入和删除节点，那么跳跃表可能更合适一些。

如果对空间性能要求较高，那么可以去使用红黑树。

五、代码实现

#include<iostream>
#include<time.h>
#include<assert.h>
#include<stdlib.h>
using namespace std;
#define MAX_L 5//跳跃表最大层数//节点结构
struct Node
{int key;//节点的值Node* next[];//多层链表节点
};
//跳跃表结构
struct Skiplist
{int level;//跳跃表层数Node* head;
};
//创建节点
Node* CreateNode(int level, int key)
{Node* p = (Node*)malloc(sizeof(Node) + level * sizeof(Node*));if (nullptr == p){return nullptr;}for (int i = 0; i < level; ++i){p->next[i] = nullptr;}p->key = key;return p;
}
//创建表
Skiplist* CreateList()
{Skiplist* s = (Skiplist*)malloc(sizeof(Skiplist));if (nullptr == s){return nullptr;}s->level = 0;Node* nh = CreateNode(MAX_L + 1, 0);if (nullptr == nh){free(s);return nullptr;}s->head = nh;return s;
}
//生成新节点的级数
int random()
{int level = 0;while (level <= MAX_L && rand() < RAND_MAX / 2){++level;}return level;
}
//向跳跃表中插入元素
bool InsertNode(Skiplist* s, int key)
{if (nullptr == s) return false;//第一步，查找到在每层待插入位置，更新update数组Node* update[MAX_L + 1] = {};Node* q = nullptr, * p = s->head;//找到每一层插入前的一个节点，更新update数组for (int i = s->level; i >= 0; --i){while (p->next[i] != nullptr && p->next[i]->key < key){p = p->next[i];}update[i] = p;}p = p->next[0];if (p != nullptr && p->key == key){return true;}//第二步，随机产生一个层数int newlevel = random();//新产生的节点层数比原跳跃表大if (newlevel > s->level){for (int i = s->level + 1; i <= newlevel; ++i){update[i] = s->head;}s->level = newlevel;}//第三步，从高往下插入p = CreateNode(newlevel + 1, key);if (nullptr == p){return false;}//根据update数组在每一层中插入新节点for (int i = newlevel; i >= 0; --i){p->next[i] = update[i]->next[i];update[i]->next[i] = p;}return true;
}
//删除跳跃表中的元素
bool DeleteNode(Skiplist* s, int key)
{Node* update[MAX_L + 1] = {};Node * p = s->head;//找到每一层待删除元素前的一个节点，放入update数组中for (int i = s->level; i >= 0; --i){while (p->next[i] != nullptr && p->next[i]->key < key){p = p->next[i];}update[i] = p;}Node* q = p->next[0];assert(q != nullptr);//判断q是否为待删除的节点 if (q==nullptr && q->key != key){return false;}for (int i = s->level; i >= 0; --i){if (update[i]->next[i]==q){update[i]->next[i] = q->next[i];if (s->head->next[i] == nullptr){s->level--;}}}free(q);return true;
}
void Print(Skiplist* s)
{Node* p = nullptr;for (int i = s->level; i >= 0; --i){p = s->head->next[i];cout << "level:" << i << endl;while (p != nullptr){cout << "key:" << p->key << " ";p = p->next[i];}cout << endl;}
}
void FreeList(Skiplist* s)
{if (nullptr == s){return;}Node* q = s->head;Node* next = nullptr;while (q != nullptr){next = q->next[0];free(q);q = next;}free(s);
}
int main()
{Skiplist* mylist = CreateList();for (int i = 1; i < 5; ++i){InsertNode(mylist, i);}DeleteNode(mylist, 3);Print(mylist);free(mylist);return 0;
}