asp.net网站开发教程,广告平面设计图片,石材石料网站搭建教程,南宁专门建网站的公司原理
跳表#xff08;Skip List#xff09; 是一种随机化数据结构#xff0c;用于高效查找、插入和删除#xff0c;尤其适用于有序数据集合。相比链表#xff0c;跳表通过多层索引结构加速查找#xff0c;期望时间复杂度接近 O(logn)。跳表的主要思想是#xff1a;
…原理
跳表Skip List 是一种随机化数据结构用于高效查找、插入和删除尤其适用于有序数据集合。相比链表跳表通过多层索引结构加速查找期望时间复杂度接近 O(logn)。跳表的主要思想是
底层链表存储所有数据元素保持有序。上层链表是稀疏索引用于跳过部分节点减少遍历的长度。
结构图
下面是一个跳表的结构示意
Level 3: [1] ---------------- [9]
Level 2: [1] ----- [4] ----- [9]
Level 1: [1] ----- [4] ----- [7] ----- [9]
Level 0: [1] - [2] - [4] - [5] - [7] - [8] - [9]如上图所示
每一层都是一个有序链表。每一层的节点是下一层的子集存储重要的中间节点形成分层索引。查找过程从最高层开始先向右移动如果目标值超出范围则向下移动到下一层。重复此过程直到找到目标节点。
优缺点
优点
插入、删除和查找的期望时间复杂度为 O(logn)。实现简单比红黑树和AVL树更容易理解和维护。
缺点
需要额外的空间存储索引层节点。
代码示例c
下面是一段简单的 C 跳表实现包括节点结构定义、插入、查找和显示功能。
#include iostream
#include cstdlib
#include ctime
#include vector
using namespace std;class Node {
public:int value;vectorNode* 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) {vectorNode* 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;
}代码解析
Node 类 表示跳表中的节点包含节点的值和指向不同层节点的指针向量 forward。 SkipList 类 实现了跳表的主要功能包括插入、查找和显示结构。randomLevel用于随机生成节点的层数控制索引的稀疏程度。insert插入元素到跳表中如果新节点的层数超过当前最大层数则更新索引。search查找目标值是否存在。 主函数 初始化跳表并插入若干元素测试插入和查找功能。
运行结果
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(logn)O(\log n)O(logn)。空间复杂度O(nlogn)O(n \log n)O(nlogn)因为每个节点可能会出现在多层中。
跳表的实现简单且高效常用于 Redis 等数据库的有序集合。
