跳表详细解析

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in life基础背景普通有序单向链表查找需要逐个遍历时间复杂度On)。 跳表skiplist是在有序链表基础上多层索引链表实现的结构。William Pugh 的原始优化思路第一层索引每 2 个底层节点向上层提一个节点建立指针。上层链表节点数只有底层一半查找比较次数减半。多层迭代在上一层链表继续隔二取一继续向上建立更高层索引层层叠加。理想情况每层节点数是下层的一半查找类似二分查找时间复杂度 O(log n)致命缺陷插入 / 删除节点会打破严格 2:1 的上下层比例要维持这个比例需要改动后面大量节点复杂度退化成O(n)跳表 SkipList 效率保证原理不再强制维持 2:1 固定比例插入新节点时随机生成这个节点的层数。 插入、删除操作只需要修改当前节点相关的指针不需要改动其他节点的层数操作简单高效。随机层数生成算法randomLevel()randomLevel() lvl : 1 while random() p and lvl MaxLevel do lvl : lvl 1 return lvl逻辑新节点初始层数 lvl1必然至少在底层链表循环每次以概率p尝试再往上增加一层达到最大层数maxLevel就停止Redis 跳表参数p1/4,maxLevel32规律层数越高生成概率越小层数恰好 1概率 (1-p)层数恰好 2概率 (p(1-p))层数恰好 3概率 (p^2(1-p))层数恰好 k概率 (p^(k-1)(1-p))节点平均层数平均指针数量推导--就是数学期望的计算因此一个节点的平均层数也即包含的平均指针数目计算如下概率*层数平均层数 1×(1-p)2p (1-p)3p²(1-p)4p³(1-p)… (1-p) × ∑(k1 到∞) k・p^(k-1) 1/(1-p)代入计算p1/2平均层数 1/(1-1/2)2每个节点平均 2 个指针 ,p1/4平均层数 1/(1-1/4)≈1.33Redis 采用这个节省内存如何保证查找插入删除平均 O (log n)1.概率上理解高层节点稀疏低层节点稠密。每层节点期望数量是下一层的 p 倍。比如 p1/4第 1 层 n 个第 2 层期望 np第 3 层 np²……高层索引数量快速衰减。这个概率分布等效于理想跳表的 2:1 分层只是用随机代替强制固定间隔。2.推导纵向逐层下沉跳表插入节点时每往上一层的成功概率是 p第 0 层n 个节点第 1 层索引期望节点数 n・p第 2 层索引期望节点数 n・p²第 k 层索引期望节点数 n・p^k当高层节点数量降到 1 个 的时候就是跳表最高层再减少都没有了呀 n・p^k ≈ 1变形 p^k 1/n 也就是 n 1/(p^k)两边取对数 log (1/p)n kk 就是跳表的期望总层数。查找的时候我们从最高层一层一层往下走最多需要下降 k 层。横向同层向右在任意一层查找时向右比较的次数的数学期望是常数1/p和数据总量 n 无关。以 Redis 的 p1/4 举例 每 4 个底层节点里平均只有 1 个节点会向上晋升到上一层索引。 也就是说在当前索引层两个相邻索引节点之间平均隔着 4 个底层节点。当我们在这一层向右查找当前节点的值 目标值继续向右走当前节点的值 ≥ 目标值停止下沉到下一层在这一层平均只需要向右比较 4 次也就是 (1/p)就一定会触发下沉。 不管总共有 1000 个还是 100 万个节点同一层的平均向右比较次数永远是 4 次不会随着 n 变大而增加这就是「常数」。总结横向同层向右期望比较次数 1/p属于 (O(1))纵向逐层下沉期望层数O (log (1/p) n)属于 (O(log n))查找总步数 每层横向比较次数 × 总层数O(1)xO(log n)所以查找整体时间复杂度 (O(log n))。最坏O(n)几乎遇不到插入删除时间复杂度1.插入分为三步查找插入位置期望 (O(log n))随机生成新节点的层数在生成层数对应的每一层链表执行插入链表插入是常数 (O(1))总耗时(O(log n)O(1)O(log n)) 最坏(O(n)2.删除和插入几乎一样查找目标节点期望 \(O(\log n)\)在该节点存在的每一层链表执行删除链表删除 \(O(1)\)总耗时(O(log n)\) 最坏(O(n))一步步实现跳表代码1.struct SkipListNodestruct SkiplistNode { int val; // 节点存储的值 vectorSkiplistNode* next; // next[i] 代表第 i 层的后继节点指针 // 构造函数val为值level代表这个节点拥有多少层指针 SkiplistNode(int v, int level) : val(v), next(level, nullptr) {} };2.class Skiplistclass Skiplist { typedef SkiplistNode Node; public: Skiplist(){} ~Skiplist(){} bool search(int target){} vectorNode* findprev(int num) void add(int num) bool erase(int num) int randomLevel() private: Node* head; // 跳表头节点 const int maxLevel 32; // 允许的最大层数 const double p 0.25; // 向上晋升一层的概率 };3.Skiplsit(){}构造函数SkipList() { // 头节点不存有效数据val-1初始只有1层,尽量不要初始化为maxlevel要加快head从上往下下沉速度 head new Node(-1, 1); }4.~Skiplsit(){}析构函数~SkipList() { Node* cur head; while (cur!nullptr) { Node* nextnode cur-next[0]; delete cur;//先把1个节点从下到上删除 cur nextnode;//去下一个节点 } }5.bool search查询某个元素在不在Skipistbool search(int target) { Node* cur head; int curlevel head-next.size() - 1; while (curlevel 0) { // 当前层的下一个节点存在并且值 target继续向右走 if (cur-next[curlevel] ! nullptr cur-next[curlevel]-_val target) { cur cur-next[curlevel]; } //下一个节点为空 或者 值 target向右找不到下沉到下一层 else if (cur-next[curlevel] nullptr || cur-next[curlevel]-_val target) { curlevel--; } // 找到相等节点 else { return true; } } // 全部层找完没有target return false; }6.vectorNode* findprev(int num)记录num的前驱vectorNode*findprev(int num) { Node* cur head; int curlevel head-next.size() - 1; // 初始化前驱数组所有层默认前驱是头节点 vectorNode*prev(curlevel 1, head);//头节点一共curlevel1层 while (curlevel 0) { // 当前层后继节点存在并且后继值 num向右移动 if (cur-next[curlevel] ! nullptr cur-next[curlevel]-_val num) { cur cur-next[curlevel]; } // 后继为空或者后继值 num不能继续右走记录当前节点为本层前驱下沉 //!!!是下沉的时候更新前驱 else { prev[curlevel] cur; curlevel--; } } return prev; }逐轮循环跑一遍num17curLevel3curheadhead-next [3]6617 → cur6 现在 6-next [3] 是 nullptr不满足右走条件。prev[3]6curLevel2。curLevel2cur66-next [2]252517不能右走。prev[2]6curLevel1。curLevel1cur66-next [1]9917 → cur9 9-next [1]252517不能右走。prev[1]9curLevel0。curLevel0cur99-next [0]121217 → cur12 12-next [0]191917不能右走。prev[0]12curLevel-1循环结束。返回结果prev[0]12prev[1]9prev[2]6prev[3]67. void add(int num)void add(int num) { //1.找到num的每一层的前驱节点 vectorNode*prev findprev(num); // 2. 随机生成新节点的层数 int newnodelevel randomLevel(); //3.创建新节点 Node* newnode new Node(num, newnodelevel); // 如果新节点层数 head层数扩容头节点head并且补充高层前驱为head if (newnodelevel head-next.size()) { head-next.resize(newnodelevel, nullptr); prev.resize(newnodelevel, head); } // 4. 逐层完成链表插入新节点指向后继前驱指向新节点 for (int i 0; i newnodelevel; i) { newnode-next[i] prev[i]-next[i]; prev[i]-next[i] newnode; } }调用add(17)插入用上面得到的 prev 数组,newnodelevel2;循环 i 从 0 到 2(所以只会用到prev[0],prev[1])i0level0 底层newNode-next[0]prev[0]-next[0] 12-next[0]19prev[0]-next[0]newNode→12 指向 17i1level1newNode-next[1]prev[1]-next[1]9-next[1]25prev[1]-next[1]newNode→9 指向 178. bool erase(int num)bool erase(int num) { vectorNode*prev findprev(num); //底层链表的后继不是num说明不存在该数字!!,要从上往下一直判断到底层 //删除插入必须到第0层找的时候特别是都还要往下走一直走到第0层才能记录所有的前驱插入和删除的时候才好连接前后指针 if (prev[0]-next[0] nullptr || prev[0]-next[0]-_val ! num) { return false; } Node* delnode prev[0]-next[0]; // 逐层断开待删除节点的链接 for (int i 0; i delnode-next.size(); i) { prev[i]-next[i] delnode-next[i]; } delete delnode; // 删除节点后清理头节点高层空指针压缩跳表最大层数,加快head从上往下下沉速度nullptr没有用 int headmaxlevel head-next.size() - 1; while (headmaxlevel 0 head-next[headmaxlevel] nullptr) { headmaxlevel--; } head-next.resize(headmaxlevel 1); return true; }prev[0]-next[0]是 17存在节点可以删除。delnode17delnode 层数是 20,1i0prev[0]-next[0]delnode-next[0]12 的后继改成 19i1prev[1]-next[1]delnode-next[1]9 的后继改成 25delete 释放 17 节点检查高层把头节点空层压缩。 删除完成跳表回到图上半部分原始状态。9.int randomLevel()随机生成新节点层数int randomLevel() { int level 1; // rand()/RAND_MAX ∈ [0,1]小于等于p就继续增加层数 while (rand() / RAND_MAX p level maxLevel) { level; } return level; }完整代码#includeiostream #includevector using namespace std; struct SkipListNode { int _val; vectorSkipListNode* next;// next[i] 代表第 i 层的后继节点指针 SkipListNode(int v, int level) :_val(v) ,next(level,nullptr) {} }; class SkipList { typedef SkipListNode Node; public: SkipList() { // 头节点不存有效数据val-1初始只有1层,尽量不要初始化为maxlevel要加快head从上往下下沉速度 head new Node(-1, 1); } ~SkipList() { Node* cur head; while (cur!nullptr) { Node* nextnode cur-next[0]; delete cur;//先把1个节点从下到上删除 cur nextnode;//去下一个节点 } } bool search(int target) { Node* cur head; int curlevel head-next.size() - 1; while (curlevel 0) { // 当前层的下一个节点存在并且值 target继续向右走 if (cur-next[curlevel] ! nullptr cur-next[curlevel]-_val target) { cur cur-next[curlevel]; } //下一个节点为空 或者 值 target向右找不到下沉到下一层 else if (cur-next[curlevel] nullptr || cur-next[curlevel]-_val target) { curlevel--; } // 找到相等节点 else { return true; } } // 全部层找完没有target return false; } vectorNode*findprev(int num) { Node* cur head; int curlevel head-next.size() - 1; // 初始化前驱数组所有层默认前驱是头节点 vectorNode*prev(curlevel 1, head);//头节点一共curlevel1层 while (curlevel 0) { // 当前层后继节点存在并且后继值 num向右移动 if (cur-next[curlevel] ! nullptr cur-next[curlevel]-_val num) { cur cur-next[curlevel]; } // 后继为空或者后继值 num不能继续右走记录当前节点为本层前驱下沉 //!!!是下沉的时候更新前驱 else { prev[curlevel] cur; curlevel--; } } return prev; } void add(int num) { //1.找到num的每一层的前驱节点 vectorNode*prev findprev(num); // 2. 随机生成新节点的层数 int newnodelevel randomLevel(); //3.创建新节点 Node* newnode new Node(num, newnodelevel); // 如果新节点层数 head层数扩容头节点head并且补充高层前驱为head if (newnodelevel head-next.size()) { head-next.resize(newnodelevel, nullptr); prev.resize(newnodelevel, head); } // 4. 逐层完成链表插入新节点指向后继前驱指向新节点 for (int i 0; i newnodelevel; i) { newnode-next[i] prev[i]-next[i]; prev[i]-next[i] newnode; } } bool erase(int num) { vectorNode*prev findprev(num); //底层链表的后继不是num说明不存在该数字!!,要从上往下一直判断到底层 //删除插入必须到第0层找的时候特别是都还要往下走一直走到第0层才能记录所有的前驱插入和删除的时候才好连接前后指针 if (prev[0]-next[0] nullptr || prev[0]-next[0]-_val ! num) { return false; } Node* delnode prev[0]-next[0]; // 逐层断开待删除节点的链接 for (int i 0; i delnode-next.size(); i) { prev[i]-next[i] delnode-next[i]; } delete delnode; // 删除节点后清理头节点高层空指针压缩跳表最大层数,加快head从上往下下沉速度nullptr没有用 int headmaxlevel head-next.size() - 1; while (headmaxlevel 0 head-next[headmaxlevel] nullptr) { headmaxlevel--; } head-next.resize(headmaxlevel 1); return true; } int randomLevel() { int level 1; // rand()/RAND_MAX ∈ [0,1]小于等于p就继续增加层数 while (rand() / RAND_MAX p level maxLevel) { level; } return level; } private: Node* head; const int maxLevel 32; // 允许的最大层数 const double p 0.25; // 向上晋升一层的概率 };