数据结构与算法详解——跳表篇（附c++实现代码）

- 跳表
- 时间复杂度分析
- 空间复杂度分析
- 插入、删除
- 索引更新
- 代码实现
- - 类定义
  - 查找
  - 随机函数
  - 插入
  - 删除
  - 完整代码

跳表

前面我们说到链表，链表的查找的时间复杂度是O(n)，比较慢，插入和删除操作是O(1)，但是实际上插入和删除都需要先遍历查找到插入和删除的位置。跳表就是在有序链表的基础上添加索引，使得有序链表的查找效率提高。
假设现在有一个16个结点的有序链表，存储1-16整型数字，现在我们需要查找值为12这个结点需要遍历12个结点。

现在我们为链表建立一层索引，假设每两个结点就建立一个索引：

现在我们查找值为12的结点，先从第一级索引中查找，找到结点11，结点11的下一个结点是13，那么12肯定在结点11和结点13之间，然后我们下降1层到有序链表，从结点11开始往后找，发现结点11的下一个结点就是结点12，这里我们遍历了7个结点。
继续建立第二层索引，在第一级索引的基础上每两个结点建立一个索引：

现在查找值为12的结点只需要遍历5个结点（第二级索引找到结点9，第一级索引找到结点11，有序链表找到结点12）。
接着建立第三层索引，查找值为12的结点只需要遍历4个结点，这里第三级索引只有两个结点了，不需要再建立多一层索引了，只有一个结点的索引建立了也没啥意义。

像上面这种为有序链表建立多层索引的数据结构就是跳表。

时间复杂度分析

假设有序链表有n个结点，按照我们上面两个结点建立一个索引，那么第一级索引有n/2个结点，第二级索引有n/4个结点，第h级索引就有n/(2^h)个结点，这个很好理解，这层的结点数是下一层结点数的1/2。
现在假设最高层索引就是第h层索引，有两个结点，我们可以得到：n/(2^h)=2，得到h=log2(n/2)=log2(n)-1，跳表的高度就可以求出来了。现在假设每一层都要遍历x个结点，时间复杂度就是O(m*h)=O(m*log2(n))（常数项忽略掉）。
按照前面的索引结构，我们可以知道每一层索引最多只需要遍历3个结点。为什么？
我们查找的思路是这样：从最高层索引开始查找，找到最后一个小于等于目标结点值的结点（也就是说这个结点的下一个结点值大于目标值，刚好目标值夹在这个结点和这个结点的下一个结点之间），然后跳到下一层，也是同样的逻辑直到在有序列表中找到这个结点。假设目标结点值为target，最后一个小于等于目标结点值的结点为now，now的下一个结点为next，那么now<=target 其实仔细看，最高层的索引的第二个结点是不是基本落在有序链表中间的位置？下一层是不是有序列表按1/4分割？看到这个有没有想起二分查找，其实跳表就是实现了类似二分查找的有序链表的数据结构。

空间复杂度分析

其实跳表就是用了空间换时间，将有序列表的查找性能从O(n)提升到O(logn)。那么跳表额外用了多少空间呢？
根据前面的分析，我们知道从1-h层索引的结点数是一个公比为1/2的等比数列：

n*(1/2)，n*(1/2)^2 ....  n*(1/2)^h，其中n*(1/2)^h=2

&emsp等比数列求和S=(n/2)(1-(1/2)^h)/(1-1/2)=n-2，所以空间复杂度是O(n)，也就是说要把一个含有n个结点的链表变成跳表，就要额外消耗n个结点的内存，总共耗费2n个结点的内存。
我们这里是每两个结点抽出一个索引结点，那如果是每3个结点抽出一个索引结点呢？得到的空间复杂度大概是O(n/2)=O(n)，虽然都是O(n)，但是实际额外消耗的结点可能只需要一半，但是查找的效率也会降低一点。

插入、删除

