c++如何实现跳表（skiplist）

2023-07-18 21:42:03 72

引言

二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。

定义

跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。
跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的插入和删除操作要简单得多，执行也更快。

C++简单实现

下面实现过程主要是简单实现跳表的过程，不是多线程安全的，LevelDB实现的跳表支持多线程安全，用了std::atomic原子操作，本文主要是为了理解跳表的原理，所以采用最简单的实现。

#ifndefSKIPLIST_H
#defineSKIPLIST_H

#include
#include
#include
#include

template
classSkiplist{
public:
structNode{
Node(Keyk):key(k){}
Keykey;
Node*next[1];//C语言中的柔性数组技巧
};

private:
intmaxLevel;
Node*head;

enum{kMaxLevel=12};

public:
Skiplist():maxLevel(1)
{
head=newNode(0,kMaxLevel);
}

Skiplist(std::initializer_listinit):Skiplist()
{
for(constKey&k:init)
{
insert(k);
}
}

~Skiplist()
{
Node*pNode=head;
Node*delNode;
while(nullptr!=pNode)
{
delNode=pNode;
pNode=pNode->next[0];
free(delNode);//对应malloc
}
}

//禁止拷贝构造和赋值
Skiplist(constSkiplist&)=delete;
Skiplist&operator=(constSkiplist&)=delete;
Skiplist&operator=(Skiplist&&)=delete;

private:
Node*newNode(constKey&key,intlevel)
{
/*
*开辟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(inti=0;inext[i]=nullptr;

returnnode;
}
/*
*随机函数，范围[1,kMaxLevel]，越小概率越大
*/
staticintrandomLevel()
{
intlevel=1;
while(rand()%2&&level=0;--i)
{
while(pNode->next[i]!=nullptr&&pNode->next[i]->keynext[i];
}
}

//如果第一层的pNode[0]->key==key，则返回pNode->next[0]，即找到key
if(nullptr!=pNode->next[0]&&pNode->next[0]->key==key)
returnpNode->next[0];

returnnullptr;
}

voidinsert(constKey&key)
{
intlevel=randomLevel();
Node*new_node=newNode(key,level);
Node*prev[kMaxLevel];
Node*pNode=head;
//从最高层开始查找，每层查找最后一个小于key的前继节点
for(inti=level-1;i>=0;--i)
{
while(pNode->next[i]!=nullptr&&pNode->next[i]->keynext[i];
}
prev[i]=pNode;
}
//然后每层将新节点插入到前继节点后面
for(inti=0;inext[i]=prev[i]->next[i];
prev[i]->next[i]=new_node;
}

if(maxLevel=0;--i)
{
while(pNode->next[i]!=nullptr&&pNode->next[i]->keynext[i];
prev[i]=pNode;
}

//如果找到key，
if(pNode->next[0]!=nullptr&&pNode->next[0]->key==key)
{
Node*delNode=pNode->next[0];
//从最高层开始，如果当前层的next节点的值等于key，则删除next节点
for(inti=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++跳表的资料请关注毛票票其它相关文章！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

c++如何实现跳表（skiplist）

热门推荐

随机推荐