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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-04

浏览次数：次

返回列表

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

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

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

跳表基本原理

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

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

核心数据结构设计

定义跳表节点：

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

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

示例代码片段：

#include <vector>
#include <random>
#include <cstdlib>
<p>template<typename K, typename V>
class SkipListNode {
public:
K key;
V value;
std::vector<SkipListNode*> forward;</p><pre class="brush:php;toolbar:false;">SkipListNode(K k, V v, int level)
    : key(k), value(v), forward(level, nullptr) {}

};

跳表类主体实现

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

Tunee AI

新一代AI音乐智能体

1104 查看详情 Tunee AI

关键操作说明：

随机层级生成： 使用随机数决定新节点应有几层，概率逐层减半。
查找： 从最高层开始，向右直到下一个节点大于目标，然后下降一层，重复直到找到或失败。
插入： 先查找路径并记录每层最后一个小于目标的节点（update 数组），再创建新节点并链接到各层。
删除： 查找节点，若存在则断开其在各层的指针，并释放内存。

部分实现示例：

template<typename K, typename V>
class SkipList {
private:
    int maxLevel;
    int currentLevel;
    SkipListNode<K, V>* header;
    std::random_device rd;
    std::mt19937 gen;
    std::uniform_int_distribution<int> dis;
<pre class="brush:php;toolbar:false;">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<SkipListNode<K,V>*> update(maxLevel);
    SkipListNode<K,V>* 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<K,V>* newNode = new SkipListNode<K,V>(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<K,V>* 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<SkipListNode<K,V>*> update(maxLevel);
    SkipListNode<K,V>* 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--;
    }
}

};