数据结构-----跳表

本文转载自博客：https://blog.csdn.net/sinat_35261315/article/details/62890796

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

链表
同数组比较，链表的插入删除操作复杂度是O(1)，然而如果想要查找一个节点，你可能会这么写：

LinkedNode<T> *targetNode = headerNode;
while(targetNode)
{
if(targetNode->element == theElement)
return targetNode;
targetNode = targetNode->next;
}
return NULL;
1
2
3
4
5
6
7
8
你会发现每次都是从链表头节点开始，时间复杂度是n（节点个数）。为了提高算法速度，就有了跳表的概念。

二分法
介绍跳表之前，先简单解释一下二分法。
对于一个有序序列来说，通常在查找某一个元素时，可以不需要从头到尾一个个比较，而是使用二分的方式，步骤如下：
1.先将中间的元素和待查找元素比较。
2.1：如果相等，返回
2.2：如果中间元素小于待查找元素，在右侧部分中查找（返回步骤1）
2.3：如果中间元素大于待查找元素，在左侧部分中查找（返回步骤1）

跳表
结合链表和二分法的特点，将链表进行加工，创造一个二者的结合体：
1.链表从头节点到尾节点是有序的
2.可以进行跳跃查找（形如二分法）

next数组
实现第一步，只需在插入的时候进行有序插入即可，核心步骤在第二步，构建一个可以实现在节点之间跳跃的链。
对于普通链表而言，你的节点也许会长这个样子（或者再多个构造析构函数？）:

template<class T>
class linkedNode
{
public:
T element;
linkedNode<T> *next;
};
1
2
3
4
5
6
7
这里的next指针是我们用于将此节点同后面一个节点连接的桥梁，正如你知道的那样，next是下一个节点的指针。
需要你考虑的事情来了，如果需要在不挨着的节点之间实现跳转，那么对于某一个节点来说，它就需要存储一个以上的指向别的节点的next指针。多个同种类型的数据通常可以采用数组存储（vector, list等STL容器也可以啦），这样，我们的跳表节点或许大概差不多应该长这个样子：

template<class T>
class skipNode
{
public:
T element;
skipNode<T> **next; //一个存储着skipNode<T>*类型变量的一维数组
};
1
2
3
4
5
6
7
暂且不论next数组的大小是多少，先让我告诉你跳表的样子。

你可能会觉得跳表这个东西很奇怪，不过最好不是因为我画的比较丑。先不管竖着的线是什么，横着看每一层好像都是一个链表，对吗。另外我觉得你也应该注意一下竖着看的时候每一个节点的名字，它们也都是一样的（不用考虑为什么有的节点有一个，有的有两个甚至更多，这是插入函数应该解决的问题）。

所以我想你现在脑子中可能有了对next数组的一种假设，尽管事实可能并不是你想的那样，不过不要紧，让我借着这张图告诉你next数组是什么。

通常我们会定义跳表的级数，简单来解释，就是层数-1（最下面一级是0级）。所以这张图表示的跳表的级数是（0， 1， 2）。而在第2级的节点（比如node5)，它的next数组大小就是(2 + 1) == 3，在第1级的节点（比如node4），它的next数组的大小就是（1 + 1） == 2，在第0级的节点（比如node3），它的next数组大小是1；

所以在申请一个skipNode的指针时，传入这个节点所在的级数好像是理所应当的事情，然后对next进行初始化，把skipNode加工一下，像这样：

