数据结构-----跳表

本文转载自博客：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的析构函数中），然后释放它自己。

完整代码下载
--------------------- 

本文地址：https://blog.csdn.net/woaitingting1985/article/details/85986748