C++怎么实现一个跳表(Skip List)_C++数据结构与概率性算法设计_技术教程

跳表通过多层链表和随机层数实现高效查找，平均时间复杂度为O(log n)。结构包含带多个后继指针的节点，头节点维护最大层数，插入时以概率决定节点层数，查找时从高层向下逐层逼近目标，删除和插入操作需更新各层指针，最终通过析构函数释放内存。该结构相比平衡树更易实现，适合替代有序链表进行快速动态操作。

跳表（Skip List）是一种基于链表的数据结构，通过多层索引提升查找效率，平均时间复杂度为 O(log n)。它用概率方式决定节点层数，相比平衡树实现更简单，适合替代有序链表进行快速查找、插入和删除操作。C++ 中可以通过类封装实现一个线程不安全但功能完整的跳表。

跳表基本结构设计

每个跳表节点包含多个后继指针，层数随机生成。定义节点结构时使用动态数组存储 forward 指针。

struct SkipListNode { int key; int value; int level; // 当前节点实际层数 std::vector forward;

SkipListNode(int k, int v, int lvl)
    : key(k), value(v), level(lvl), forward(lvl, nullptr) {}

};

跳表主体维护最大层数、当前最大层数和头节点指针：

class SkipList { private: static const int MAX_LEVEL = 16; // 最大层数限制 SkipListNode* head; int currentMaxLevel; std::default_random_engine rng; std::uniform_real_distribution dist;

public: SkipList() : currentMaxLevel(1), rng(std::random_device{}()), dist(0.0, 1.0) { head = new SkipListNode(-1, -1, MAX_LEVEL); }

~SkipList();
bool search(int key, int& value);
bool insert(int key, int value);
bool remove(int key);
void display();

};

随机层数生成与查找路径记录

插入新节点前需要确定其层数，通常以 50% 概率逐层上升，直到达到上限或随机失败。

int randomLevel() { int lvl = 1; while (dist(rng)

查找过程中要记录每一层最后访问的节点，用于后续插入或删除操作的指针更新。

std::vector update(MAX_LEVEL, nullptr); SkipListNode* curr = head;

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

插入与删除操作实现

插入操作：先查找位置，若键已存在则更新值；否则生成新节点并链接到各层。

bool insert(int key, int value) { std::vector update(MAX_LEVEL, nullptr); SkipListNode* curr = head;

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

curr = curr->forward[0];
if (curr && curr->key == key) {
    curr->value = value;
    return true;
}

int newLevel = randomLevel();
if (newLevel > currentMaxLevel) {
    for (int i = currentMaxLevel; i < newLevel; i++)
        update[i] = head;
    currentMaxLevel = 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;
}

return true;

}

删除操作：查找到节点后，在每一层将其前后节点连接，并释放内存。

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

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

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

for (int i = 0; i < currentMaxLevel; i++) {
    if (update[i]->forward[i] != curr) break;
    update[i]->forward[i] = curr->forward[i];
}

delete curr;

while (currentMaxLevel > 1 && head->forward[currentMaxLevel - 1] == nullptr)
    currentMaxLevel--;

return true;

}

完整功能与测试输出

提供 search 和 display 方法验证正确性：

bool search(int key, int& value) { SkipListNode* curr = head; for (int i = currentMaxLevel - 1; i >= 0; i--) { while (curr->forward[i] != nullptr && curr->forward[i]->key forward[i]; } curr = curr->forward[0]; if (curr && curr->key == key) { value = curr->value; return true; } return false; }

void display() { for (int i = currentMaxLevel - 1; i >= 0; i--) { std::cout forward[i]; while (p) { std::cout key value forward[i]; } std::cout

析构函数释放所有节点：

~SkipList() { SkipListNode* curr = head; while (curr) { SkipListNode* next = curr->forward[0]; delete curr; curr = next; } }

基本上就这些。跳表结合了链表的灵活性和二分查找的思想，用空间换时间，实现比红黑树简单得多，适合学习概率性数据结构的设计思路。