SkipList 跳表的原理以及实现

#pragma once
#ifndef SKIPLIST_INT_H_
#define SKIPLIST_INT_H_
#include <cstdlib>     /* srand, rand */
#include <ctime>       /* time */
#include <climits>     /* INT_MIN */
/* 简单跳跃表，它允许简单的插入和删除元素，并提供O(logn)的查询时间复杂度。 */
/*
    SkipList_Int的性质
    (1) 由很多层结构组成，level是通过一定的概率随机产生的，基本是50%的产生几率。
    (2) 每一层都是一个有序的链表，默认是升序，每一层的链表头作为跳点。
    (3) 最底层(Level 1)的链表包含所有元素。
    (4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
    (5) 每个节点包含四个指针，但有可能为nullptr。
    (6) 每一层链表横向为单向连接，纵向为双向连接。
*/
// Simple SkipList_Int 表头始终是列表最小的节点
class SkipList_Int {
private:
    /* 节点元素 */
    struct node {
        node(int val = INT_MIN) :value(val), up(nullptr), down(nullptr), left(nullptr), right(nullptr) {}
        int value;
        // 设置4个方向上的指针
        struct node* up; // 上
        struct node* down; // 下
        struct node* left; // 左
        struct node* right; // 右
    };
private:
    node* head; // 头节点，查询起始点
    int lvl_num; // 当前链表层数
    /* 随机判断 */
    bool randomVal();
public:
    SkipList_Int(): lvl_num(1) {
        head = new node();
    }
    /* 插入新元素 */
    void insert(int val);
    /* 查询元素 */
    bool search(int val);
    /* 删除元素 */ 
    void remove(int val);
};
#endif // !SKIPLIST_INT_H_

#include "SkipList_Int.h"

static unsigned int seed = NULL; // 随机种子

bool SkipList_Int::randomVal() {    
    if (seed == NULL) {
        seed = (unsigned)time(NULL);
    }
    ::srand(seed);
    int ret = ::rand() % 2;
    seed = ::rand();
    if (ret == 0) {
        return true;
    }
    else {
        return false;
    }
}

void SkipList_Int::insert(int val) {
    /* 首先查找L1层 */
    node* cursor = head;
    node* new_node = nullptr;
    while (cursor->down != nullptr) {
        cursor = cursor->down;
    }
    node* cur_head = cursor; // 当前层链表头
    while (cursor->right != nullptr) {
        if (val < cursor->right->value && new_node == nullptr) {
            new_node = new node(val);
            new_node->right = cursor->right;
            cursor->right = new_node;
        }
        cursor = cursor->right; // 向右移动游标
    }
    if (new_node == nullptr) {
        new_node = new node(val);
        cursor->right = new_node;
    }
    /* L1层插入完成 */
    /* 上层操作 */
    int cur_lvl = 1; // 当前所在层
    while (randomVal()) {
        cur_lvl++;
        if (lvl_num < cur_lvl) { // 增加一层
            lvl_num++;
            node* new_head = new node();
            new_head->down = head;
            head->up = new_head;
            head = new_head;
        }
        cur_head = cur_head->up; // 当前链表头上移一层
        cursor = cur_head; // 继续获取游标
        node* skip_node = nullptr; // 非L1层的节点
        while (cursor->right != nullptr) {
            if (val < cursor->right->value && skip_node == nullptr) {
                skip_node = new node(val);
                skip_node->right = cursor->right;
                cursor->right = skip_node;
            }
            cursor = cursor->right;
        }
        if (skip_node == nullptr) {
            skip_node = new node(val);
            cursor->right = skip_node;
        }
        while (new_node->up != nullptr) {
            new_node = new_node->up;
        }
        /* 连接上下两个节点 */
        skip_node->down = new_node;
        new_node->up = skip_node;
    }
}

bool SkipList_Int::search(int val) {
    node* cursor = nullptr;
    if (head == nullptr) {
        return false;
    }
    /* 初始化游标指针 */
    cursor = head;
    while (cursor->down != nullptr) { // 第一层循环游标向下
        while (cursor->right != nullptr) { // 第二层循环游标向右
            if (val <= cursor->right->value) { // 定位元素:于当前链表发现可定位坐标则跳出循环...
                break;
            }
            cursor = cursor->right;
        }
        cursor = cursor->down;
    }
    while (cursor->right != nullptr) { // L1层循环开始具体查询
        if (val > cursor->right->value) {
            cursor = cursor->right; // 如果查找的值大于右侧值则游标可以继续向右
        } 
        else if (val == cursor->right->value) { // 如果等于则表明已经找到节点
            return true;
        }
        else if (val < cursor->right->value) { // 如果小于则表明不存在该节点
            return false;
        }
    }
    return false; // 完成遍历返回false;
}

