C语言中skip函数,c++如何实现跳表（skiplist）

引言

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

定义

跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。

跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的插入和删除操作要简单得多，执行也更快。

C++简单实现

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

#ifndef SKIPLIST_H

#define SKIPLIST_H

#include

#include

#include

#include

template

class Skiplist {

public:

struct Node {

Node(Key k) : key(k) {}

Key key;

Node* next[1]; // C语言中的柔性数组技巧

};

private:

int ma

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！