如何的实现一个高效的有序集合?最先想到的就是二叉树。当然二叉树的性能会受到输入数据的影响,一般采用二叉树的改进版本比如红黑树、AVL树。最近在看算法相关的书的时候发现,原来链表经过一定的改进也可以实现高效插入删除,这就是跳跃表。网易公开课上也有关于跳跃表的公开课,Erik Demaine大神授课,浅显易懂。完整代码见Gist

有序链表

跳跃表的基础就是有序链表,所以首选需要实现一个有序的链表。对于有序链表,加入一个空的头部节点会让整个插入过程容易很多。

下面就是一个简单的有序链表,数据结构本身没有太大难度。

template <class K, class V>
class SkipList
{
	// key-value data
	struct Pair
	{
		K _key;
		V _value;
		Pair(K k, V v): _key(k), _value(v) {}
	};

	// link list node
	struct Node
	{
		Node *_next, *_prev;
		Pair *_pair;
		Node(Pair *pair = nullptr, Node *prev = nullptr, Node *next = nullptr): _pair(pair), _prev(prev), _next(next) {}
		~Node()
		{
			if (_pair)
				delete _pair;
		}
	};

	Node *head = new Node();

	// find the node that node->_key <= key
	Node *searchList(Node *li, const K &key)
	{
		Node *ptr = li;
		while (ptr->_next && ptr->_next->_pair->_key <= key)
			ptr = ptr->_next;
		return ptr;
	}
public:
	SkipList() = default;

	SkipList(const SkipList &li)
	{
		head = new Node();
		Node *tail = head;
		Node *ptr = li.head->_next;
		while (ptr) {
			Node *node = new Node(new Pair(*ptr->_pair), tail);
			node->_prev = tail;
			tail->_next = node;
			tail = node;
			ptr = ptr->_next;
		}
	}

	~SkipList()
	{
		Node *ptr = head;
		while (ptr) {
			Node *tmpPtr = ptr;
			ptr = ptr->_next;
			delete tmpPtr;
		}
	}

	SkipList& operator=(SkipList li)
	{
		std::swap(head, li.head);
		return (*this);
	}

	void put(const K key, const V value)
	{
		Node *prev = searchList(head, key);
		if (prev->_pair && prev->_pair->_key == key) {	// already exist, update value
			prev->_pair->_value = value;
			return;
		}
		Node *node = new Node(new Pair(key, value), prev, prev->_next);
		if (prev->_next)
			prev->_next->_prev = node;
		prev->_next = node;
	}

	V *get(K key)
	{
		Node *node = searchList(head, key);
		Pair *pair = node->_pair;
		if (pair == nullptr || pair->_key != key)	// not found
			return nullptr;
		return &(pair->_value);
	}

	void remove(K key)
	{
		Node *node = searchList(head, key);
		Pair *pair = node->_pair;
		if (pair == nullptr || pair->_key != key)	// not found
			return;
		if (node->_next)
			node->_next->_prev = node->_prev;
		node->_prev->_next = node->_next;
	}
};

增加高层有序链表

跳跃表就是在有序链表的基础上增加了很多的高层有序链表,高层的有序链表存储着下层有序链表的一个子集。在查找某个元素的时候,从高层链表向底层链表搜索,每次在某一层上搜索的时候,就可以缩小搜索的范围。

查找

查找从顶层的链表开始,可以认为所有的头节点的值为负无穷。每次搜索元素x的时候,找到最大的满足小于等于x的节点。如果节点的值刚好是要查找的值,那就直接返回。否则,将节点的下层节点为起点,反复进行同样的搜索过程。当然,如果在底层链表中还是找不到想要的节点,那么搜索失败。

插入

首先在底层链表中找到新节点应该插入的位置的前驱节点,将新节点插入。接下来,我们需要用随机数来决定是否要在高层的链表中插入新节点。为了能够在高层表中插入,程序在查找插入位置的过程中记录每一层新节点应该插入的位置的前驱节点,保存在栈中是一种很好的方式。如果运气比较好,新节点要插入比顶层链表更高层的链表,那么需要创建一个更加高层的链表,然后把新节点插入。

删除