void SkipList_Int::remove(int val) {
    node* cursor = head; // 获得游标
    node* pre_head = nullptr; // 上一行的头指针，删除行时使用
    while (true) {
        node* cur_head = cursor; // 当前行头指针
        if (pre_head != nullptr) {
            cur_head->up = nullptr;
            pre_head->down = nullptr; // 解除上下级的指针
            delete pre_head;
            pre_head = nullptr; // 指针归0
            lvl_num--; // 层数-1
            head = cur_head; // 重新指定起始指针
        }
        while (cursor != nullptr && cursor->right != nullptr) { // 在当前行中查询val
            if (val == cursor->right->value) {
                node* delptr = cursor->right;
                cursor->right = cursor->right->right;
                delete delptr; // 析构找到的节点
            }
            cursor = cursor->right;
        }
        if (cur_head->right == nullptr) { // 判断当前行是否还存在其它元素，如果不存在则删除该行并将整个跳跃表降维
            pre_head = cur_head;
        }
        if (cur_head->down == nullptr) {
            break;
        }
        else {
            cursor = cur_head->down;
        }
    }
}

template<typename T>
class Entry {
private:
    int key; // 排序值
    T value; // 保存对象
    Entry* pNext;
    Entry* pDown;
public:
    // The Constructor
    Entry(int k, T v) :value(v), key(k), pNext(nullptr), pDown(nullptr) {}
    // The Copy-constructor
    Entry(const Entry& e) :value(e.value), key(e.key), pNext(nullptr), pDown(nullptr) {}

public:
    /* 重载运算符 */
    bool operator<(const Entry& right) {
        return key < right.key;
    }
    bool operator>(const Entry& right) {
        return key > right.key;
    }
    bool operator<=(const Entry& right) {
        return key <= right.key;
    }
    bool operator>=(const Entry& right) {
        return key >= right.key;
    }
    bool operator==(const Entry& right) {
        return key == right.key;
    }
    Entry*& next() {
        return pNext;
    }
    Entry*& down() {
        return pDown;
    }
};

struct Endpoint {
    Endpoint* up;
    Endpoint* down;
    Entry<T>* right;
};

#pragma once
#ifndef SKIPLIST_ENTRY_H_
#define SKIPLIST_ENTRY_H_
/* 一个更具备代表性的泛型版本 */
#include <ctime>
#include <cstdlib>
template<typename T>
class Entry {
private:
    int key; // 排序值
    T value; // 保存对象
    Entry* pNext;
    Entry* pDown;
public:
    // The Constructor
    Entry(int k, T v) :value(v), key(k), pNext(nullptr), pDown(nullptr) {}
    // The Copy-constructor
    Entry(const Entry& e) :value(e.value), key(e.key), pNext(nullptr), pDown(nullptr) {}

public:
    /* 重载运算符 */
    bool operator<(const Entry& right) {
        return key < right.key;
    }
    bool operator>(const Entry& right) {
        return key > right.key;
    }
    bool operator<=(const Entry& right) {
        return key <= right.key;
    }
    bool operator>=(const Entry& right) {
        return key >= right.key;
    }
    bool operator==(const Entry& right) {
        return key == right.key;
    }
    Entry*& next() {
        return pNext;
    }
    Entry*& down() {
        return pDown;
    }
};
template<typename T>
class SkipList_Entry {
private:
    struct Endpoint {
        Endpoint* up;
        Endpoint* down;
        Entry<T>* right;
    };
    struct Endpoint* header;
    int lvl_num; // level_number 已存在的层数
    unsigned int seed;
    bool random() {
        srand(seed);
        int ret = rand() % 2;
        seed = rand();
        return ret == 0;
    }
public:
    SkipList_Entry() :lvl_num(1), seed(time(0)) {
        header = new Endpoint();
    }
    /* 插入新元素 */
    void insert(Entry<T>* entry) { // 插入是一系列自底向上的操作
        struct Endpoint* cur_header = header;
        // 首先使用链表header到达L1
        while (cur_header->down != nullptr) {
            cur_header = cur_header->down;
        }
        /* 这里的一个简单想法是L1必定需要插入元素，而在上面的各跳跃层是否插入则根据random确定
           因此这是一个典型的do-while循环模式 */
        int cur_lvl = 0; // current_level 当前层数
        Entry<T>* temp_entry = nullptr; // 用来临时保存一个已经完成插入的节点指针
        do {
            Entry<T>* cur_cp_entry = new Entry<T>(*entry); // 拷贝新对象
            // 首先需要判断当前层是否已经存在，如果不存在增新增
            cur_lvl++;
            if (lvl_num < cur_lvl) {
                lvl_num++;
                Endpoint *new_header = new Endpoint();
                new_header->down = header;
                header->up = new_header;
                header = new_header;
            }
            // 使用cur_lvl作为判断标准，!=1表示cur_header需要上移并连接“同位素”指针
            if (cur_lvl != 1) {
                cur_header = cur_header->up;
                cur_cp_entry->down() = temp_entry;
            }
            temp_entry = cur_cp_entry;
            // 再需要判断的情况是当前所在链表是否已经有元素节点存在，如果是空链表则直接对右侧指针赋值并跳出循环
            if (cur_header->right == nullptr) {
                cur_header->right = cur_cp_entry;
                break;
            }
            else {
                Entry<T>* cursor = cur_header->right; // 创建一个游标指针
                while (true) { // 于当前链表循环向右寻找可插入点，并在找到后跳出当前循环
                    if (*cur_cp_entry < *cursor) { // 元素小于当前链表所有元素，插入链表头
                        cur_header->right = cur_cp_entry;
                        cur_cp_entry->next() = cursor;
                        break;
                    }
                    else if (cursor->next() == nullptr) { // 元素大于当前链表所有元素，插入链表尾
                        cursor->next() = cur_cp_entry;
                        break;
                    }
                    else if (*cur_cp_entry < *cursor->next()) { // 插入链表中间
                        cur_cp_entry->next() = cursor->next();
                        cursor->next() = cur_cp_entry;
                        break;
                    }
                    cursor = cursor->next(); // 右移动游标
                }
            }
        } while(random());
    }

