c++如何实现跳表(如何实现跳表(skiplist))
引言引言
二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了
吗?实际上,只需要对链表稍加改造,就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。
定义定义
跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是
O(log n),优于普通队列的O(n)。性能上和红黑树,AVL树不相上下,但跳表的原理非常简单,目前Redis和LevelDB中都有用
到。
跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡,而不是严格平衡。因此,跟平衡二叉树相比,跳表的插入
和删除操作要简单得多,执行也更快。
C++简单实现简单实现
下面实现过程主要是简单实现跳表的过程,不是多线程安全的,LevelDB实现的跳表支持多线程安全,用了std::atomic原子操
作,本文主要是为了理解跳表的原理,所以采用最简单的实现。
#ifndef SKIPLIST_H
#define SKIPLIST_H
#include <ctime>
#include <initializer_list>
#include <iostream>
#include <random>
template <typename Key>
class Skiplist {
public:
struct Node {
Node(Key k) : key(k) {}
Key key;
Node* next[1]; // C语言中的柔性数组技巧
};
private:
int maxLevel;
Node* head;
enum { kMaxLevel = 12 };
public:
Skiplist() : maxLevel(1)
{
head = newNode(0, kMaxLevel);
}
Skiplist(std::initializer_list<Key> init) : Skiplist()
{
for (const Key& k : init)
{
insert(k);
}
}
~Skiplist()
{
Node* pNode = head;
Node* delNode;
while (nullptr != pNode)
{
delNode = pNode;
pNode = pNode->next[0];
free(delNode); // 对应malloc
}
}
评论5