前言
Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。
跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，跳跃表使用概率均衡技术而不是使用强制性均衡，因此，对于插入和删除结点比传统上的平衡树算法更为简洁高效。
一个跳表具有以下特征：
1.一个跳表应该有几个层（level）组成；
2.跳表的第一层包含所有的元素；
3.每一层都是一个有序的链表；
4.如果元素x出现在第i层，则所有比i小的层都包含x；
5.第i层的元素通过一个down指针指向下一层拥有相同值的元素；
6.Top指针指向最高层的第一个元素。
下面来研究一下跳表的核心思想: 先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。
如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
如上图所示，是一个即为简单的跳跃表。传统意义的单链表是一个线性结构，向有序的链表中插入一个节点需要O(n)的时间，查找操作需要O(n)的时间。如果我们使用上图的跳跃表，就可以减少查找所需时间为O(n/2)，因为我们可以先通过每个节点的最上面的指针先进行查找，这样子就能跳过一半的节点。比如我们想查找19，首先和6比较，大于6之后，在和9进行比较，然后在和12进行比较......最后比较到21的时候，发现21大于19，说明查找的点在17和21之间，从这个过程中，我们可以看出，查找的时候跳过了3、7、12等点，因此查找的复杂度为O(n/2)。
当然上面只是最简单的就是跳跃表，真正的跳表每一个结点不单单只包含指向下一个结点的指针，可能包含很多个指向后续结点的指针，这样就可以跳过一些不必要的结点，从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针，这个过程是通过一个随机函数生成器得到，就是通过随机生成一个结点中指向后续结点的指针数目。
通过上面的跳表的很容易设计这样的数据结构：
定义每个节点类型：
|
1
2
3
4
5
6
7
8
9
|
typedef struct nodeStructure *node;typedef struct nodeStructure{ keyType key; // key值 valueType value; // value值 // 向前指针数组，根据该节点层数的 // 不同指向不同大小的数组 node forward[1]; }; |
上面的每个结构体对应着图中的每个节点，如果一个节点是一层的节点的话（如7，12等节点），那么对应的forward将指向一个只含一个元素的数组，以此类推。
定义跳表数据类型：
|
1
2
3
4
5
|
// 定义跳表数据类型typedef struct listStructure{ int level; struct nodeStructure * header;} * list; |
先不看代码先用图来描述一下Skip List构造，插入和删除的过程：
构造Skip List
1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。
插入过程
例子：插入 119， level = 2
如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4
删除 21
看到这就很清楚了，上面已经提到所谓的Skip List是每层从它的下一层按照某种规律抽出一些元素，它的操作也很简单，它的操作其实按层来操作链表，基本上是从上往下来操作。
具体的实现如下：
定义数据结构
|
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
|
//// skiplist_def.h// test//// Created by 杜国超 on 17/9/24.// Copyright © 2017年 杜国超. All rights reserved.//#ifndef skiplist_def_h#define skiplist_def_h#define MAX_LEVEL 8typedef int KeyType;typedef int ValueType;//定义节点信息数据结构template <typename K,typename V>struct NodeStructure { K key; V value; NodeStructure* forward[1];};//定义跳跃表数据结构template <typename K,typename V>struct SkipLisStructure{ int level; NodeStructure<K,V>* header;};typedef struct NodeStructure<KeyType,ValueType> NodeType;typedef struct SkipLisStructure<KeyType,ValueType> ListType;typedef NodeType* Node;typedef ListType* List;#define NEW_LEVEL_NODE(level) (Node)malloc(sizeof(NodeType) + (level) * sizeof(Node))#endif /* skiplist_def_h */ |
增删查操作实现
|
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
|
//// skiplist.h// test//// Created by 杜国超 on 17/9/24.// Copyright © 2017年 杜国超. All rights reserved.//#ifndef skiplist_h#define skiplist_h#include "skiplist_def.h"class CSkipList{public: CSkipList(); ~CSkipList();public: ValueType* Search(const KeyType& key); bool Insert(KeyType& key,ValueType& value); bool Delete(const KeyType& key,ValueType& value); void FreeList();private: int RandomLevel();private: List _skipList; int _size; }; #endif /* skiplist_h */ |
|
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
148
149
150
151
152
153
154
155
|
//// skiplist.cpp// test//// Created by 杜国超 on 17/9/24.// Copyright © 2017年 杜国超. All rights reserved.//#include "skiplist_def.h"#include "skiplist.h"#include <stdlib.h>CSkipList::CSkipList(){ _skipList = (List)malloc(sizeof(ListType)); // 设置跳表的层level，初始的层为0层（数组从0开始） _skipList->level = 0; _skipList->header = NEW_LEVEL_NODE(MAX_LEVEL); // 将header的forward数组清空 for(int i = 0; i < MAX_LEVEL; ++i) _skipList->header->forward[i] = NULL; _size = 0;}CSkipList::~CSkipList(){ FreeList();}ValueType* CSkipList::Search(const KeyType& key){ Node node = _skipList->header; Node indexNode = NULL; for(int i = _skipList->level - 1; i >= 0; --i){ while((indexNode = node->forward[i]) && (indexNode->forward[i]->key <= key)) { if (indexNode->key == key) { return &(indexNode->value); } node = indexNode; } } return NULL;}bool CSkipList::Insert(KeyType& key, ValueType& value){ Node update[MAX_LEVEL]; int i; Node node = _skipList->header; Node indexNode = NULL; //寻找key所要插入的位置 for(i = _skipList->level - 1; i >= 0; --i){ while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key)) { node = indexNode; } update[i] = node; } node = node->forward[0]; //如果key已经存在 if(node->key == key){ node->value = value; return false; }else{ //随机生成新结点的层数 int level = RandomLevel(); if(level > _skipList->level){ for (int i = _skipList->level;i < level;++i) { update[i] = _skipList->header; } _skipList->level = level; } //申请新的结点 Node newNode = NEW_LEVEL_NODE(level); newNode->key = key; newNode->value = value; //调整forward指针 for(int i = level - 1; i >= 0; --i){ node = update[i]; newNode->forward[i] = node->forward[i]; node->forward[i] = newNode; } //更新元素数目 ++_size; return true; }}bool CSkipList::Delete(const KeyType& key,ValueType& value){ Node update[MAX_LEVEL]; int i; Node node = _skipList->header; Node indexNode = NULL; //寻找key所要插入的位置 for(i = _skipList->level - 1; i >= 0; --i){ while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key)) { node = indexNode; } update[i] = node; } node = node->forward[0]; //结点不存在 if(node->key != key){ return false; }else{ value = node->value; //调整指针 for(i = 0; i < _skipList->level; ++i){ if(update[i]->forward[i] != node) break; update[i]->forward[i] = node->forward[i]; } //删除结点 free(node); for(int i = _skipList->level - 1; i >= 0; i--){ if(_skipList->header->forward[i]==NULL){ _skipList->level--; } } //更新链表元素数目 --_size; return true; } }int CSkipList::RandomLevel(){ int k = 1; while (rand()%2) { k++; } k=(k<MAX_LEVEL)?k:MAX_LEVEL; return k;}void CSkipList::FreeList(){ Node p = _skipList->header; Node q; while(p != NULL){ q = p->forward[0]; free(p); p = q; } free(p); free(_skipList); _size = 0;} |
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对服务器之家的支持。
原文链接：http://blog.csdn.net/D_Guco/article/details/78004991
