c++如何实现跳表(skiplist)
引言
二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?实际上,只需要对链表稍加改造,就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。
定义
跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是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_list init):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;i next[i]=nullptr; returnnode; } /* *随机函数,范围[1,kMaxLevel],越小概率越大 */ staticintrandomLevel() { intlevel=1; while(rand()%2&&level =0;--i) { while(pNode->next[i]!=nullptr&&pNode->next[i]->key next[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]->key next[i]; } prev[i]=pNode; } //然后每层将新节点插入到前继节点后面 for(inti=0;i next[i]=prev[i]->next[i]; prev[i]->next[i]=new_node; } if(maxLevel =0;--i) { while(pNode->next[i]!=nullptr&&pNode->next[i]->key 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(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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。