注意这里是有序链表，插入和删除需要先查找到插入删除的位置，时间复杂度是O(logn)，再在有序链表上执行插入删除操作，时间复杂度是O(1)。
但是插入删除只更新最下层的有序链表的话是不行的，因为当插入的元素过多地集中在某两个索引结点之间时，跳表可能会退化成链表。删除了有序链表里的元素时，索引也要对应删除，不然在索引找到某个元素，有序链表里没有。
所以在插入删除时，需要进行索引的更新。

索引更新

我们以每两个结点抽出一个索引结点的规则为例，我们在实际中如果要严格按照这种规则更新索引其实成本是相当高的，有可能因为插入一个结点，使得所有索引都要重建，这显然是不合理的。举个例子，就在文章一开始介绍跳表那个图中插入值为0的结点，是不是所有的索引都要改变？
实际中，我们是使用随机函数来决定结点插入哪几层索引。这里假设插入结点0，随机函数生成2，那么就将结点0插入到有序链表还有第1、2级索引中：

我们在一开始建立整个跳表时，也可以像插入一样使用随机函数进行建立，而不是按照每两个结点抽出一个索引结点的方法，这样子会更加容易实现。
那么这个随机函数的选取就很重要了，理论上讲有100%的数据在第0层（有序链表），有50%的数据在第1层，有25%的数据在第2层，以此类推；所以这个函数应该有： 50%的几率返回1，25%的几率返回2，以此类推。

代码实现类定义

const int MAX_LEVEL = 16;
template 
class skipList {
private:
	struct Node {
		T data;
		int level=0;
		Node* nextNode[MAX_LEVEL];		//node.nextNode[i]表示node在第i层的下一个结点
		Node(){
			for (int i = 0; i < MAX_LEVEL; i++)
				nextNode[i] = nullptr;
		}
		Node(T data, int level):Node() {
			this->data = data;
			this->level = level;
		}
	};

private:
	int max_level=1;	//当前最高的层数
	float probability=0.5;
	Node* head = new Node();	//所有层的哨兵
public:
	skipList(){}
	skipList(std::initializer_list init);
	~skipList();
	Node* find(T value);
	void insert(int value);
	void remove(int value);
	void print();
private:
	int randomLevel();
};

先来看看Node的设计，其实索引和有序链表用的是一个结点，看上面图里面结点1有4个，这里我们用的是同一个结点，但是我们在结点里定义了一个nextNode数组，存储Node指针，这个nextNode数组是跳表实现的关键，我在注释里也写了nextNode数组的含义：node.nextNode[i]表示node在第i层的下一个结点。
举个例子，还是上面的图，我们关注结点1这个Node，结点1的nextNode[3]表示结点1在第三层的下一个结点，即结点1的nextNode[3]指向结点9，结点1的nextNode[2]指向结点5，结点1的nextNode[1]指向结点3，结点1的nextNode[0]指向结点2。
注意这里我们把有序链表规定为第0层。
类里的head也是一个哨兵，注意不仅是第0层的哨兵，是所有层的哨兵，在Node的无参构造函数里，我们为head的nextNode数组的每个元素初始化为nullptr。

查找

