1. 跳表

遍历一遍链表时间复杂度为O(N)

如果每相邻两个节点上高一层，增加一个节点，让指针指向下一个节点。这样所有的新增指针又会组成一个新的链表，但包含的节点的个数只有原来的一半，遍历链表的速度也会提高一半。以此类推后分成多层

跳表查找的过程

eg：查找节点17过程如下：

1. 17比节点9大，所以直接通过最上层指针跳跃到节点9。
2. 17节点比节点21小，向下查找节点，正好找到17节点，找到17节点。
3. 如果找到NULL说明已经查找完毕或者没有下一层，说明没有找到。

这种思想类似于二分查找，每次查找都会排除一般的节点。时间复杂度为O(logN)

跳表的插入与删除优化处理

为了保证这种跳表结构，插入与删除需要进行特殊操作。这里不在要求严格的格式匹配，在插入节点时候随机出一个层数，这样每次插入和删除都不需要考虑其他节点的层数，方便处理。(每个节点有几层个数不确定)

同时，为了保证效率

1. 每个节点的随机层数有最大的层数。
2. 其次，还要抽象出一种概率，让每个节点的层数分布合理

设多一层的概率为p
节点层数至少为1。而大于1的节点层数，满足一个概率分布。
节点层数恰好等于1的概率为1-p。
节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
节点层数大于等于3的概率为p ^ 2，而节点层数恰好等于3的概率为p ^ 2×(1-p)。节点层数大于等于4的概率为p ^ 3，而节点层数恰好等于4的概率为p^3×(1-p)。

层数越高，概率越低。

一个节点的平均层数的公式为：

跳表的平均时间复杂度为O(logN)

具体时间复杂度的分析，相关参考文章：

1. 铁蕾的博客
2. William_Pugh的论文

2. C++实现跳表

力扣链接

#pragma once

#include
#include
#include
#include 

struct SkiplistNode {
    int val;
    std::vector<SkiplistNode*>_nextV;//节点有多少层
    SkiplistNode(int _val, int leve)
        :val(_val), _nextV(leve, nullptr)
    {}
};

class Skiplist {
    typedef SkiplistNode Node;
private:
    Node* _head;//头节点
    size_t _maxleve = 32;//每个节点最大的层数
    double _p = 0.25;//设每个节点多一层的概率为p

    int _randomLeve() {
        //产生节点的随机层数
        int leve = 1;
        while (rand() < (RAND_MAX * _p) && leve < _maxleve) {
            //rand()<(RAND_MAX*_p的概率为0.25
            leve += 1;
        }
        return leve;
    }

    //查找某个节点的所有前一个指针
    std::vector<Node*>_findPrevNode(int num) {
        //首先要查找插入的位置，前一个节点指针
        Node* cur = _head;
        int curleve = cur->_nextV.size() - 1;
        std::vector<Node*>prev(curleve + 1, _head);//保存前一个节点的指针
        while (curleve >= 0) {//如果还没有找到节点的最后一层时都要继续循环
            //节点向下移动时，更新前一个节点指针数组
            if (cur->_nextV[curleve] && cur->_nextV[curleve]->val < num) {
                //跳表向右走，跳到下一个节点
                //特殊情况，下一个节点为空时，要向跳表也要向下移动
                cur = cur->_nextV[curleve];
            }
            else if (cur->_nextV[curleve] == nullptr || cur->_nextV[curleve]->val >= num) {
                //更新prev数组，跳表向下走
                prev[curleve] = cur;
                curleve -= 1;
            }
        }
        return prev;
    }
public:
    Skiplist() {
        //头节点值为-1,开始为第一层
        _head = new Node(-1, 1);
        srand(time(0));//随机数种子
    }

    bool search(int target) {
        Node* cur = _head;
        int curleve = cur->_nextV.size() - 1;
        while (curleve >= 0) {//如果还没有找到节点的最后一层时都要继续循环
            if (cur->_nextV[curleve] && cur->_nextV[curleve]->val < target) {
                //跳表向右走，跳到下一个节点
                //特殊情况，下一个节点为空时，要向跳表也要向下移动
                cur = cur->_nextV[curleve];
            }
            else if (cur->_nextV[curleve] == nullptr || cur->_nextV[curleve]->val > target) {
                //跳表向下走
                curleve -= 1;
            }
            else {
                //找到了这个节点
                return true;
            }
        }
        return false;
    }

    void add(int num) {
        //添加数据时可以冗余
        std::vector<Node*>prev = _findPrevNode(num);
        int newLeve = _randomLeve();
        Node* newNode = new Node(num, newLeve);
        //如果newLeve超过头节点的最大层数，则选择升高head层数
        if (newLeve > _head->_nextV.size()) {
            _head->_nextV.resize(newLeve);//避免新增节点导致头节点层数不足
            prev.resize(newLeve, _head);//多余的层数指向头节点。
        }

        //连接前后节点
        for (size_t i = 0; i < newLeve; i++) {
            newNode->_nextV[i] = prev[i]->_nextV[i];
            prev[i]->_nextV[i] = newNode;
        }
    }

    //测试打印每一层跳表
    void _Print() {
        int leve = _head->_nextV.size();
        for (int i = leve - 1; i >= 0; i--) {
            Node* cur = _head;
            //打印每一层的链表
            while (cur != nullptr) {
                std::cout << cur->val << "->";
                cur = cur->_nextV[i];
            }
            std::cout << "nullptr" << std::endl;
        }
    }

    bool erase(int num) {
        //删除节点，找到到节点的前一个指针，在把要删除节点的所有下一个指针连接起来
        std::vector<Node*>prev = _findPrevNode(num);
        if (prev[0]->_nextV[0] == nullptr || prev[0]->_nextV[0]->val != num) {
            //跳表最下层都找不到这个节点，说明找不到节点
            return false;
        }
        //找到了对应节点
        Node* del = prev[0]->_nextV[0];
        for (size_t i = 0; i < del->_nextV.size(); i++) {
            //连接del节点的每一层前后指针
            prev[i]->_nextV[i] = del->_nextV[i];
        }
        delete del;

        //如果删除可以减少跳表的高度，提高搜索效率
        int _headLeve = _head->_nextV.size() - 1;
        while (_headLeve >= 0) {
            if (_head->_nextV[_headLeve] == nullptr) {
                _headLeve -= 1;
            }
            else {
                break;
            }
        }
        _head->_nextV.resize(_headLeve + 1);
        return true;
    }
};

/**
 * 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

测试代码：

#include"StopWatch.h"

void TestAdd() {
	Skiplist sp;
	int arr[] = { 1,2,3,4 };
	for (auto num : arr) {
		sp.add(num);
	}
	//sp.search(0);
	sp._Print();
	for (auto num : arr) {
		sp.erase(num);
	}
}

int main() {
	TestAdd();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果：

3. 跳表与哈希表，红黑树对比

跳表与红黑树对比：
相同点：

1. 在遍历时都可以做到让数据有序遍历。
2. 平均时间复杂度相差不多O(logN)

不同点：

1. 跳表实现简单，比较容易控制，红黑树与平衡树增删查改遍历更加复杂
2. 跳表结构所需要的额外空间相比与红黑树，平衡树更小。因为红黑树,平衡树需要储存颜色，平衡因子等
3. 红黑树，AVL树更加稳定

跳表与哈希表对比：

不同点：

1. 如果哈希冲突不严重，哈希表查找比跳表更快O(1)
2. 哈希表空间使用比跳表大
3. 哈希表扩容有性能消耗。