高效查找的利器：C++跳表数据结构详解（从零实现跳表教程）

为什么使用跳表？

相比红黑树等平衡树结构，跳表具有以下优势：

• 实现简单，无需复杂的旋转操作。
• 天然支持范围查询（如查找 [a, b] 之间的所有元素）。
• 并发性能好，在多线程环境下更容易实现无锁或细粒度锁。

Redis 的有序集合（ZSET）就使用了跳表作为底层数据结构之一！因此掌握 C++跳表实现 对理解高性能系统非常有帮助。

C++ 跳表实现步骤

我们将逐步构建一个支持插入、查找和删除操作的跳表。

1. 定义节点结构

每个节点包含一个值和一个指针数组，指向各层的下一个节点：

struct SkipListNode {    int value;    std::vector<SkipListNode*> forward; // 每一层的下一个节点指针    SkipListNode(int val, int level) : value(val), forward(level, nullptr) {}};

2. 跳表类定义

class SkipList {private:    static const int MAX_LEVEL = 16; // 最大层数    static const double PROBABILITY = 0.5; // 随机提升概率    SkipListNode* header; // 头节点（哨兵）    int currentLevel;     // 当前最大层数    int randomLevel(); // 生成随机层数public:    SkipList();    ~SkipList();    void insert(int value);    bool search(int value);    void remove(int value);    void display(); // 打印跳表（用于调试）};

3. 随机层数生成函数

新插入的节点有 50% 概率提升一层，最多不超过 MAX_LEVEL：

int SkipList::randomLevel() {    int level = 1;    while ((rand() / (double)RAND_MAX) < PROBABILITY && level < MAX_LEVEL) {        level++;    }    return level;}

4. 插入操作

插入时需记录每层的前驱节点，以便更新指针：

void SkipList::insert(int value) {    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);    SkipListNode* current = header;    // 从最高层开始向下搜索    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->forward[i] != nullptr &&               current->forward[i]->value < value) {            current = current->forward[i];        }        update[i] = current;    }    // 检查是否已存在    if (current->forward[0] != nullptr && current->forward[0]->value == value) {        return; // 不允许重复    }    int newLevel = randomLevel();    if (newLevel > currentLevel) {        for (int i = currentLevel; i < newLevel; i++) {            update[i] = header;        }        currentLevel = newLevel;    }    SkipListNode* newNode = new SkipListNode(value, newLevel);    for (int i = 0; i < newLevel; i++) {        newNode->forward[i] = update[i]->forward[i];        update[i]->forward[i] = newNode;    }}

5. 查找与删除

查找和删除逻辑类似，都需要从顶层开始逐层下降：

bool SkipList::search(int value) {    SkipListNode* current = header;    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->forward[i] != nullptr &&               current->forward[i]->value < value) {            current = current->forward[i];        }    }    current = current->forward[0];    return (current != nullptr && current->value == value);}void SkipList::remove(int value) {    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);    SkipListNode* current = header;    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->forward[i] != nullptr &&               current->forward[i]->value < value) {            current = current->forward[i];        }        update[i] = current;    }    current = current->forward[0];    if (current != nullptr && current->value == value) {        for (int i = 0; i < currentLevel; i++) {            if (update[i]->forward[i] != current) break;            update[i]->forward[i] = current->forward[i];        }        delete current;        // 更新当前层数        while (currentLevel > 1 && header->forward[currentLevel - 1] == nullptr) {            currentLevel--;        }    }}

完整使用示例

#include <iostream>#include <vector>#include <cstdlib>#include <ctime>// ... 上述 SkipListNode 和 SkipList 类定义 ...int main() {    srand(time(0)); // 初始化随机种子    SkipList sl;    sl.insert(3);    sl.insert(6);    sl.insert(7);    sl.insert(9);    sl.insert(12);    std::cout << "Search 6: " << (sl.search(6) ? "Found" : "Not Found") << std::endl;    std::cout << "Search 5: " << (sl.search(5) ? "Found" : "Not Found") << std::endl;    sl.remove(6);    std::cout << "After removing 6, search 6: "               << (sl.search(6) ? "Found" : "Not Found") << std::endl;    return 0;}

总结

通过本教程，我们详细讲解了 跳表数据结构 的原理，并用 C++ 从零实现了插入、查找和删除操作。跳表不仅性能优秀，而且代码简洁，是替代平衡树的绝佳选择。

无论你是准备面试，还是想深入理解 Redis 等系统内部机制，掌握 C++有序集合 的跳表实现都极具价值。希望这篇 跳表教程 能帮助你轻松入门这一高效数据结构！

提示：实际项目中可考虑使用智能指针管理内存，避免内存泄漏。