【C++数据结构】跳表

文章目录

前言

skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。

跳表是什么

其实光从概念来说，跳表可能并不难理解，跳表相当于是单链表的基础上，向上增加索引的方式，让我们查找数据的时候能够类似用一个二分查找的方式查找，但实际上建立上面的索引过后，新插入和删除节点会破坏上下两层1：2的关系，也就是说，倘若你在第一层的索引：第二层的索引是1：2，并且后面的n:n+1也都保持这样的关系，那么查找的时候是能够保持logN的效率，但是插入和删除就会破坏这里的结构。

怎么解决上述问题呢？
skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数。即不需要调节其他节点的层数。

换句话讲，就是一个节点最多有多少层，上层的索引最高多少，在一开始就已经确定好了。当我们需要插入删除操作的时候，只需要找到插入位置前后节点，改变链接关系即可。

这是一种大胆的处理，是因为每次插入的时候跳表里的数据存储的位置，层数都可能发生变化，并且他也有可能出现前面部分都是低矮层数，后面都是高层次的节点，从而降低了效率。

随即层数的理解

其中节点随机层数，其实随即层数也是有讲究的，随即过后每一层的节点数其实是相对固定的，随即层数的函数会保证上一层的节点数：下一层的节点数是1：2。
当p设置的小，层数就会低一点，像redis通常设置为0.25。

跳表通常需要有一个最大层数maxLevel，以及一个概率p，即新增加一层的概率。通常数据量够大，就会呈现出一定的比率。

当p是0.25，那么只有产生一层的概率就是1-p（0.75），产生第二层的概率就是（1-p） * p。三层（1-p）pp…
因此，一个节点的平均层数（也即包含的平均指针数目），计算如下

设计一个跳表

1. 设计跳表

#pragmaonce#include<iostream>usingnamespace std;#include<vector>#include<time.h>#include<random>#include<chrono>classSkiplist{public:structNode{
        vector<Node*> _skiplist;int _level;int _val;Node(int level,int val):_skiplist(level,nullptr),_level(level),_val(val){}};Skiplist(){srand(0);//头节点默认只有0层，即最底层
        _root =newNode(1,-1);}boolsearch(int target){//查找一个元素的时候//指针指向的比key值小的话，往右，其他情况往下
        Node* cur = _root;int level = cur->_level -1;//从最上层开始往下遍历while(level >=0){if(cur->_skiplist[level]&& cur->_skiplist[level]->_val < target){//往右边走
                cur = cur->_skiplist[level];}elseif(cur->_skiplist[level]&& cur->_skiplist[level]->_val == target){//此时查找的值就在右边returntrue;}else{//其他情况都是往下走，最终会从下面越界
                level--;}}returnfalse;}//由于前后链接的时是需要整个Node占一个数组的位置
    vector<Node*>Find(int target,int level){if(_root->_level < level){//超过level的置成nullptr
            _root->_skiplist.resize(level,nullptr);
            _root->_level = level;}//level层，并且每一个插入元素的前一个位置的指针
        vector<Node*>preNode(level,nullptr);
        level--;//从索引处开始
        Node* cur = _root;//实际上cur是工具人while(level >=0){if(cur->_skiplist[level]&& cur->_skiplist[level]->_val < target){//往右边走
                cur = cur->_skiplist[level];}else{//往下走之前实际上右边就是我们要插入的点
                preNode[level]= cur;

                level--;}}return preNode;}voidadd(int num){//先会创建num的节点//Random函数创建这个随机的层数int level =Random();//if(num == 0)//{//    level = 1;//}//else//{//    level = 5;//}
        Node* newNode =newNode(level, num);
        vector<Node*> preNode =Find(num, level);//此时将节点的前节点和后节点分别连接起来.//注意：先链接newNode的_skiplist节点for(int i =0; i < level;++i){
            newNode->_skiplist[i]= preNode[i]->_skiplist[i];
            preNode[i]->_skiplist[i]= newNode;}}intRandom(){int level =1;//最低从第一层开始if(rand()< _p * RAND_MAX && level < _maxLevel){
            level++;}return level;}/*int Random()
    {
        static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
        static std::uniform_real_distribution<double> distribution(0.0, 1.0);

        size_t level = 1;
        while (distribution(generator) <= _p && level < _maxLevel)
        {
            ++level;
        }

        return level;
    }*/boolerase(int num){int level = _root->_level;
        vector<Node*> preNode =Find(num, level);//若找不到，就是删除失败
        Node* del = preNode[0]->_skiplist[0];if(del ==nullptr|| del->_val != num)returnfalse;int delLevel = del->_level;
        delLevel--;//索引处开始删while(delLevel >=0){
            preNode[delLevel]->_skiplist[delLevel]= del->_skiplist[delLevel];
            delLevel--;}delete del;//erase节点的时候还可以优化，删掉头顶若干层int index = _root->_level -1;while(index >=0){if(!_root->_skiplist[index]){
                index--;}else{break;}}if(index != _root->_level -1){//说明上面几层可以不要
            _root->_skiplist.resize(index+1);
            _root->_level = index +1;}returntrue;}private:int _maxLevel =32;double _p =0.7;
    Node* _root =nullptr;};voidtest(){
    Skiplist skiplist;
    skiplist.add(0);
    skiplist.add(5);int x; 
    cin >> x;
    skiplist.erase(x);}/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

复杂度考量

skiplist跟平衡搜索树和哈希表的对比

1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差 不多。

• skiplist的优势是：
• a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
• b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。
• skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包 含的平均指针数目为1.33；

1. skiplist相比哈希表而言，就没有那么大的优势了。

• 哈希表平均时间复杂度是O(1)，比skiplist快。
• 哈希表空间消耗略多一点。
• skiplist优势如下：
• a、遍历数据有序
• b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
• c、哈希表扩容有性能损耗。
• d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。