跳表

本文主要是介绍跳表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 跳表介绍

跳表是一种随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树、AVL树不相上下，
但是跳表的原理非常简单，目前在Redis和LevelDB 中都有用到
跳表的期望空间复杂度为 O(n)，跳表的查询，插入和删除操作的期望时间复杂度均为O(logn)
跳表实际为一种多层的有序链表，跳表的每一层都为一个有序链表
且满足每个位于第i层的节点有p的概率出现在第i+1层，其中p为常数

2. 跳表的查找（从上往下）

跳表在进行查找时，首先从当前的最高层 L(n)层开始查找，在当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点
然后移动至下一层进行查找，重复这个过程直至到达第一层。
此时，若下一个节点是目标节点，则成功查找；反之，则元素不存在。
由于从高层往低层开始查找，由于低层出现的元素可能不会出现在高层，
因此跳表在进行查找的过程中会跳过一些元素，相比于有序链表的查询，跳表的查询速度会更快

3. 跳表的增添（从上往下）

从跳表的当前的最大层数level层开始查找，在当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点，
然后移动至下一层进行查找，重复这个过程直至到达第1层。设新加入的节点为newNode，
我们需要计算出此次节点插入的层数 lv，如果 level 小于lv，则同时需要更新level。
我们用数组 update 保存每一层查找的最后一个节点，第 i 层最后的节点为update[i]
我们将 newNode 的后续节点指向update[i]的下一个节点，同时更新update[i] 的后续节点为newNode(头插法)

4. 跳表的删除（从上往下）

首先我们需要查找当前元素是否存在跳表中。从跳表的当前的最大层数level 层开始查找，
在当前层水平地逐个比较直至当前节点的下一个节点大于等于目标节点，然后移动至下一层进行查找，
重复这个过程直至到达第1层。如果第1层的下一个节点不等于num 时，则表示当前元素不存在直接返回
我们用数组update保存每一层查找的最后一个节点，第 i 层最后的节点为update[i]
此时第 i 层的下一个节点的值为num，则我们需要将其从跳表中将其删除。
由于第 i 层的以 p 的概率出现在第 i+1 层，因此我们应当从第 1 层开始往上进行更新，
将 num 从 update[i] 的下一跳中删除，同时更新 update[i] 的后续节点，直到当前层的链表中没有出现 num 的节点为止
最后我们还需要更新跳表中当前的最大层数level

5. 跳表实现

constexpr int MAX_LEVEL = 32;//最大层次
constexpr double P_FACTOR = 0.25; //以四分之一的概率转移到上层

//自定义n叉树
struct SkiplistNode {
    int val;
    vector<SkiplistNode *> forward;
    SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {
    }
};

class Skiplist {
private:
    SkiplistNode * head;
    int level;
    mt19937 gen{random_device{}()};//梅森随机数
    uniform_real_distribution<double> dis;//随机数范围

public:
    //初始化层次为0，头结点值为-1，无后驱，随机数范围（0,1）
    Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {}

    bool search(int target) {
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 target 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < target) {
                curr = curr->forward[i];//指针同层次后移
            }
        }
        curr = curr->forward[0];
        /* 检测当前元素的值是否等于 target */
        if (curr && curr->val == target) {
            return true;
        } 
        return false;
    }

    void add(int num) {
        vector<SkiplistNode *> update(MAX_LEVEL, head);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;//记录插入节点前驱
        }
        int lv = randomLevel();//生成层次
        level = max(level, lv);//取当前最大值
        SkiplistNode *newNode = new SkiplistNode(num, lv);//新建节点
        for (int i = 0; i < lv; i++) {
            /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
            newNode->forward[i] = update[i]->forward[i];//头插法插入节点
            update[i]->forward[i] = newNode;
        }
    }

    bool erase(int num) {
        vector<SkiplistNode *> update(MAX_LEVEL, nullptr);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        /* 如果值不存在则返回 false */
        if (!curr || curr->val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i]->forward[i] != curr) {
                break;
            }
            /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        /* 更新当前的 level */
        while (level > 1 && head->forward[level - 1] == nullptr) {
            level--;
        }
        return true;
    }

    int randomLevel() {
        int lv = 1;
        /* 随机生成 当前 lv */
        while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }
};
```

这篇关于跳表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！