SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构。由于它的代码以及原理实现的简单性,更为人们所接受。

所有操作均从上向下逐层查找,越上层一次next操作跨度越大。其实现是典型的空间换时间。

Skip lists  are data structures  that use probabilistic  balancing rather  than  strictly  enforced balancing. 
As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly
faster than equivalent algorithms for balanced trees.

 

后面的图片来自:http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

后面的代码当然是我自己写的呀。

(1)SkipList图示

(2)SkipList插入

(3)SkipList删除

(3)SkipList查找

  查找操作也是上面的套路


 

实现中主要有几点需要注意:

(1) 如何支持各种数据类型的数据。 通用的做法就是 char数组保存value + char数组对应value的长度

(2) 看图中,每个节点有多个指向不同层级的指针。代码中可以使用指针数组 + 节点的level来保存。

(3) 查找、插入、删除操作,都要找到(或者经过)需要操作点的前驱节点。这个操作可以封装起来,极大减少代码量。

(4) skiplist整体是一个链表, 设置一个头节点方便后续的各种操作。

数据结构如下:

 1 truct SkipNode{ 
 2     int  key;       //key 
 3     char *value;    //value,可以支持任意类型 
 4     int  length;    //value_length, 记录数据长度 
 5     int  level;     //保存当前节点的level 
 6     SkipNode** next;    //记录各层后续的地址 
 7 };

skiplist.h

class SkipList{ 
public: 
    SkipList(int level = 10); 
    ~SkipList(); 
 
    //根据key获取数据 
    int get(const int key, char* value, int &length); 
 
    //链表插入新节点 
    int insert( 
            const int key,  
            const char* value,  
            const int length); 
 
    //删除key对应节点 
    int del(const int key); 
 
private: 
    //初始化链表头, 路过链表 
    int init(); 
 
    //空间释放 
    int deinit(); 
 
    //新建一个节点 
    SkipNode* createNode( 
            const int key,  
            const char* value,  
            const int &length, 
            const int level); 
 
    //所用随机函数获取一个level值, 用于后续新建节点使用 
    int getNewNodeLevel(); 
    
    //init update node 
    int init_updatenode(); 
 
    //get node pre(get update) 
    int get_update(const int key); 
 
    //记录skiplist支持的最大level, 以及当前高度 
    int max_level; 
    int curr_level; 
 
    SkipNode* List; //skiplist 第一个节点 
    SkipNode** Update;  //记录每层搜索节点的前驱节点 
};

 

cpp代码比较长,这里就不贴了。

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Reservoir Sampling 蓄水池抽样算法,经典抽样讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。