template 
typename skipList::Node* skipList::find(T value) {		//注意skipList::Node前要加typename
	Node* cur = head;
	for (int i = max_level - 1; i >= 0; i--) {
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
	}
	if (cur->nextNode[0] != nullptr && cur->nextNode[0]->data == value) {
		return cur->nextNode[0];
	}
	else {
		std::cout << "find failed: cant find Node->data == "< 
  我们从最高层开始查找，也是按照前文提到的思路：找到该层最后一个小于等于目标结点值的结点，然后跳到下一层，直到在第0层找到目标值value。
   这里需要注意的是，跳表是支持按区间查找数据的，例如查找值在[3,20]之间的数据，我们可以先查找到结点3，然后在有序链表中往后遍历就可以了。 
随机函数 
template 
int skipList::randomLevel() {
	int level = 1;
	const unsigned int seed =std::chrono::system_clock::now().time_since_epoch().count();	//获取系统时间戳，单位微秒(microsecond)。
	std::default_random_engine generator(seed);	//系统时间戳作为种子
	std::uniform_real_distribution distribution(0, 1);	
	float random_num = distribution(generator);	//均匀分布，生成区间[0,1]的浮点数
	while (random_num < probability && level < MAX_LEVEL) {	//模拟每一次都是50%的概率小于probability
		random_num = distribution(generator);
		++level;
	}
	return level;
}
 
插入 
template 
void skipList::insert(int value) {
	int level = randomLevel();
	Node* newNode = new Node(value, level);
	Node** preNode=new Node*[level];
	for (int i = 0; i < level; i++)
		preNode[i] = head;

	Node* cur = head;
	for (int i = level - 1; i >= 0; i--) {		//每一层遍历，找到小于value的最后一个结点，记录在preNode[i]中
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
		preNode[i] = cur;
	}
	for (int i = 0; i < level; i++) {		//每层都插入结点newNode
		newNode->nextNode[i] = preNode[i]->nextNode[i];
		preNode[i]->nextNode[i] = newNode;
	}
	if (level > max_level)	//更新max_level
		max_level = level;
	delete[] preNode;
}

 
  插入我们需要找到每一层插入的前置结点，这里我们用一个preNode数组来存储，由于preNode是一个指针数组，所以是二维指针，我们初始化preNode将每一个元素指向head，然后按查找的思路在每一层查找到最后一个小于插入值的结点，存储在preNode数组中。
   接着就像链表插入一样进行指针的赋值操作，然后看看需不需要更新整个跳表的最大层数max_level，最后释放掉preNode的内存，整个插入操作就完成了。 
删除 
template 
void skipList::remove(int value) {
	Node** preNode = new Node * [max_level];
	Node* cur = head;
	for (int i = max_level - 1; i >= 0; i--) {	//每一层遍历，找到小于value的最后一个结点，记录在preNode[i]中
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
		preNode[i] = cur;
	}
	if (cur->nextNode[0] != nullptr && cur->nextNode[0]->data == value) {
		Node* tmp = cur->nextNode[0];
		for (int i = max_level - 1; i >= 0; i--) 
			if (preNode[i]->nextNode[i] != nullptr && preNode[i]->nextNode[i]->data == value)
				preNode[i]->nextNode[i]=preNode[i]->nextNode[i]->nextNode[i];
		delete tmp;
	}
	else
		std::cout << "remove failed: cant find Node->data==valuen";

	while (max_level > 1 && head->nextNode[max_level - 1] == nullptr)	//更新max_level
		--max_level;

	delete[] preNode;
}
 
  删除我们也同样需要找到要删除的结点在每一层的前置结点，存储在preNode数组中，然后删除这个结点。
   更新层高，我们从最高层max_level，从head开始看看head在每一层是否有下一个结点，如果head的下一个结点为空，说明这一层没有索引了，所以max_level要减一。 
完整代码 
#ifndef SKIPLIST_H
#define SKIPLIST_H

#include 
#include 
#include 
#include 
#include 

const int MAX_LEVEL = 16;

template 
class skipList {
private:
	struct Node {
		T data;
		int level=0;
		Node* nextNode[MAX_LEVEL];		//node.nextNode[i]表示node在第i层的下一个结点
		Node(){
			for (int i = 0; i < MAX_LEVEL; i++)
				nextNode[i] = nullptr;
		}
		Node(T data, int level):Node() {
			this->data = data;
			this->level = level;
		}
	};

private:
	int max_level=1;//当前最高的层数
	float probability=0.5;
	Node* head = new Node();//所有层的哨兵
public:
	skipList(){}
	skipList(std::initializer_list init);
	~skipList();
	Node* find(T value);
	void insert(int value);
	void remove(int value);
	void print();
private:
	int randomLevel();
};

template 
skipList::skipList(std::initializer_list init) {	//这里用户输入的初始化列表需要用户自己保证有序
	for (auto& v : init)
		insert(v);
}

template 
skipList::~skipList() {
	Node* node = head;
	while(node!=nullptr && node->nextNode[0]!=nullptr){
		Node* tmp = node;
		node = node->nextNode[0];	//这里只需要遍历删除nextNode[0]，因为即使有多层，其实用的只有一个node，看Insert的实现就知道了
		delete tmp;
	}
	delete node;
}

template 
typename skipList::Node* skipList::find(T value) {		//注意skipList::Node前要加typename
	Node* cur = head;
	for (int i = max_level - 1; i >= 0; i--) {
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
	}
	if (cur->nextNode[0] != nullptr && cur->nextNode[0]->data == value) {
		return cur->nextNode[0];
	}
	else {
		std::cout << "find failed: cant find Node->data == "<
void skipList::insert(int value) {
	int level = randomLevel();
	Node* newNode = new Node(value, level);
	Node** preNode=new Node*[level];
	for (int i = 0; i < level; i++)
		preNode[i] = head;

	Node* cur = head;
	for (int i = level - 1; i >= 0; i--) {		//每一层遍历，找到小于value的最后一个结点，记录在preNode[i]中
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
		preNode[i] = cur;
	}
	for (int i = 0; i < level; i++) {		//每层都插入结点newNode
		newNode->nextNode[i] = preNode[i]->nextNode[i];
		preNode[i]->nextNode[i] = newNode;
	}
	if (level > max_level)	//更新max_level
		max_level = level;
	delete[] preNode;
}

template 
void skipList::remove(int value) {
	Node** preNode = new Node * [max_level];
	Node* cur = head;
	for (int i = max_level - 1; i >= 0; i--) {	//每一层遍历，找到小于value的最后一个结点，记录在preNode[i]中
		while (cur->nextNode[i] != nullptr && cur->nextNode[i]->data < value)
			cur = cur->nextNode[i];
		preNode[i] = cur;
	}
	if (cur->nextNode[0] != nullptr && cur->nextNode[0]->data == value) {
		Node* tmp = cur->nextNode[0];
		for (int i = max_level - 1; i >= 0; i--) 
			if (preNode[i]->nextNode[i] != nullptr && preNode[i]->nextNode[i]->data == value)
				preNode[i]->nextNode[i]=preNode[i]->nextNode[i]->nextNode[i];
		delete tmp;
	}
	else
		std::cout << "remove failed: cant find Node->data==valuen";

	while (max_level > 1 && head->nextNode[max_level - 1] == nullptr)	//更新max_level
		--max_level;

	delete[] preNode;
}

//简单打印
template 
void skipList::print() {
	for (int i = max_level - 1; i >= 0; i--) {
		std::cout << "level-" << i << "   ";
		Node* cur = head;
		while (cur->nextNode[i] != nullptr) {
			std::cout << cur->nextNode[i]->data << " ";
			cur = cur->nextNode[i];
		}
		std::cout << std::endl;
	}
}



template 
int skipList::randomLevel() {
	int level = 1;
	const unsigned int seed =std::chrono::system_clock::now().time_since_epoch().count();	//获取系统时间戳，单位微秒(microsecond)。
	std::default_random_engine generator(seed);	//系统时间戳作为种子
	std::uniform_real_distribution distribution(0, 1);	
	float random_num = distribution(generator);	//均匀分布，生成区间[0,1]的浮点数
	while (random_num < probability && level < MAX_LEVEL) {	
		random_num = distribution(generator);
		++level;
	}
	return level;
}
#endif

数据结构与算法详解——跳表篇（附c++实现代码）

C/C++/C#相关栏目本月热门文章