template<class T>
class skipNode<T>
{
public:
skipNode(const T& theElement, size_t size):
element(theElement)
{
next = new skipNode<T>*[size+1];
}

T element;
skipNode<T> **next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
现在开始解释next数组，你最好看着上面的图：
对于第2级的node5来说

node5->next[2] == tailNode;
node5->next[1] == node7;
node5->next[0] == node6;
1
2
3
对于第1级的node2来说

node2->next[1] == node4;
node2->next[0] == node3;
1
2
如果你还是不理解，我想你可以把每一列的同名节点看成是不同的节点，它们存的element数据是一样的，而且每个节点只有一个指向下一个节点的指针。再把每一层看成一个链表。然后再看一遍。最后把每一列合成一个节点，它们只是有一个指针数组而已，你应该这么想。

find
我觉得这个函数可以帮助你更好地理解next数组的作用。如果没有，唔，怪我表达能力太弱。。。

继续看着这张图，让我先解释一下headerNode和tailNode是什么（如果你因为它们的存在感到一丝困惑的话），它们是设计者（就是我们啦）人为添加的两端节点，很像存在头节点和尾节点的链表（又或者像队列？），它们不存储需要保存的有用的数据，但是需要人为给定一个数，让它比整个跳表中的element都大，仅仅是用来判断是否是头和尾。当跳表为空时，级数为0，headerNode->next[0] == tailNode;

现在回到上面那个图片上，如果我想要查找node6，想想二分法（但不是从中间开始）。
假设targetNode记录着此时的节点，初值赋为headerNode；

第一次你应该比较的是headerNode->next[2]->element和theElement（待查找数据），也就是node5->element和theElement。显然node5小于theElement（别忘了跳表的数据也是有序的），这一步的结果导致下一次应该从第2级的node5开始查询。也就是令targetNode = targetNode->next[2];

第二次你应该比较targetNode->next[2]->element和theElement，也就是tailNode->element和theElement。看看前面，tailNode->element是最大的，对吗。所以结果是大于，这一步的结果导致下一次应该从第1级的node5开始查询。这里从第2级跳到第1级。但是没有改变targetNode。

第三次你应该比较targetNode->next[1]->element和theElement，也就是node7->element和theElement。显然也是大于，这一步的结果导致下一次应该从第0级的node5开始查询。这里从第1级跳到第0级。也没有改变targetNode。

第四次你应该比较targetNode->next[0]->element和theElement，也就是node6->element和theElement。这时你应该庆幸终于相等了，此时结束。如果小于，改变targetNode = targetNode->next[0]（像第一步那样），如果大于，结束，不然还往哪一级降，没了，对吗。

没懂？接着看：
比较的时候的三种情况，以targetNode->next[i]->element和theElement为例：
1.小于：令targetNode = targetNode->next[i]; //第i级链表的下一个
2.大于：向下降级，i- - //不改变targetNode
3.等于：向下降级，i- - //不改变targetNode

退出后，再次比较targetNode->next[0]和theElement，判断是否找到。
所以整个运算下来，targetNode是要查找的节点前面那个节点。如果你不明白，想想找不到那个节点时的情况，比如说，额，查找node6.6。
让我们看看代码：

template<class K, class E>
pair<const K, E> *skipNode<K, E>::find(const K& theKey)
{
skipNode<K, E>* beforeNode = headerNode;
for(int i = curLevels; i >= 0; --i) //降级
{
while(beforeNode->next[i]->element.first < theKey)
beforeNode = beforeNode->next[i]; //跳转到同一级的下一个
}
//跳出存在两种可能
//1.找到了，此时 if(beforeNode->next[0]->element.first == theKey)
//2.没找到，此时 if(beforeNode->next[0]->element.first > theKey)
if(beforeNode->next[0]->element.first == theElement.first)
return &beforeNode->next[0]->element;
return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
insert
像红黑树，AVL树一样，跳表也是一种平衡结构，只不过这种平衡结构是利用随机函数产生的级数维持的（终于填了前面的坑，还记得吗，为什么有的节点有2级，有的只有0级）。

接着上面那个图，想想插入node6.6的过程中会发生什么（假设随机函数给它分配的是第2级）。。。静思一秒钟。
啊！插入之后会破坏每一级的结构，会破坏哪些节点的结构呢。。。静思一秒钟。
啊！自然是第2级的node5，第1级的node5，第0级的node6这些节点的next数组。

分析过后，第一步便是找到这几个节点。我觉得你应该停一下想想怎么找，实在想不出来，参考find函数。
find函数中，for循环内套while循环，想想每次while循环结束之后的beforeNode是什么。哇哦，它就是我们要找的节点。我们用一个last数组记录这些节点，last[i]表示第i级要找的节点。

第二步：利用随机函数分配级数level
找节点是为了改变这些节点的next数组，分配级数是为了只改变找到的那些节点中位于第0级到第level级的节点。啊！你又想了，万一随机出的level比目前最大级数还大怎么办。这时就将跳表增加一级呗，像这样：

int level = levels();
if(level > curLevels)
{
level = ++curLevels;
last->next[level] = heaerNode;
//增加一级的同时也要改变last数组
//用于将新节点插入时newNode->next[level] = last[level]->next[level]
}
1
2
3
4
5
6
7
8
万事俱备后，开始更新涉及到的节点的next数组，看代码之前，先想想怎么在链表中插入节点。

skipNode<K,E> *newNode = new skipNode<K, E>(thePair, level+1);

//因为只影响了[0, level]级的节点，更高级的节点不受影响
for(int i = 0; i <= level; ++i)
{
//每一级都插入新节点
newNode->next[i] = last[i]->next[i];
last[i]->next[i] = newNode;
}
1
2
3
4
5
6
7
8
9
总结一下插入函数，需要两个额外的函数：
1.随机函数，用于生成新节点的级数
2.初始化last数组，保存每一级中处在待插入位置前面的节点

//随机函数，为新节点生成级数
template<class K, class E>
int skipList<K, E>::levels()
{
int level = 0;
//cutOff预先设定的值,cutOff = prob * MAX_RAND;
//prob:是第i级同时又是第i-1级的概率，人为设定
while(rand() > cutOff)
level++;
return level;
}

template<class K, class E>
skipNode<K, E>* skipList<K, E>::search(const K& theKey)
{
//与find函数相同
skipNode<K, E>* beforeNode = headerNode;
for(int i = curLevels; i >= 0; --i)
{
while(beforeNode->next[i]->element.first < theKey)
beforeNode = beforeNode->next[i];
last[i] = beforeNode; //找到每一级待插入位置前面的节点
}

//返回找到的节点，用于判断是否已存在键为theKey的节点
return beforeNode->next[0];
}

template<class K, class E>
void skipList<K, E>::insert(const pair<const K, E>& thePair)
{
if(thePair.first >= tailNode->element.first)
return;

skipNode<K, E> *theNode = search(thePair.first);
if(theNode->element.first == thePair.first) //判断是否存在该节点
{
theNode->element.second = thePair.second; //更新值
return;
}

int level = levels();
//cutLevels：记录当前最大级数
if(level > curLevels)
{
level = ++curLevels; //级数加一,让新节点作为最高级节点
last[level] = headerNode;
}

//每一级如同链表插入一样进行插入
skipNode<K, E> *newNode = new skipNode<K, E>(thePair, level+1);
for(int i = 0; i <= level; ++i)
{
newNode->next[i] = last[i]->next[i];
last[i]->next[i] = newNode;
}
dSize++;
}
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
erase
如果你理解了插入函数，删除函数会带给你从未有过的轻松感，至少比起还在文章开头徘徊的你是这样。噢对，还有一件事，或许你应该在回忆链表删除的状态里待几秒钟。如果没有头绪，插入函数最后一个for循环说不定会帮到你。

要删除一个节点，自然是先找到这个节点啦，同时还要初始化last数组啦。然后从第0级开始到最高级，如果last[i]->next[i]是要删除的节点，就删除掉。直接上代码：

template<class K, class E>
void skipList<K, E>::erase(const K& theKey)
{
if(theKey >= tailNode->first)
return;

skipNode<K, E> *theNode = search(theKey);
if(theNode->element.first != theKey)
return; //不存在要删除的节点

int i = 0;
while(i <= curLevels && last[i]->next[i] == theNode)
{
//每一级的链表删除
last[i]->next[i] = theNode->next[i];
i++;
}

//如果删除的是最高级，且未删除前，最高级就一个节点，则当前节点减一
while(last[curLevels]->next[curLevels] == tailNode)
curLevels--;

delete theNode;
dSize--;
}
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
现在唯一可能会让你感到头疼的就是构造函数了。想想构造函数应该做些什么，对数据成员进行初始化？啊，对，那是所有构造函数应该做的事情。我说的是具体应该怎么做。
我猜你看上述代码的时候会对像cutOff, curLevels这些凭空出现的变量有点不理解，没关系，正如你想的那样，把它们放到private数据成员里。总结一下让你感到困惑的变量：

int dSize; //记录着跳表中节点的个数，初始为0
int curLevels; //记录跳表当前最大级数，如果是图片那样的话，它的值是2
int cutOff; //用于随机函数的随机算法，一个很大的值
int maxLevel; //跳表可以存储的最大级数
skipNode<K, E> *heaerNode; //跳表头节点，键是跳表中最大的
skipNode<K, E> *tailNode; //尾节点，键同headerNode
skipNode<K, E> **last; //记录每一级中要查找的节点前面那个节点
1
2
3
4
5
6
7
8
构造函数首先初始化这些变量，然后给节点申请内存，将头节点和尾节点连接起来（因为此时跳表是空的）。就这么简单。

//prob: 是第i级同时又是第i-1级的概率
//maxPairs: 跳表可以存储的最多节点个数
//largetKey: 最大键
template<class K, class E>
skipList<K, E>::skipList(K largerKey, int maxPairs, double prob):
cutOff(prob * RAND_MAX),
maxLevel((int)ceil(logf((float)maxPairs) / logf(1 / prob)) - 1),
cutLevels(0),
dSize(0)
{
pair<K, E> tailPair;
tailPair.first = largerKey;
headerNode = new skipNode<K, E>(tailPair, maxLevel+1);
tailNode = new skipNode<K, E>(tailPair, 0);
last = new skipNode<K, E>*[maxLevel+1];

for(int i = 0; i <= maxLevel; ++i)
{
headerNode->next[i] = tailNode;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
析构函数就没什么了，对第0级的每一个节点，释放它的next数组（可以写在skipNode的析构函数中），然后释放它自己。