跳表(SkipList)

缘起

数组和链表各有所长——前者便于静态查找， 但动态维护成本较高； 后者便于增量式的动态维护， 但只能支持顺序查找。为结合二者的优点， 同时弥补其不足，才逐步引入了二叉树、平衡二叉搜索树，其查找、插入和删除操作均可在O(logn)时间内完成。尽管如此，这些结构的相关算法往往较为复杂，代码实现和调试的难度较大，其正
确性、鲁棒性和可维护性也很难保证。设计并引入跳表（skip list） 结构的初衷，正是在于试图找到另外一种简便直观的方式，来完成这一任务。具体地，跳转表是一种高效的词典结构，它的定义与实现完全基于（多层）有序链表结构，其查询和维护操作在平均的意义下均仅需O(logn)时间。

跳表的性能上与红黑树(例如c++ STL中的set与map都是用红黑树实现的)、AVL（绝对平衡的结构，红黑树是稍差一些的平衡）等等匹敌,但是缺点是跳表比较吃内存(原因也很直观——红黑树、AVL中是没有重复的元素的(有人对平衡类型的动态查找树只进行惰性删除，但是主流实现不是),但是跳表有很多重复元素)

但因为其简单性、易维护性，所以很多开源软件，如Redis 和 LevelDB 都有用到它.

分析

首先我们来看看跳表长什么样子

为什么跳表搜索比较快?

举个例子, 上图中搜索117

要经过如下几个步骤

(1) 比较 21， 比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85， 比 85 大，从后面找

(5) 比较 117， 等于 117， 找到了节点。

看到了吧? 跳着、跳着（相比于链表（哪怕有序,也得老老实实一个一个遍历）的顺序遍历）就把元素找到了. 所以跳表的名字取的还是很到位的.

跳表的插入

首先丢硬币决定要插入的层数（level）K，即打算将这个元素插入到底基层， 则自K层以下，都要插入此元素

分两种情况

  1. 如果1<=K<=当前最大层次（即top->level）,注意，我的最低层次是1，则在level1~levelK，都要插入此元素

    下面的例子是插入119，K=2

  2. 如果K>当前最大层次，则需要新建一层，并从上往下都要插入, 例如下图最大层次原本是3，同样是插入119，结果你来一个K=4，注意，这种情况是有必要的，不然跳表的层次要是上不去的话，都在一层，那岂不是退化为有序链表O（n）的查询速度了?

跳表的删除

算法就是先找到，然后一溜删除（标准的链表删除，其实链表的删除采不采用惰性删除都一样，都是O（1）复杂度）

例如，删除71

跳表有如下性质

1
2
3
4
5
6
7
8
9
10
11
跳表具有如下性质：

(1) 由很多层结构组成

(2) 每一层都是一个有序的单向链表（一般默认是升序）

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现（正下方）。(所以跳表比较吃内存， 因为重复元素的存在)

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

关于跳表算法和之前的树型算法比较总结如下

1
2
3
4
5
6
7
8
9
10
11
不仅逻辑上比AVL、红黑树，B树简单而且代码的长度是它们的一半..
尽管 AVL 树和红黑树在数据搜索和排序方面都是有效的数据结构，但是这两种数据结构都需要重新平衡操作来
保持树的平衡，这就导致大量费用和复杂性。,我的理解就是前两种是维持某种绝对的平衡（最坏情况下都是O(NlogN)复杂度）,
但是正如静态查找树表中的次优二叉查找树虽然不如最优二叉查找树那么最优，但是建立起来的时间耗费要低得多(次优二叉查找树的建立的时间复杂度是O(NlogN)【2】,但是最优二叉查找树的建立的时间复杂度是O（N^3）)【1】
但其实实际工作中次优并不比最优效率低多少...
跳跃表特别适用于查找。这种数据结构提供了树的功效且不需要担心重新平衡问题。
跳跃表（Skip List）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。
跳跃表其实真心简单！跳跃表也是有序链表（即链表中的元素是按照从小到大排序的），有人会问那么为什么不用折半查找呢? 那是因为折半只适用于静态查找表,并且必须按照数组存储(即可以随机访问元素)
但是静态查找的缺点就在于不能很方便的插入与删除,尤其是插入(删除你可以采用惰性删除,即打算删除某个元素的时候,只是标记这个元素被删除了，而不是真的删除了它)
插入的话,折半这种方法必定导致大量元素的移动而产生大量的时间耗费,所以我们就想到了链表——链表的优势不在查找(一个链表，哪怕是有序链表，你要找一个元素也要O(N),因为你必须一个一个找过去,而有序数组的话，只需要折半算法的O(logN)),而在于插入与删除(O(1)级别的时间)
所以跳跃表干的事情就是保留了链表插入与删除的优势，利用额外的空间来换时间克服查找慢的弱点,所以跳跃表就是空间换时间(我觉得所有快速的算法本质上都是hash，即空间换时间)

跳表的空间复杂度分析:

如果确定高度的算法是抛硬币，只要没抛到正面就继续抛，直至抛到为止，然后拿抛硬币的次数作为此次高度值，则遵从几何分布，期望是1/0.5=2, 所以期望跳表的高度是2，则跳表的空间复杂度是O(n).

不难知道，空间复杂度越高，跳表的性能也越好(因为跳的也越频繁).

跳表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define LOCAL

const int INF = 0x3f3f3f3f; 

typedef struct SkipListNode
{
	int val, level;
	SkipListNode *right, *down;
	SkipListNode(int val, int level):val(val),level(level),right(0),down(0){}
} SkipListNode, *SkipList; // 跳表节点和跳表

