高阶数据结构学习之跳表

1相关概念

1. 假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图b所示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半。

2. 以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图c，这样搜索效率就进一步提高了。

3. skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。
   

4. skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了。细节过程入下图：

平均时间复杂度O(logN)

插入节点的关键是找到这个位置的前一个节点

2相关题目

1206. 设计跳表链接

链接: 1206. 设计跳表

描述

代码

struct SkiplistNode
{
	int _val;
	vector<SkiplistNode*> _nextV;
	SkiplistNode(int val, int level)
		:_val(val)
		, _nextV(level, nullptr)
	{}
};

class Skiplist {
    typedef SkiplistNode Node;
public:
    Skiplist() {
        srand(time(0));
        _head=new SkiplistNode(-1,0);
    }
    
	bool search(int target) {
		Node* cur = _head;
		int level = _head->_nextV.size() - 1;
		while (level >= 0)
		{
			// 目标值比下一个节点值要大，向右走
			// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
			if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
			{
				// 向右走
				cur = cur->_nextV[level];
			}
			else if (cur->_nextV[level] == nullptr || cur->_nextV[level] -> _val > target)
			{
				// 向下走
				--level;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

    vector<Node*> FindPrevNode(int num)
	{
		Node* cur = _head;
		int level = _head->_nextV.size() - 1;
		// 插入位置每一层前一个节点指针
		vector<Node*> prevV(level + 1, _head);
		while (level >= 0)
		{
			// 目标值比下一个节点值要大，向右走
			// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
			if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
			{
				// 向右走
				cur = cur->_nextV[level];
			}
			else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
			{
				// 更新level层前一个
				prevV[level] = cur;
				// 向下走
				--level;
			}
		}
		return prevV;
	}
    
    void add(int num) {
		vector<Node*> prevV = FindPrevNode(num);
		int n = RandomLevel();
		Node* newnode = new Node(num, n);
		// 如果n超过当前最大的层数，那就升高一下_head的层数
		if (n > _head->_nextV.size())
		{
			_head->_nextV.resize(n, nullptr);
			prevV.resize(n, _head);
		}
		// 链接前后节点
		for (size_t i = 0; i < n; ++i)
		{
			newnode->_nextV[i] = prevV[i]->_nextV[i];
			prevV[i]->_nextV[i] = newnode;
		}
	}
    
    bool erase(int num) {
		vector<Node*> prevV = FindPrevNode(num);
		// 第一层下一个不是val，val不在表中
		if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val !=num)
		{
			return false;
		}
		else
		{
			Node* del = prevV[0]->_nextV[0];
			// del节点每一层的前后指针链接起来
			for (size_t i = 0; i < del->_nextV.size(); i++)
			{
				prevV[i]->_nextV[i] = del->_nextV[i];
			}
			delete del;
			// 如果删除最高层节点，把头节点的层数也降一下
			int i = _head->_nextV.size() - 1;
			while (i >= 0)
			{
				if (_head->_nextV[i] == nullptr)
					--i;
				else
					break;
			}
			_head->_nextV.resize(i + 1);
			return true;
		}
	}

    //随机生成节点层数
    int RandomLevel()
    {
        size_t level=1;
        while(rand()<RAND_MAX*_p && level<_maxLevel)
        {
            ++level;
        }
        return level;
    }
private:
    Node* _head;
    size_t _maxLevel=32;
    double _p=0.25;
};

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

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

1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。
   skiplist的优势是：
   a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
   b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33；
2. skiplist相比哈希表而言，就没有那么大的优势了。
   相比而言a、哈希表平均时间复杂度是O(1)，比skiplist快。
   b、哈希表空间消耗略多一点。
   skiplist优势如下：
   a、遍历数据有序
   b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
   c、哈希表扩容有性能损耗。
   d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力