算法: skiplist 跳跃表代码实现和原理

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. 

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

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;  //记录每层搜索节点的前驱节点
};