我要评论引言
二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。
定义
跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是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
}
}
// 禁止拷贝构造和赋值
skiplist(const skiplist&) = delete;
skiplist& operator=(const skiplist&) = delete;
skiplist& operator=(skiplist&&) = delete;
private:
node* newnode(const key& key, int level)
{
/*
* 开辟sizeof(node) + sizeof(node*) * (level - 1)大小的空间
* sizeof(node*) * (level - 1)大小的空间是给node.next[1]指针数组用的
* 为什么是level-1而不是level，因为sizeof(node)已包含一个node*指针的空间
*/
void* node_memory = malloc(sizeof(node) + sizeof(node*) * (level - 1));
node* node = new (node_memory) node(key);
for (int i = 0; i < level; ++i)
node->next[i] = nullptr;
return node;
}
/*
* 随机函数，范围[1, kmaxlevel]，越小概率越大
*/
static int randomlevel()
{
int level = 1;
while (rand() % 2 && level < kmaxlevel)
level++;
return level;
}
public:
node* find(const key& key)
{
// 从最高层开始查找，每层查找最后一个小于key的前继节点，不断缩小范围
node* pnode = head;
for (int i = maxlevel - 1; i >= 0; --i)
{
while (pnode->next[i] != nullptr && pnode->next[i]->key < key)
{
pnode = pnode->next[i];
}
}
// 如果第一层的pnode[0]->key == key，则返回pnode->next[0]，即找到key
if (nullptr != pnode->next[0] && pnode->next[0]->key == key)
return pnode->next[0];
return nullptr;
}
void insert(const key& key)
{
int level = randomlevel();
node* new_node = newnode(key, level);
node* prev[kmaxlevel];
node* pnode = head;
// 从最高层开始查找，每层查找最后一个小于key的前继节点
for (int i = level - 1; i >= 0; --i)
{
while (pnode->next[i] != nullptr && pnode->next[i]->key < key)
{
pnode = pnode->next[i];
}
prev[i] = pnode;
}
// 然后每层将新节点插入到前继节点后面
for (int i = 0; i < level; ++i)
{
new_node->next[i] = prev[i]->next[i];
prev[i]->next[i] = new_node;
}
if (maxlevel < level) // 层数大于最大层数，更新最大层数
maxlevel = level;
}
void erase(const key& key)
{
node* prev[maxlevel];
node* pnode = head;
// 从最高层开始查找，每层查找最后一个小于key的前继节点
for (int i = maxlevel - 1; i >= 0; --i)
{
while (pnode->next[i] != nullptr && pnode->next[i]->key < key)
pnode = pnode->next[i];
prev[i] = pnode;
}
// 如果找到key，
if (pnode->next[0] != nullptr && pnode->next[0]->key == key)
{
node *delnode = pnode->next[0];
// 从最高层开始，如果当前层的next节点的值等于key，则删除next节点
for (int i = maxlevel - 1; i >= 0; --i)
{
if (prev[i]->next[i] != nullptr && key == prev[i]->next[i]->key)
prev[i]->next[i] = prev[i]->next[i]->next[i];
}
free(delnode); // 最后销毁pnode->next[0]节点
}
// 如果max_level>1且头结点的next指针为空，则该层已无数据，max_level减一
while (maxlevel > 1 && head->next[maxlevel] == nullptr)
{
maxlevel--;
}
}
};
#endif
redis和leveldb选用跳表而弃用红黑树的原因
- skiplist的复杂度和红黑树一样，而且实现起来更简单。
- 在并发环境下skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。
以上就是c++如何实现跳表的详细内容，更多关于c++ 跳表的资料请关注移动技术网其它相关文章！
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论