C++怎么实现一个跳表_C++实现效率媲美红黑树的动态查找数据结构

跳表是一种基于多层链表的动态查找结构，通过随机化分层实现平均O(log n)时间复杂度的插入、删除和查找操作。其核心是每个节点包含多个后继指针，形成逐层稀疏索引，查找时从顶层开始逐层下降，提升效率。相比红黑树，跳表实现更简单，逻辑清晰，尤其在并发环境下优势明显。C++中可通过模板类实现，维护头节点、最大层级和随机层数生成器，关键操作包括插入时记录更新路径、删除时调整各层指针，并动态维护当前最大层级。虽然最坏情况为O(n)，但实际性能接近平衡树，适合大数据量或高并发场景，可作为std::map的替代方案。

跳表（Skip List）是一种基于链表的数据结构，通过多层索引提升查找效率，平均时间复杂度为 O(log n)，最坏情况也是 O(n)，但实际表现接近平衡树。相比红黑树，跳表实现更简单，插入、删除和查找逻辑清晰，且在并发环境下更容易处理。C++ 中实现跳表，可以达到与 STL 中 std::map（基于红黑树）相近的性能。

跳表基本原理

跳表本质是带多级指针的有序链表。每一层都是下一层的“快速通道”。底层包含所有元素，上层以一定概率（通常为 50%）向上提升节点，形成稀疏索引。

查找时从顶层开始，横向移动到小于目标的最大值，再下降一层继续，直到底层找到目标或确定不存在。

核心数据结构设计

每个节点包含一个值（key）、一个存储各层后继指针的数组（或 vector），以及可选的 value（用于 map 场景）。

立即学习“C++免费学习笔记（深入）”；

层级数在节点创建时随机生成，控制最大层数（如 16 或 32）防止无限增长。

示例代码片段：

#include 
#include 
#include 
template
class SkipListNode {
public:
K key;
V value;
std::vector forward;
SkipListNode(K k, V v, int level)
    : key(k), value(v), forward(level, nullptr) {}
};

跳表类主体实现
需要维护最大层级、当前最大层级、头节点指针，以及用于生成随机层级的工具。

							

								
								

									花生AI
									
B站推出的AI视频创作工具
								
								下载 
							
						
关键操作说明：


随机层级生成： 使用随机数决定新节点应有几层，概率逐层减半。

查找： 从最高层开始，向右直到下一个节点大于目标，然后下降一层，重复直到找到或失败。

插入： 先查找路径并记录每层最后一个小于目标的节点（update 数组），再创建新节点并链接到各层。

删除： 查找节点，若存在则断开其在各层的指针，并释放内存。

部分实现示例：
template
class SkipList {
private:
    int maxLevel;
    int currentLevel;
    SkipListNode* header;
    std::random_device rd;
    std::mt19937 gen;
    std::uniform_int_distribution dis;
int randomLevel() {
    int lvl = 1;
    while (dis(gen) < 0.5 && lvl < maxLevel) {
        lvl++;
    }
    return lvl;
}
public:
SkipList(int maxLvl = 16) 
: maxLevel(maxLvl), currentLevel(1), gen(rd()), dis(0, 1) {
header = new SkipListNode(K(), V(), maxLevel);
}
void insert(K key, V value) {
    std::vector*> update(maxLevel);
    SkipListNode* current = header;

    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current->forward[i] != nullptr &&
               current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];

    if (current != nullptr && current->key == key) {
        current->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(key, value, newLevel);
    for (int i = 0; i < newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

bool search(K key, V& value) {
    SkipListNode* current = header;
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current->forward[i] != nullptr &&
               current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }
    current = current->forward[0];
    if (current != nullptr && current->key == key) {
        value = current->value;
        return true;
    }
    return false;
}

void remove(K key) {
    std::vector*> update(maxLevel);
    SkipListNode* current = header;

    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current->forward[i] != nullptr &&
               current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];
    if (current == nullptr || current->key != key) return;

    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--;
    }
}
};

性能对比与使用建议
跳表在平均情况下插入、删除、查找均为 O(log n)，常数因子略高于红黑树，但实现更简洁，调试更容易。STL 的 std::map 是红黑树，而跳表适合需要自定义排序或更高并发性能的场景。
实际测试中，小数据量下红黑树稍快，大数据量或频繁插入删除时，跳表性能接近甚至优于手写不优的平衡树。
若追求极致性能，可结合缓存友好设计（如扁平化节点存储），或使用 lock-free 跳表实现高并发有序集合。
基本上就这些，跳表是一个值得掌握的高效动态查找结构。不复杂但容易忽略细节，比如随机层数控制和指针更新顺序。正确实现后，完全可以作为红黑树的替代方案。