    /* 查询元素 */
    bool search(Entry<T>* entry) const {
        if (header->right == nullptr) { // 判断链表头右侧空指针
            return false;
        }
        Endpoint* cur_header = header;
        // 在lvl_num层中首先找到可以接入的点
        for (int i = 0; i < lvl_num; i++) {
            if (*entry < *cur_header->right) {
                cur_header = cur_header->down;
            }
            else {
                Entry<T>* cursor = cur_header->right;
                while (cursor->down() != nullptr) {
                    while (cursor->next() != nullptr) {
                        if (*entry <= *cursor->next()) {
                            break;
                        }
                        cursor = cursor->next();
                    }
                    cursor = cursor->down();
                }
                while (cursor->next() != nullptr) {
                    if (*entry > *cursor->next()) {
                        cursor = cursor->next();
                    }
                    else if (*entry == *cursor->next()) {
                        return true;
                    }
                    else {
                        return false;
                    }
                }
                return false; // 节点大于L1最后一个元素节点，返回false
            }
        }
        return false; // 找不到接入点，则直接返回false;
    }
    /* 删除元素 */
    void remove(Entry<T>* entry) {
        if (header->right == nullptr) {
            return;
        }
        Endpoint* cur_header = header;
        Entry<T>* cursor = cur_header->right;
        int lvl_counter = lvl_num; // 因为在删除的过程中，跳跃表的层数会中途发生变化，因此应该在进入循环之前要获取它的值。
        for (int i = 0; i < lvl_num; i++) {
            if (*entry == *cur_header->right) {
                Entry<T>* delptr = cur_header->right;
                cur_header->right = cur_header->right->next();
                delete delptr;
            }
            else {
                Entry<T> *cursor = cur_header->right;
                while (cursor->next() != nullptr) {
                    if (*entry == *cursor->next()) { // 找到节点->删除->跳出循环
                        Entry<T>* delptr = cursor->next();
                        cursor->next() = cursor->next()->next();
                        delete delptr;
                        break;
                    }
                    cursor = cursor->next();
                }
            }
            // 向下移动链表头指针的时候需要先判断当前链表中是否还存在Entry节点
            if (cur_header->right == nullptr) {
                Endpoint* delheader = cur_header;
                cur_header = cur_header->down;
                header = cur_header;
                delete delheader;
                lvl_num--;
            }
            else {
                cur_header = cur_header->down;
            }
        }
    }
};
#endif // !SKIPLIST_ENTRY_H_