c++实现跳表

原理

跳表（Skip List） 是一种随机化数据结构，用于高效查找、插入和删除，尤其适用于有序数据集合。相比链表，跳表通过多层索引结构加速查找，期望时间复杂度接近 O(log⁡n)。跳表的主要思想是：

• 底层链表存储所有数据元素，保持有序。
• 上层链表是稀疏索引，用于跳过部分节点，减少遍历的长度。

结构图

下面是一个跳表的结构示意：

Level 3:  [1] ----------------> [9]
Level 2:  [1] -----> [4] -----> [9]
Level 1:  [1] -----> [4] -----> [7] -----> [9]
Level 0:  [1] -> [2] -> [4] -> [5] -> [7] -> [8] -> [9]

如上图所示：

1. 每一层都是一个有序链表。
2. 每一层的节点是下一层的子集，存储重要的中间节点，形成分层索引。
3. 查找过程：从最高层开始，先向右移动，如果目标值超出范围，则向下移动到下一层。重复此过程直到找到目标节点。

优缺点

优点：

• 插入、删除和查找的期望时间复杂度为 O(log⁡n)。
• 实现简单，比红黑树和AVL树更容易理解和维护。

缺点：

• 需要额外的空间存储索引层节点。

代码示例（c++）

下面是一段简单的 C++ 跳表实现，包括节点结构定义、插入、查找和显示功能。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;class Node {
public:int value;vector<Node*> forward;  // 每层的前向指针Node(int val, int level) : value(val), forward(level + 1, nullptr) {}
};class SkipList {
private:int maxLevel;  // 跳表的最大层数float probability;  // 晋升概率Node* header;  // 头节点int currentLevel;  // 当前跳表的层数public:SkipList(int maxLevel, float probability) : maxLevel(maxLevel), probability(probability), currentLevel(0) {header = new Node(-1, maxLevel);  // 头节点初始化为-1srand(time(nullptr));  // 初始化随机数种子}// 随机生成节点的层数int randomLevel() {int lvl = 0;while ((rand() / double(RAND_MAX)) < probability && lvl < maxLevel) {lvl++;}return lvl;}// 插入新节点void insert(int value) {vector<Node*> update(maxLevel + 1);Node* current = header;// 从最高层向下查找插入位置for (int i = currentLevel; i >= 0; i--) {while (current->forward[i] && current->forward[i]->value < value) {current = current->forward[i];}update[i] = current;}// 在底层插入节点的位置current = current->forward[0];// 如果节点不存在，则插入新节点if (!current || current->value != value) {int lvl = randomLevel();if (lvl > currentLevel) {for (int i = currentLevel + 1; i <= lvl; i++) {update[i] = header;}currentLevel = lvl;}Node* newNode = new Node(value, lvl);for (int i = 0; i <= lvl; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}cout << "Inserted value: " << value << " at level: " << lvl << endl;}}// 查找节点bool search(int value) {Node* current = header;for (int i = currentLevel; i >= 0; i--) {while (current->forward[i] && current->forward[i]->value < value) {current = current->forward[i];}}current = current->forward[0];return current && current->value == value;}// 打印跳表结构void display() {for (int i = currentLevel; i >= 0; i--) {Node* current = header->forward[i];cout << "Level " << i << ": ";while (current) {cout << current->value << " ";current = current->forward[i];}cout << endl;}}
};int main() {SkipList skipList(4, 0.5);  // 最大层数为4，晋升概率为0.5skipList.insert(3);skipList.insert(6);skipList.insert(7);skipList.insert(9);skipList.insert(12);skipList.insert(19);cout << "Skip List Structure:" << endl;skipList.display();cout << "Search 7: " << (skipList.search(7) ? "Found" : "Not Found") << endl;cout << "Search 4: " << (skipList.search(4) ? "Found" : "Not Found") << endl;return 0;
}

代码解析

1. Node 类：
   • 表示跳表中的节点，包含节点的值和指向不同层节点的指针向量 forward。
2. SkipList 类：
   • 实现了跳表的主要功能，包括插入、查找和显示结构。
   • randomLevel：用于随机生成节点的层数，控制索引的稀疏程度。
   • insert：插入元素到跳表中，如果新节点的层数超过当前最大层数，则更新索引。
   • search：查找目标值是否存在。
3. 主函数：
   • 初始化跳表并插入若干元素，测试插入和查找功能。

运行结果

Inserted value: 3 at level: 0
Inserted value: 6 at level: 1
Inserted value: 7 at level: 2
Inserted value: 9 at level: 0
Inserted value: 12 at level: 1
Inserted value: 19 at level: 3
Skip List Structure:
Level 3: 19 
Level 2: 7 19 
Level 1: 6 12 19 
Level 0: 3 6 7 9 12 19 
Search 7: Found
Search 4: Not Found

总结

• 时间复杂度：查找、插入、删除的期望时间复杂度为 O(log⁡n)O(\log n)O(logn)。
• 空间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)，因为每个节点可能会出现在多层中。

跳表的实现简单且高效，常用于 Redis 等数据库的有序集合。