---

前言

skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。

跳表是什么

其实光从概念来说，跳表可能并不难理解，跳表相当于是单链表的基础上，向上增加索引的方式，让我们查找数据的时候能够类似用一个二分查找的方式查找，但实际上建立上面的索引过后，新插入和删除节点会破坏上下两层1：2的关系，也就是说，倘若你在第一层的索引：第二层的索引是1：2，并且后面的n:n+1也都保持这样的关系，那么查找的时候是能够保持logN的效率，但是插入和删除就会破坏这里的结构。

怎么解决上述问题呢？
skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数。即不需要调节其他节点的层数。

换句话讲，就是一个节点最多有多少层，上层的索引最高多少，在一开始就已经确定好了。当我们需要插入删除操作的时候，只需要找到插入位置前后节点，改变链接关系即可。

这是一种大胆的处理，是因为每次插入的时候跳表里的数据存储的位置，层数都可能发生变化，并且他也有可能出现前面部分都是低矮层数，后面都是高层次的节点，从而降低了效率。

随即层数的理解

其中节点随机层数，其实随即层数也是有讲究的，随即过后每一层的节点数其实是相对固定的，随即层数的函数会保证上一层的节点数：下一层的节点数是1：2。
当p设置的小，层数就会低一点，像redis通常设置为0.25。

跳表通常需要有一个最大层数maxLevel，以及一个概率p，即新增加一层的概率。通常数据量够大，就会呈现出一定的比率。

当p是0.25，那么只有产生一层的概率就是1-p（0.75），产生第二层的概率就是（1-p） * p。三层（1-p）pp…
因此，一个节点的平均层数（也即包含的平均指针数目），计算如下

设计一个跳表

1206. 设计跳表

#pragma once
#include
using namespace std;
#include
#include 
#include 
#include 
class Skiplist {
public:
    struct Node
    {
        vector<Node*> _skiplist;
        int _level;
        int _val;
        Node(int level, int val)
            :_skiplist(level, nullptr)
            , _level(level)
            , _val(val)
        {}
    };

    Skiplist() {
        srand(0);
        //头节点默认只有0层，即最底层
        _root = new Node(1, -1);
    }

    bool search(int target) {
        //查找一个元素的时候
        //指针指向的比key值小的话，往右，其他情况往下
        Node* cur = _root;
        int level = cur->_level - 1;
        //从最上层开始往下遍历
        while (level >= 0)
        {
            if (cur->_skiplist[level] && cur->_skiplist[level]->_val < target)
            {
                //往右边走
                cur = cur->_skiplist[level];
            }
            else if (cur->_skiplist[level] && cur->_skiplist[level]->_val == target)
            {
                //此时查找的值就在右边
                return true;
            }
            else
            {
                //其他情况都是往下走，最终会从下面越界
                level--;
            }
        }
        return false;
    }

    //由于前后链接的时是需要整个Node占一个数组的位置
    vector<Node*> Find(int target, int level)
    {
        if (_root->_level < level)
        {
            //超过level的置成nullptr
            _root->_skiplist.resize(level, nullptr);
            _root->_level = level;
        }
        //level层，并且每一个插入元素的前一个位置的指针
        vector<Node*> preNode(level, nullptr);
        level--;//从索引处开始
        Node* cur = _root;//实际上cur是工具人
        while (level >= 0)
        {
            if (cur->_skiplist[level] && cur->_skiplist[level]->_val < target)
            {
                //往右边走
                cur = cur->_skiplist[level];
            }
            else
            {
                //往下走之前实际上右边就是我们要插入的点
                preNode[level] = cur;

                level--;
            }
        }
        return preNode;
    }

    void add(int num) {
        //先会创建num的节点
        //Random函数创建这个随机的层数
        int level = Random();
        //if(num == 0)
        //{
        //    level = 1;
        //}
        //else
        //{
        //    level = 5;
        //}
        Node* newNode = new Node(level, num);
        vector<Node*> preNode = Find(num, level);

        //此时将节点的前节点和后节点分别连接起来.
        //注意：先链接newNode的_skiplist节点
        for (int i = 0; i < level; ++i)
        {
            newNode->_skiplist[i] = preNode[i]->_skiplist[i];
            preNode[i]->_skiplist[i] = newNode;
        }
    }

    int Random()
    {
        int level = 1;//最低从第一层开始
        if (rand() < _p * RAND_MAX && level < _maxLevel)
        {
            level++;
        }
        return level;
    }
    /*int Random()
    {
        static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
        static std::uniform_real_distribution distribution(0.0, 1.0);

        size_t level = 1;
        while (distribution(generator) <= _p && level < _maxLevel)
        {
            ++level;
        }

        return level;
    }*/

    bool erase(int num) {
        int level = _root->_level;
        vector<Node*> preNode = Find(num, level);
        //若找不到，就是删除失败
        Node* del = preNode[0]->_skiplist[0];
        if (del == nullptr || del->_val != num)
            return false;

        int delLevel = del->_level;
        delLevel--;//索引处开始删
        while (delLevel >= 0)
        {
            preNode[delLevel]->_skiplist[delLevel] = del->_skiplist[delLevel];
            delLevel--;
        }

        delete del;
        //erase节点的时候还可以优化，删掉头顶若干层
        int index = _root->_level - 1;
        while (index >= 0)
        {
            if (!_root->_skiplist[index])
            {
                index--;
            }
            else
            {
                break;
            }
        }
        if (index != _root->_level - 1)
        {
            //说明上面几层可以不要
            _root->_skiplist.resize(index+1);
            _root->_level = index + 1;
        }
        return true;
    }
private:
    int _maxLevel = 32;
    double _p = 0.7;
    Node* _root = nullptr;
};

void test()
{
    Skiplist skiplist;
    skiplist.add(0);
    skiplist.add(5);
    int x; 
    cin >> x;
    skiplist.erase(x);
}
/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

复杂度考量

skiplist跟平衡搜索树和哈希表的对比

1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差
   不多。

• skiplist的优势是：
• a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
• b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。
• skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包
  含的平均指针数目为1.33；

2. skiplist相比哈希表而言，就没有那么大的优势了。

• 哈希表平均时间复杂度是O(1)，比skiplist快。
• 哈希表空间消耗略多一点。
• skiplist优势如下：
• a、遍历数据有序
• b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
• c、哈希表扩容有性能损耗。
• d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。