跳表

介绍

• 跳表全称叫做跳跃表，简称跳表。
• 跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。
• 跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
• 跳表可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis中有用到。
• 跳表采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。
• 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候已经十分接近要查找的元素的位置。
• 跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。

实现

跳表层数

由于跳表是多层链表结构，层数需要指定，即跳表的最大高度，取经验值level = 8;

static const int level = 8;  // 层数，经验值 8

跳表节点

在跳表的每一层都由头节点引出一条链表，所以一个跳表节点需要：

• 节点值；
• next数组，存储该节点在每一层的next指针，没有就是空指针；

// 定义跳表节点
struct Node {
    int val;
    
    // 记录节点在每一层的 next，next[i] 表示当前节点第 i 层的 next
    vector<Node*> next;

    Node(int _val) : val(_val) { next.resize(level, nullptr); }
} *head;  // 定义头节点 head

跳表结构

• 一个跳表类中成员函数一般就是查找、插入、删除操作；
• 层索引是从最下层到最上层，0~level-1;
• 我们统一定义一个辅助的查询函数find()，用来找到每一层中小于目标值的最大的节点；
• 每一层的查找、插入、删除操作同于操作普通链表；
• 插入操作时从下往上遍历每一层，每一层有50%的概率插入新节点，第0层一定是含有所有节点；

class Skiplist {
public:
    // 构造函数创建头节点
    Skiplist() {
        head = new Node(-1);
    }
	
    // 析构函数删除头节点
    ~Skiplist() {
        delete head;
    }

    // 辅助函数：找到每一层(层索引i)中小于目标值 target 的最大节点 pre[i]
    void find(int target, vector<Node*>& pre) {
        auto p = head;
        // 从头节点开始遍历，从上层往下层找
        for (int i = level - 1; i >= 0; --i) {
            while (p->next[i] && p->next[i]->val < target) {
                p = p->next[i];
            }
            pre[i] = p;
        }
    }

    // 从跳表中查找 target
    bool search(int target) {
        // 先找到每一层 i 小于目标值 target 的最大节点 pre[i]
        vector<Node*> pre(level);
        find(target, pre);

        auto p = pre[0]->next[0];
        return p && p->val == target;
    }

    // 向跳表中插入元素 num
    void add(int num) {
        // 先找到每一层 i 小于目标值 target 的最大节点 pre[i]
        vector<Node*> pre(level);
        find(num, pre);

        auto p = new Node(num); 
        // 从下往上遍历每一层，每一层是单链表的插入逻辑
        for (int i = 0; i < level; i++) {
            p->next[i] = pre[i]->next[i]; 
            pre[i]->next[i] = p;
            // 每一层有 50% 的概率不插入新节点
            if (rand() % 2) break;  
        }
    }

    // 从跳表中删除 num
    bool erase(int num) {
        // 先找到每一层 i 小于目标值 target 的最大节点 pre[i]
        vector<Node*> pre(level);
        find(num, pre);

        // 先判断 num 是否存在，不存在直接返回 false，只需在第0层判断
        auto p = pre[0]->next[0];
        if (!p || p->val != num) return false;

        // 删除每一层的 num，如果 pre[i]->next[i] == p 说明第 i 层存在 p
        for (int i = 0; i < level && pre[i]->next[i] == p; ++i) {
            pre[i]->next[i] = p->next[i];
        }

        delete p;

        return true;
    }
};

---

【参考资料】力扣题解-设计跳表