删除操作和查找操作类似,不过在找到目标节点之后,如果目标节点存在下层节点,那么需要将下层节点也一并删除。

#include <ctime>
#include <cstdlib>
#include <stack>
#include <memory>

template <class K, class V>
class SkipList
{
	// key-value data
	struct Pair
	{
		K _key;
		V _value;
		Pair(const K &k, const V &v): _key(k), _value(v) {}
	};

	// link list node
	struct Node
	{
		Node *_next, *_prev, *_children;
		Pair *_pair;
		Node(Pair *pair = nullptr, Node *prev = nullptr,
			 Node *next = nullptr, Node *children = nullptr): 
			_pair(pair), _prev(prev), _next(next), _children(children) {}
		~Node()
		{
			// if node is bottom node, then delete pair
			if (_children == nullptr && _pair)
				delete _pair;
		}
	};

	Node *head = new Node();

	// find the node that node->_key <= key
	Node *searchList(Node *li, const K &key)
	{
		Node *ptr = li;
		while (ptr->_next && ptr->_next->_pair->_key <= key)
			ptr = ptr->_next;
		return ptr;
	}
public:
	SkipList()
	{
		srand(time(nullptr));
	}

	SkipList(const SkipList &li)
	{
		head = new Node();
		srand(time(nullptr));
		// reach bottom list
		Node *bottomList = li.head;
		while (bottomList->_children)
			bottomList = bottomList->_children;
		// add items to new skiplist
		for (Node *ptr = bottomList; ptr; ptr = ptr->_next)
			if (ptr->_pair)
				put(ptr->_pair->_key, ptr->_pair->_value);
	}

	~SkipList()
	{
		// delete all nodes
		Node *li = head;
		while (li) {
			Node *tmphead = li;
			li = li->_children;
			Node *ptr = tmphead;
			while (ptr) {
				Node *tempnode = ptr;
				ptr = ptr->_next;
				delete tempnode;
			}
		}
	}

	SkipList& operator=(SkipList li)
	{
		std::swap(head, li.head);
		return (*this);
	}

	void put(const K &key, const V &value)
	{
		// track the precursor node in each level
		std::stack<Node*> prevs;
		Node *li = head;
		while (li) {
			Node *prev = searchList(li, key);
			prevs.push(prev);
			li = prev->_children;
		}
		// insert node in bottom level
		Pair *pair = new Pair(key, value);
		Node *prev = prevs.top();
		prevs.pop();
		// already exist
		if (prev->_pair && prev->_pair->_key == key) {
			prev->_pair->_value = value;
			return;
		}
		Node *newNode = new Node(pair, prev, prev->_next);
		if (prev->_next)
			prev->_next->_prev = newNode;
		prev->_next = newNode;
		// insert node in higher level
		while (true) {
			bool insertUp = rand() % 2;
			if (!insertUp)
				return;
			if (!prevs.empty()) {
				prev = prevs.top();
				prevs.pop();
			} else {
				head = new Node(nullptr, nullptr, nullptr, head);
				prev = head;
			}
			newNode = new Node(pair, prev, prev->_next, newNode);
			if (prev->_next)
				prev->_next->_prev = newNode;
			prev->_next = newNode;
		}
	}

	V *get(const K &key)
	{
		Node *ptr;
		Node *li = head;
		while (li) {
			ptr = searchList(li, key);
			if (ptr->_pair && ptr->_pair->_key == key)
				return &ptr->_pair->_value;
			li = ptr->_children;
		}
		if (ptr->_pair == nullptr || ptr->_pair->_key != key)
			return nullptr;
		return &ptr->_pair->_value;
	}

	void remove(const K &key)
	{
		// find node
		Node *ptr = head;
		while (ptr) {
			Node *node = searchList(ptr, key);
			if (node->_pair && node->_pair->_key == key) {
				ptr = node;
				break;
			}
			ptr = node->_children;
		}
		// not found
		if (ptr == nullptr)
			return;
		// delete node in each level
		while (ptr) {
			ptr->_prev->_next = ptr->_next;
			if (ptr->_next)
				ptr->_next->_prev = ptr->_prev;
			ptr = ptr->_children;
		}
	}
};