跳跃表SkipList(简单的C++实现)

**跳跃表SkipList**

跳跃表是一种高效的数据结构，用于快速查找、插入和删除元素。它通过在原始链表上构建多层索引来实现这一点，每一层索引都代表一个随机生成的高度值。这种设计使得跳跃表能够以 O(log n) 的时间复杂度进行查找、插入和删除操作。

**SkipList类定义**

cppclass SkipList {
private:
 int maxLevel; // 最大层级数 int headNode; // 头结点 Node* head; // 头结点指针public:
 SkipList(int maxLevel) : maxLevel(maxLevel), headNode(0), head(nullptr) {}

 ~SkipList() {
 for (int i =0; i <= maxLevel; i++) {
 delete[] head[i];
 }
 }

 // 插入新元素 void insert(int key, int value);

 // 查找元素 Node* search(int key);

 // 删除元素 void remove(int key);
};

cppclass Node {
public:
 int key; // 键值 int value; // 值 Node* next[maxLevel +1]; // 下一个结点指针 Node() : key(0), value(0) {
 for (int i =0; i <= maxLevel; i++) {
 next[i] = nullptr;
 }
 }

 ~Node() {}
};

cppSkipList::SkipList(int maxLevel) : maxLevel(maxLevel), headNode(0), head(nullptr) {
 // 初始化头结点 head = new Node[maxLevel +1];
 for (int i =0; i <= maxLevel; i++) {
 head[i] = nullptr;
 }
}

cppvoid SkipList::insert(int key, int value) {
 //生成随机高度值 int level = rand() % (maxLevel +1);
 Node* newNode = new Node();
 newNode->key = key;
 newNode->value = value;

 // 插入新元素 Node** update[maxLevel +1];
 for (int i =0; i <= maxLevel; i++) {
 update[i] = &head[i];
 }
 for (int i = level; i >=0; i--) {
 while (*update[i] && (*update[i])->key < key) {
 update[i] = &(*update[i])->next[i];
 }
 newNode->next[i] = *update[i];
 *update[i] = newNode;
 }

 // 更新头结点 if (level > headNode) {
 headNode = level;
 }
}

cppNode* SkipList::search(int key) {
 Node** update[maxLevel +1];
 for (int i =0; i <= maxLevel; i++) {
 update[i] = &head[i];
 }

 // 搜索元素 for (int i = maxLevel; i >=0; i--) {
 while (*update[i] && (*update[i])->key < key) {
 update[i] = &(*update[i])->next[i];
 }
 if (*update[i] && (*update[i])->key == key) {
 return *update[i];
 }
 }

 // 元素不存在 return nullptr;
}

cppvoid SkipList::remove(int key) {
 Node** update[maxLevel +1];
 for (int i =0; i <= maxLevel; i++) {
 update[i] = &head[i];
 }

 // 搜索元素 Node* node = search(key);
 if (node && node->key == key) {
 // 删除元素 for (int i =0; i <= maxLevel; i++) {
 if (update[i] != nullptr && update[i]->next[i] == node) {
 update[i]->next[i] = node->next[i];
 }
 }

 // 更新头结点 if (headNode >0 && head[headNode] == nullptr) {
 headNode--;
 }
 }
}

cppint main() {
 SkipList skipList(3);

 // 插入元素 skipList.insert(5, "five");
 skipList.insert(10, "ten");
 skipList.insert(15, "fifteen");

 // 查找元素 Node* node = skipList.search(10);
 if (node) {
 std::cout << "Key: " << node->key << ", Value: " << node->value << std::endl;
 }

 // 删除元素 skipList.remove(10);

 return0;
}