c++实现跳表

原理

跳表（Skip List） 是一种随机化数据结构，用于高效查找、插入和删除，尤其适用于有序数据集合。相比链表，跳表通过多层索引结构加速查找，期望时间复杂度接近 O(log⁡n)。跳表的主要思想是：

• 底层链表存储所有数据元素，保持有序。
• 上层链表是稀疏索引，用于跳过部分节点，减少遍历的长度。

结构图

下面是一个跳表的结构示意：

Level 3:  [1] ----------------> [9]
Level 2:  [1] -----> [4] -----> [9]
Level 1:  [1] -----> [4] -----> [7] -----> [9]
Level 0:  [1] -> [2] -> [4] -> [5] -> [7] -> [8] -> [9]

如上图所示：

1. 每一层都是一个有序链表。
2. 每一层的节点是下一层的子集，存储重要的中间节点，形成分层索引。
3. 查找过程：从最高层开始，先向右移动，如果目标值超出范围，则向下移动到下一层。重复此过程直到找到目标节点。

优缺点

优点：

• 插入、删除和查找的期望时间复杂度为 O(log⁡n)。
• 实现简单，比红黑树和AVL树更容易理解和维护。

缺点：

• 需要额外的空间存储索引层节点。

代码示例（c++）

下面是一段简单的 C++ 跳表实现，包括节点结构定义、插入、查找和显示功能。

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

class Node {
public:
    int value;
    vector<Node*> forward;  // 每层的前向指针

    Node(int val, int level) : value(val), forward(level + 1, nullptr) {}
};

class SkipList {
private:
    int maxLevel;  // 跳表的最大层数
    float probability;  // 晋升概率
    Node* header;  // 头节点
    int currentLevel;  // 当前跳表的层数

public:
    SkipList(int maxLevel, float probability) 
        : maxLevel(maxLevel), probability(probability), currentLevel(0) {
        header = new Node(-1, maxLevel);  // 头节点初始化为-1
        srand(time(nullptr));  // 初始化随机数种子
    }

    // 随机生成节点的层数
    int randomLevel() {
        int lvl = 0;
        while ((rand() / double(RAND_MAX)) < probability && lvl < maxLevel) {
            lvl++;
        }
        return lvl;
    }

    // 插入新节点
    void insert(int value) {
        vector<Node*> update(maxLevel + 1);
        Node* current = header;

        // 从最高层向下查找插入位置
        for (int i = currentLevel; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        // 在底层插入节点的位置
        current = current->forward[0];

        // 如果节点不存在，则插入新节点
        if (!current || current->value != value) {
            int lvl = randomLevel();

            if (lvl > currentLevel) {
                for (int i = currentLevel + 1; i <= lvl; i++) {
                    update[i] = header;
                }
                currentLevel = lvl;
            }

            Node* newNode = new Node(value, lvl);
            for (int i = 0; i <= lvl; i++) {
                newNode->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = newNode;
            }
            cout << "Inserted value: " << value << " at level: " << lvl << endl;
        }
    }

    // 查找节点
    bool search(int value) {
        Node* current = header;
        for (int i = currentLevel; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return current && current->value == value;
    }

    // 打印跳表结构
    void display() {
        for (int i = currentLevel; i >= 0; i--) {
            Node* current = header->forward[i];
            cout << "Level " << i << ": ";
            while (current) {
                cout << current->value << " ";
                current = current->forward[i];
            }
            cout << endl;
        }
    }
};

int main() {
    SkipList skipList(4, 0.5);  // 最大层数为4，晋升概率为0.5

    skipList.insert(3);
    skipList.insert(6);
    skipList.insert(7);
    skipList.insert(9);
    skipList.insert(12);
    skipList.insert(19);

    cout << "Skip List Structure:" << endl;
    skipList.display();

    cout << "Search 7: " << (skipList.search(7) ? "Found" : "Not Found") << endl;
    cout << "Search 4: " << (skipList.search(4) ? "Found" : "Not Found") << endl;

    return 0;
}

代码解析

1. Node 类：
   • 表示跳表中的节点，包含节点的值和指向不同层节点的指针向量 forward。
2. SkipList 类：
   • 实现了跳表的主要功能，包括插入、查找和显示结构。
   • randomLevel：用于随机生成节点的层数，控制索引的稀疏程度。
   • insert：插入元素到跳表中，如果新节点的层数超过当前最大层数，则更新索引。
   • search：查找目标值是否存在。
3. 主函数：
   • 初始化跳表并插入若干元素，测试插入和查找功能。

运行结果

Inserted value: 3 at level: 0
Inserted value: 6 at level: 1
Inserted value: 7 at level: 2
Inserted value: 9 at level: 0
Inserted value: 12 at level: 1
Inserted value: 19 at level: 3
Skip List Structure:
Level 3: 19 
Level 2: 7 19 
Level 1: 6 12 19 
Level 0: 3 6 7 9 12 19 
Search 7: Found
Search 4: Not Found

总结

• 时间复杂度：查找、插入、删除的期望时间复杂度为 O(log⁡n)O(\log n)O(logn)。
• 空间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，因为每个节点可能会出现在多层中。

跳表的实现简单且高效，常用于 Redis 等数据库的有序集合。