c++如何实现一个跳表(Skip List)_c++平衡树的高效替代方案-C++-PHP中文网

c++如何实现一个跳表(Skip List)_c++平衡树的高效替代方案

穿越時空

发布： 2025-11-30 12:59:23

原创

401人浏览过

跳表是一种基于多层链表的动态数据结构，通过随机化层数实现平均O(log n)的查找、插入和删除性能；其核心由带前向指针数组的节点构成，利用头节点简化操作，从最高层开始逐层跳跃查找，插入时记录路径并更新各层指针，删除时断开连接并回收内存，同时可优化当前最大层数；相比平衡树，跳表代码更简洁、易于维护，且在并发场景下表现良好。

c++如何实现一个跳表(skip list)_c++平衡树的高效替代方案

跳表（Skip List）是一种基于概率的动态数据结构，能够以较低的实现复杂度达到与平衡树相近的性能。相比红黑树、AVL树等复杂的自平衡二叉搜索树，跳表在插入、删除和查找操作上平均时间复杂度均为 O(log n)，且代码更简洁、易于理解和维护。它通过多层链表实现快速“跳跃”，从而提升查询效率。

跳表的基本原理

跳表本质上是一个多层有序链表。底层（第0层）包含所有元素，每一层都是下一层的“快速通道”。每个节点有一定概率向上提升一层（通常为50%），形成索引。查找时从最高层开始，像二分查找一样向右、向下移动，直到找到目标值。

主要特点：

随机化层数：新节点的层数由随机函数决定，避免严格平衡带来的复杂调整。
前向指针数组：每个节点维护一个指针数组，指向每一层的下一个节点。
头节点简化操作：设置一个虚拟头节点，统一处理边界情况。

核心结构设计

定义跳表节点和主类结构：

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

// 跳表节点 struct SkipListNode { int val; std::vector forward; // 每一层的下一个节点指针 SkipListNode(int v, int level) : val(v), forward(level, nullptr) {} };

// 跳表主类 class SkipList { private: static const int MAX_LEVEL = 16; // 最大层数 SkipListNode* head; // 头节点 int currentLevel; // 当前最大有效层数

// 随机生成节点层数
int randomLevel() {
    int level = 1;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        ++level;
    }
    return level;
}

登录后复制

public: SkipList() : currentLevel(1) { head = new SkipListNode(-1, MAX_LEVEL); }

查找操作实现

从最高层开始，向右直到下一个节点值大于目标，然后下降一层继续，最终在底层判断是否存在。

bool search(int target) { SkipListNode* curr = head; for (int i = currentLevel - 1; i >= 0; --i) { while (curr->forward[i] && curr->forward[i]->val forward[i]; } } curr = curr->forward[0]; return curr && curr->val == target; }

插入操作实现

先查找路径并记录每层最后访问的节点，再随机生成新节点层数，更新各层指针。

BRANDMARK

AI帮你设计Logo、图标、名片、模板……等

180

查看详情

void add(int num) { std::vector update(MAX_LEVEL, head); SkipListNode* curr = head;

// 查找插入位置，记录每层最后一个小于num的节点
for (int i = currentLevel - 1; i >= 0; --i) {
    while (curr->forward[i] && curr->forward[i]->val < num) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

int newNodeLevel = randomLevel();
SkipListNode* newNode = new SkipListNode(num, newNodeLevel);

// 更新各层指针
for (int i = 0; i < newNodeLevel; ++i) {
    newNode->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = newNode;
}

// 更新当前最大层数
if (newNodeLevel > currentLevel) {
    currentLevel = newNodeLevel;
}

登录后复制

}

删除操作实现

查找目标节点，若存在则逐层断开连接，并回收内存。同时检查是否需要降低当前最大层数。

bool erase(int num) { std::vector update(MAX_LEVEL, nullptr); SkipListNode* curr = head;

for (int i = currentLevel - 1; i >= 0; --i) {
    while (curr->forward[i] && curr->forward[i]->val < num) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[0];
if (!curr || curr->val != num) return false;

// 断开各层指针
for (int i = 0; i < currentLevel; ++i) {
    if (update[i]->forward[i] != curr) break;
    update[i]->forward[i] = curr->forward[i];
}

delete curr;

// 降低当前层数（可选优化）
while (currentLevel > 1 && head->forward[currentLevel-1] == nullptr) {
    --currentLevel;
}

return true;

登录后复制

}

完整的析构函数可以遍历底层链表释放所有节点，防止内存泄漏。

跳表作为平衡树的替代方案，优势在于实现简单、并发友好（如ConcurrentSkipListMap）、支持范围查询高效。虽然最坏情况性能不如严格平衡树，但平均表现足够优秀，适合大多数场景。

基本上就这些。不复杂但容易忽略细节，比如随机层数控制和指针更新顺序。写好后多测几个边界用例即可稳定使用。

以上就是c++++如何实现一个跳表(Skip List)_c++平衡树的高效替代方案的详细内容，更多请关注php中文网其它相关文章！