根据数据规模确定索引层数，根据概率确定插入数据索引层数。

每插入一个元素，有概率生成$x$级索引，$0\le x\le p$，若当前跳表插入元素个数为$n$，$p$是满足$2^p\ge n$最小的数。生成$x$级索引的概率是$\frac{1}{2^x},(x>0)$，不生成索引$(x=0)$概率为$\frac{1}{2^p}$。

#include <bits/stdc++.h>

using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

#define NINF 0xf3f3f3f3
class Skiplist {
public:
    struct Node {
        int val;
        Node* down;
        Node* right;
        Node(int val, Node* down=NULL, Node* right=NULL):val(val),down(down),right(right) {}
    };
    int val_cnt = 0;
    int p = 0; // samllest p, that 2^p >= val_cnt
    vector<Node*> head; // size = p+1
    Skiplist() {
        head.emplace_back(new Node(NINF));
    }
    
    bool search(int target) {
        int lev = head.size()-1;
        // 高层索引头为空，移除
        while (lev && head[lev]->right == NULL) {
            delete head[lev];
            head.pop_back();
            lev--;
        }
        Node* cur = head[lev];
        while (cur) {
            // 右侧节点小于target 右移动
            while (cur->right && cur->right->val < target) cur = cur->right;
            // 右侧为target，找到答案
            if (cur->right && cur->right->val == target) return true;
            //否则进入下一层索引
            cur = cur->down;
        }
        return false;
    }
    
    void add(int num) {
        val_cnt++;
        while ((1<<p) < val_cnt) p++;
        // 获取建立索引层数，概率算法
        int idx = rand_idx();
        // 当前索引头不够
        int lev = head.size()-1;
        while (lev < idx) {
            head.push_back(new Node(NINF, head.back()));
            lev++;
        }
        Node* cur = head[lev], *up = NULL;
        while (cur) {
            // 右侧节点小于num 右移动
            while (cur->right && cur->right->val < num) cur = cur->right;
            // idx及以下建立索引
            if (lev<=idx) {
                cur->right =  new Node(num, NULL, cur->right);
                if (up != NULL) up->down = cur->right;
                up = cur->right;
            }
            //进入下一层索引
            cur = cur->down;
            lev--;
        }
    }
    
    bool erase(int num) {
        int lev = head.size()-1;
        // 高层索引头为空，移除
        while (lev && head[lev]->right == NULL) {
            delete head[lev];
            head.pop_back();
            lev--;
        }
        bool rt = false;
        Node* cur = head[lev];
        while (cur) {
            // 右侧节点小于num 右移动
            while (cur->right && cur->right->val < num) cur = cur->right;
            // 右侧为num，删除之
            if (cur->right && cur->right->val == num) {
                rt = true;
                Node* e = cur->right;
                cur->right = e->right;
                delete e;
            }
            //否则进入下一层索引
            cur = cur->down;
        }

        val_cnt--;
        while (p && (1<<p-1) >= val_cnt) p--;

        return rt;
    }
    void awesome_print() {
        int lev = head.size()-1;
        cout << "val_cnt: " << val_cnt << "\\tlev: " << lev << "\\tp: " << p << endl;
        map<Node*,int> mp;
        set<Node*> st;
        for (int i=lev; i>=0; i--) {
            Node* cur = head[i];
            while (cur) {
                if (!st.count(cur)) {
                    Node* t = cur;
                    st.insert(t);
                    int c = 0;
                    while (t->down) st.insert(t = t->down), c++;
                    mp[t] = c;
                }
                cur = cur->right;
            }
        }
        function<void(int)> dfs = [&](int l) {
            if (l > lev) return;
            dfs(l+1);
            Node *t = head[0];
            while (t) {
                cout << "\\t";
                if (l<=mp[t]) {
                    if (t->val == NINF) {
                        cout << "HEAD";
                    } else {
                        cout << t->val;
                    }
                }
                t = t->right;
            }
            cout << endl;
        };
        dfs(0);
    }
private:
    int rand_idx() {
        int sz = 1<<p;
        // int v = rand()%sz;
        int v = random(0, sz-1);
        int rt = 0;
        while (v) {
            rt++;
            v >>= 1;
        }
        /*
            sz = 8
            0 : 0
            1 : 1
            2 : 2 3
            4 : 4 5 6 7
        */ 
        return rt;
    }
};

void sol() {
    Skiplist sl;
    vector<int> a;
    for (int i=0; i<20; i++) {
        a.push_back(random(0, 100));
    }
    cout << "add seq " << a << endl;
    for (int i:a) {
        sl.add(i);
        cout << "add " << i << endl;
        sl.awesome_print();
    }
    random_shuffle(a.begin(), a.end());
    cout << "del seq " << a << endl;
    for (int i:a) {
        sl.erase(i);
        cout << "erase " << i << endl;
        sl.awesome_print();
    }
}

int main() {
    sol();
    return 0;
}

• print