数据结构-跳表

简介

跳表（Skip List）是一种高效的数据结构，用于在有序集合中实现快速查找、插入和删除操作。

它最早由 William Pugh 在其 1990 年的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出，它通过在链表的基础上引入多层索引的方式，将单链表的线性查找提升为接近二分查找的性能，同时保持了链表操作的简单性。

在跳表的最底层是一个普通的有序链表，存储所有数据元素，在底层链表之上，跳表构建了多层索引链表。每层索引链表是下一层链表的“稀疏”子集，即只包含部分节点。

新元素被插入时，会根据一定的概率决定它是否出现在更高层索引中。通常，这种概率是固定的（例如 50%），即每个节点以 1/2 的概率向上晋升到更高层。

跳表操作

查找

1. 从最高层索引链表开始，向右查找，直到找到一个比目标值大的节点。

2. 如果能直接找到，则直接返回。如果右边节点比目标值大，则往下一层。如果到了当层最右边，则往下一层，重复往上

3. 如果查找过程遇到空节点，则说明目标节点不存在。

例如，如果要查找16，则查找路径为[1,13,13,13,16]

如果要查找23，则查找路径为[1,13,21,22,22,NUL]

插入

1. 首先按照查找的流程定位新元素应该插入的位置，注意，我们必须是在最底层插入，因为底层是原始数据，底层之上都是索引。

2. 根据随机概率决定新节点需要晋升到哪些层级，即是否将其增加到索引层中。

3. 更新各层级的指针，确保跳表的结构正确。

删除

1. 按照查找的流程定位目标节点。

2. 从底层开始逐层删除目标节点，如果待删除的节点在更高层中出现，则往上继续删除。

时空复杂度

• 平均时间复杂度：查找、插入、删除操作的平均时间复杂度均为 $O(\log n)$ ，其中 n 是跳表中元素的数量，这是因为跳表的层数期望为$O(\log n)$ ，且每一层的查找步数也是 $O(\log n)$ 。
• 空间复杂度：跳表的空间复杂度为 $O(n)$ ，因为每一层索引的节点数量是底层节点数量的固定比例（例如 50%）。

代码实现

#include<iostream>
#include<vector>
#include<stack>
#include<cstdlib>
#include<ctime>
using namespace std;


struct Node {
    int value;
    Node* right;
    Node* down;
    Node(Node* right, Node* down, int value)
        : value(value), right(right), down(down) {
    }
};

class Skiplist {
private:
    Node* head;

public:
    Skiplist() {
        srand(time(0));
        // 空的头节点，方便作为边界
        head = new Node(nullptr, nullptr, -1);
    }

    bool search(int target) {
        Node* p = head;
        while (p) {
            // 在同层之间跳
            while (p->right && p->right->value < target) {
                p = p->right;
            }
            // 到达了同层最右边，或者本层右边元素大于目标值，则往下继续探索
            if (p->right == nullptr || target < p->right->value) {
                p = p->down;
            }else {
                return true;
            }
        }
        return false;
    }

    void add(int num) {
        // tmpPathList 中存放的是访问路径
        stack<Node*> tmpPathList;
        Node* p = head;
        while (p) {
            // 在同层之间跳
            while (p->right && p->right->value < num) {
                p = p->right;
            }
            tmpPathList.push(p);
            // 到达了同层最右边，或者本层右边元素大于目标值，则往下继续探索
            p = p->down;
        }
        // 从访问路径中最下面的节点开始往上，通过随机数来决定是否将新的节点增加到本层
        bool needInsert = true;
        Node* topNode, * lastDownNode = nullptr;
        while (needInsert && !tmpPathList.empty()) {
            topNode = tmpPathList.top();
            tmpPathList.pop();
            topNode->right = new Node(topNode->right, lastDownNode, num);
            lastDownNode = topNode->right;
            needInsert = rand() & 1;
        }
        // 回到第一层，则向上增加一层
        if (needInsert) {
            head = new Node(new Node(nullptr, lastDownNode, num), head, -1);
        }
    }

    bool erase(int num) {
        Node* p = head;
        Node* deleteNode;
        bool isDelete = false;
        while (p) {
            // 在同层之间跳
            while (p->right && p->right->value < num) {
                p = p->right;
            }
            // 到达了同层最右边，或者本层右边元素大于目标值，则往下继续探索
            if (p->right == nullptr || num < p->right->value) {
                p = p->down;
            }
            else if (p->right != nullptr && p->right->value == num) {
                // 找到目标值
                deleteNode = p->right;
                p->right = deleteNode->right;
                p = p->down;
                delete deleteNode;
                isDelete = true;
            }
        }
        return isDelete;
    }
};


int main() {
    Skiplist * s = new Skiplist();
    s->add(1);
    s->add(2);
    s->add(3);
    s->search(3);
    return 0;
}