void init(SkipList &top) // 初始化跳表，其中top是跳表的查询入口，就是图示中的top
{
	top = new SkipListNode(-INF, 1);
	SkipList tail = new SkipListNode(INF, 1); // 层数从1开始，最低1层, 该层最小是-INF，最大是INF
	top->right = tail;
}

void search(SkipList top, int val, SkipList &loc, SkipList pos[], bool flag, int &lv) // 在跳表top中搜索val，如果找到的话，其指针存放在loc中，一路待插入的位置保存在insertPos中,这样在插入的时候就可以直接插入了，而不需要再次扫描
{ // flag=true表示只是想单纯的查询有木有，false为false的话，表示目的是想得到插入位置信息
	int level = top->level;
	bool found = false;
	SkipList p = top; // 从top开始移动
	while(p)
	{
		while (p->right->val < val) p = p->right; // 首先在每根链表从左至右扫描，直至p的右节点>=val(肯定会的，因为每层升序链表的最后一个节点是INF节点)，注意，因为每层链表的起始节点都是-INF节点，所以p->right都是有实际意义的, 可见每层加一个无穷的头尾是多么的重要
		if (p->right->val == val) // 找到了, 则因为跳表需要上层有的话，则自他以下的所有层都要有， 所以这里不能return.
		{
			 loc = p->right;
			 if (flag) return; // 这样对于单纯的查询操作就不需要再往下搜了（加快一般查询操作, 即不是insert或者delete调用的search），否则的话，因为插入或者删除需要知道自顶以下位置信息, 所以还是要往下搜索的——不能停止的
			 if (!found) // 第一次找到val，记录其所在层次, 这个删除要用,因为删除要用 pos[lv,...,1]
			 {
				  lv = level;
				  found = true;
			 }
		}
		// 说明 p->right->val > val && p->val < val, 所以如果要插入的话，val就应该作为p的后继
		pos[level--] = p;
		p = p->down; // 到下层去， 继续
	}
}

int randomlevel() // 掷硬币决定新插入的元素在第几层（最低层是1）, 这个数既可能小于当前跳表的层次，也可能>当前跳表的层次
{
	int ret = 1;
	while(rand()<20000) ret++; // 只要没超过2w，就继续掷硬币
	return ret;
}

void subinsert(SkipList insertPos[], int level, int val) // 根据插入位置信息insertPos[level,...,1] 插入val到跳表top中去,val在第i层应该成为insertPos[i]的后继
{
	SkipList prev = 0; // 上一层插入的节点
	do
	{
		SkipList newNode = new SkipListNode(val, level); // 新插入的跳表节点
		if (prev) {prev->down = newNode;}
		prev = newNode;
		newNode->right = insertPos[level]->right; // 标准的链表插入
		insertPos[level]->right = newNode;
	}while(--level);
}

void insert(SkipList &top, int val) // 注意，如果掷硬币>当前跳表的层数，则跳表的入口可能变化，所以要 &
{
	SkipList loc = 0; // 插入位置
	SkipList *insertPos = new SkipList[top->level+2]; // 插入位置，因为最底层是1，而insertPos[top->level+1]是给如果掷硬币决定的插入层次>当前跳表的层次的话，需要新盖一层, insertPos[top->level+1]指的就是这个插入位置
	int level = top->level; //从顶层开始搜索
	search(top,val,loc,insertPos, false, level);
	if (loc)
	{
		puts("该元素已存在，禁止插入!");
		return;
	}
	// 该元素不存在，要决定它的插入层次
	level = randomlevel();
	if (level > top->level) // 如果超过当前跳表的高度
	{
		SkipList newTop = 0; // 新的跳表入口
		init(newTop); // 新盖一层, newTop是新的跳表的入口
		newTop->level = newTop->right->level = level = top->level+1;
		newTop->down = top;
		top = insertPos[level] = newTop;
	}
	subinsert(insertPos, level, val);
}


void subdel(SkipList &top, SkipList delpos[], int level) // 用 delPos[level,...,1]信息删除跳表
{
	do 
	{
		SkipList todel = delpos[level]->right; // 要移除的节点
		delpos[level]->right = todel->right; // 移除 todel
		delete todel; // 释放空间
		todel = 0;
		if (top->right->val == INF)  // 如果这一层删空了(就跟俄罗斯方块一样)
		{
			SkipList pretop = top;
			top = top->down;
			delete pretop->right;
			delete pretop;
			pretop = 0; // 回收此层的两INF节点
		}
	} while (--level);
}

void del(SkipList &top, int val) // 跳表top 删除val, 因为可能跳表的最高一层就只有一个节点，而如果此节点刚好就是要删除的节点的话，则这一层就都没有了，即跳表的入口可能变化
{
	SkipList loc = 0;
	SkipList *delPos = new SkipList[top->level+1]; // 保存删除位置信息
	int level = top->level; // 从顶层开始搜索
	search(top, val, loc, delPos,false, level); // 查询val的时候保存删除位置
	if (!loc)
	{
		puts("此元素不存在，删除失败！");
		return;
	}
	subdel(top, delPos, level);
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	srand((unsigned int)time(NULL));
	SkipList top = 0;
	init(top);
	int a[8]={7,14,21,32,37,71,85,117};
	//测试跳表的插入
	for (int i = 0; i < 8; i++)
	{
		insert(top,a[i]);
	}
	//测试跳表的删除
	for (int i = 0; i < 8; i++)
	{
		del(top,a[i]);	
	}
	return 0;
}

和原先写的相比，这里简化了一些操作. 特别是search函数

参考

【1】https://yfsyfs.github.io/2019/06/17/%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

【2】https://yfsyfs.github.io/2019/06/17/%E6%AC%A1%E4%BC%98%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

【3】https://kenby.iteye.com/blog/1187303