跳表是平衡树的一种替代的数据结构，和红黑树不同，跳表对树的平衡的实现是基于一种随机化的算法，这样就使得跳表的插入和删除的工作比较简单。
跳表是一种复杂的链表，在简单链表的节点信息之上又增加了额外的后继节点指针。这样，单链表每次只能向后移动一个节点，而跳表每个节点有多个后继节点，就可以移动多个不同的距离，加快了查找的速度。
跳表的数据存储结构
定义：如果一个节点存在k个向前的指针的话，则该节点为k层的节点。一个跳表的层MaxLevel为跳表中所有节点层数的最大值。
下图为一个完整的跳表：
可以设计跳表节点的数据结构：
struct SkipNode{
int key; //跳表节点的key
int value; //跳表节点的val，可以是其他类型
int level; //跳表节点的level，实际的节点level从0 开始，计到level
SkipNode** forward; //跳表节点的后继
SkipNode(int lvl){ //跳表节点的level，则它的level计数从0计到level
level = lvl;
forward = new SkipNode*[level + 1];
}
~SkipNode(){
delete[] forward;
}
};
跳表的实现
1. 初始化
初始化的过程就是生成下图中红色区域内的部分，也就是跳表的基本结构：
2. 查找操作
跳表的查找依赖于节点的forward数组，跳表的每个节点都有一个后继节点数组forward， 里面存放着该节点向后的多个层次的后继。后继节点层次越高，则距离当前节点越远。这样在进行查找的时候，先看高层次的后继节点，如果后继节点的key小于要找的key，则沿着当前层次的后继节点链继续走，直到后继节点的key大于等于要查找的key；然后层次减去一继续进行搜索操作，直到层次变为0.
3. 插入操作
插入的时候，先根据key值利用查找操作的方法找到应该被插入的位置，然后修改forward指针，并更新跳表的level变量。
4. 删除操作
删除的时候，先根据key值找到节点的位置，然后更改forward指针，并更新跳表的level变量。
实现(c++)
#include<iostream>
using namespace std;
#define MAX_LEVEL 20
#define INVALID_VALUE 1 << 30
struct SkipNode{
int key; //跳表节点的key
int value; //跳表节点的val，可以是其他类型
int level; //跳表节点的level，实际的节点level从0 开始，计到level
SkipNode** forward; //跳表节点的后继 SkipNode(int lvl){ //跳表节点的level，则它的level计数从0计到level
level = lvl;
forward = new SkipNode*[level + 1];
}
~SkipNode(){
delete[] forward;
}
}; struct SkipList{
SkipNode* header;
SkipList(){
header = new SkipNode(0); //初始时，只设置一层跳
for (int i = 0; i < MAX_LEVEL; i++){
header->forward[i] = NULL;
}
};
~SkipList(){ }
int FindEle(int key){
SkipNode* p = header, *q;
int k = header->level;
//跳表的每个节点多层，则含有多个后继节点，后继节点的level越高，则该后继节点距离该节点越远
//在查找的时候，将一个节点的后继节点level从高到低进行遍历。
//当前节点在level层时，其后继节点的key若大于目标节点，则应该缩小后继距离，则此时可以减小level...直到level为0.
//到level为0时候节点q的key不小于 要查找的key，则若跳表中存在元素key，则应该为q节点
for (int level = k; level >= 0; level--){
q = p->forward[level];
while (q && q->key < key){
p = q;
q = p->forward[level];
};
}
if (q->key == key){
return q->value;
}
return INVALID_VALUE;
}
bool Insert(int key, int val){
SkipNode* p = header, *q;
SkipNode* update[MAX_LEVEL]; //update数组记录每层 最后一个节点key值小于要插入的key的节点
int k = header->level; // k 记录跳表中level的最大值
for (int level = k; level >= 0; level--){
q = p->forward[level];
while (q && q->key < key){
p = q;
q = p->forward[level];
}
update[level] = p;
}
if (q->key == key){ //不能含有相同的元素
q->value = val;
return false;
}
int new_level = rand();
if (new_level > header->level){ //随机生成节点的level
if (new_level > header->level && header->level == MAX_LEVEL - 1){
new_level = header->level;
}
else{
k = new_level = ++header->level; //若生成的level大于header的level，则更新 header->level 和 k
update[k] = header;
} }
SkipNode* new_node = new SkipNode(new_level);
new_node->key = key;
new_node->value = val; //对插入的节点，更改其前驱和后继
for (int level = k; level >= 0; level--){
p = update[level];
new_node->forward[level] = p->forward[level];
p->forward[level] = new_node;
}
return true;
} bool Delete(int key){
SkipNode* p = header, *q;
SkipNode* update[MAX_LEVEL]; //update数组记录每层 最后一个节点key值小于要插入的key的节点
int k = header->level; // k 记录跳表中level的最大值
for (int level = k; level >= 0; level--){
q = p->forward[level];
while (q && q->key < key){
p = q;
q = p->forward[level];
}
update[level] = p;
}
if (!q || q->key != key){ //若不存在元素key，直接返回
return false;
}
//删除该节点，并更新其前驱和后继
for (int level = k; level >= 0; level--){
p = update[level];
if (p->forward[level] == q){ //如果update节点的后继为要删除的节点，则进行更新
p->forward[level] = q->forward[level];
}
}
//删除该节点，可能会导致整个跳表的level减少
while (header->forward[k] == NULL && k >= 0)
k--;
header->level = k; delete q; return true;
}
};
参考: 跳表SkipList