中山古镇做网站的公司,免费公司网站建站,做网站提高淘宝店排名,网站权重有时降目录写在前面跳表概要查找步骤插入步骤删除步骤完整代码写在前面
关于跳表的一些知识可以参考这篇文章,最好是先看完这篇文章再看详细的思路-代码的复现步骤: Redis内部数据结构详解(6)——skiplist 关于跳表的插入、删除基本操作其实也就是链表的插入和删除#xff0c;所… 目录写在前面跳表概要查找步骤插入步骤删除步骤完整代码 写在前面
关于跳表的一些知识可以参考这篇文章,最好是先看完这篇文章再看详细的思路-代码的复现步骤: Redis内部数据结构详解(6)——skiplist 关于跳表的插入、删除基本操作其实也就是链表的插入和删除所以如果不熟悉的话还得先回顾链表的插入以及删除是怎样的可以参考 【数据结构基础笔记】【链表】 相关代码以及其他语言的写法或者其他思路可以参考 1206. 设计跳表 代码参考链接 https://leetcode-cn.com/problems/design-skiplist/solution/can-kao-redisshi-xian-by-bakezq/ https://www.iteye.com/blog/kenby-1187303
跳表概要
跳表采用随机法决定链表中哪些节点应该增加向前指针以及在该节点中应增加多少个指针。 跳表结构的头节点需要有足够的指针域以满足可能构造最大级数的需求而尾节点不需要指针域。 跳表在原有的有序链表上增加了多级索引通过索引来实现快速查找。 1、首先在最高级索引上查找最后一个小于当前查找元素的位置 2、调到次高级索引继续查找直到调到最底层为止如果查找元素存在的话此刻已经十分接近要查找的元素的位置了。
查找步骤
你需要了解的内容 1、指定head为左上角 2、初始化prevs数组(转折点数组) 3、查找只有 right 和 down 两个方向 4、maxlevel是当前跳表的最大层数并非一开始人为限制的MAXLEVEL。maxlevel可能会随着插入新的结点时的产生随机层数而更新。 但是总是有maxlevel MAXLEVEL 以下面的图为例从中你应该能清楚了解到prevs数组的含义。 从从顶层向下遍历到最底层 根据这样的思路可以写出这样的代码
vectorNode* _search(int key)
{Node* cur head;vectorNode* prevs(MAX_LEVEL);//从顶层向下遍历注意这里的maxlevel是当前跳表的最大层数并非一开始人为限制的MAXLEVEL。//maxlevel可能会随着插入新的结点时的产生随机层数而更新。for(int i maxlevel- 1;i 0;i--){//在当前层中比较直到查找元素小于keywhile(cur-level[i] cur-level[i]-val key)cur cur-level[i];//每层找到一个最靠近的点作为向下的转折点prevs[i] cur;}return prevs;
}bool search(int target)
{//获取第一层(最底层)最靠近key且val小于key的节点Node* prev _search(target)[0];return prev-level[0] prev-level[0]-val target;
}插入步骤
插入步骤 1、通过查找子函数获取最底层链表中num值的最近的节点赋给prevs 2、随机产生该节点的层数 首先每个节点肯定都有第1层指针每个节点都在第1层链表里。 如果一个节点有第i层(i1)指针即节点已经在第1层到第i层链表中那么它有第(i1)层指针的概率为p。 节点最大的层数不允许超过一个最大值记为MaxLevel。
static int random_level() {int level 1;while (rand() SKIPLIST_P_VAL level MAX_LEVEL) level;return level;
}randomLevel()的伪码中包含两个参数一个是p一个是MaxLevel。在Redis的skiplist实现中这两个参数的取值为 p 1/4 MaxLevel 32 3、更新当前的跳表中的最大层数maxlevel在新生成的层里将prevs[]初始化为head结点 如下图当我们插入的数为2随机出来的层数为5那么新的一层中小于这个num的节点一定是头结点。 4、生成一个新的结点值为num层数为level 5、对于每一层来说由于新插入了一个结点于是原本的索引关系就得发生改变 将原本prevs的在本层的后继作为cur在本层的后继再将cur作为prevs的后继 以第0层为例 由于这里的prevs[i]都是head结点所以可以比较方便的看出关系整理之后就是下面的样子 代码
void add(int num)
{//1、通过查找子函数获取最底层链表中num值的最近的节点。auto prevs _search(num);//2、随机产生该节点的层数int level random_level();//3、更新当前的跳表中的最大层数maxlevel,并且if(level maxlevel){for(int i maxlevel; i level; i)prevs[i] head;maxlevel level;}Node* cur new Node(num,level);//for(int i level -1; i 0; i--){cur-level[i] prevs[i]-level[i];prevs[i]-level[i] cur}
}删除步骤 1、通过查找子函数获取最底层链表中 num值的最近的节点赋给prevs 2、特殊情况处理如果prevs在原链表中不存在(是指向空的节点) 或者 最近的节点的值不等于num没有值为num的节点返回错误 3、否则说明存在值为nums的结点且为prevs[0]-level[0] 4、接下来就是要通过修改节点之间的后继关系将值为num的前继后继节点相连。 prevs的后继为需要删除的del节点则将del的后继连接到prevs后面作为新的prevs的后继 5、将空间释放 6、删除掉一个结点可能需要更新当前最大层数如果删除的结点是之前层数最多的话 判断方法如果头结点maxlevel-1层的结点没有后继说明本层已经没有其他节点了 bool erase(int num)
{//1、通过查找子函数获取最底层链表中 num值的最近的节点赋给prevsauto prevs _search(num);//2、特殊情况处理如果prevs在原链表中不存在(是指向空的节点) 或者 最近的节点的值不等于num没有值为num的节点返回错误if (!prevs[0]-level[0] || prevs[0]-level[0]-val ! num)return false;//3、否则说明存在值为nums的结点且为prevs[0]-level[0] Node * del prevs[0]-level[0];//4、接下来就是要通过修改节点之间的后继关系将值为num的前继后继节点相连。for (int i 0; i maxlevel; i)//prevs的后继为需要删除的del节点则将del的后继连接到prevs后面作为新的prevs的后溪if (prevs[i]-level[i] del)prevs[i]-level[i] del-level[i];//将空间释放delete del;//删除掉一个结点可能需要更新当前最大层数如果删除的结点是之前层数最多的话//如果头结点maxlevel-1层的结点没有后继说明本层已经没有其他节点了。while (maxlevel 1 !head.level[maxlevel - 1])maxlevel--;return true;
}完整代码
将成员数据和函数进行了私有公有的划分
class Skiplist {
private://定义结点struct Node {int val;vectorNode * level;Node(int val, int size MAX_LEVEL) : val(val), level(size) {}};//定义随机结点层数的参数static const int SKIPLIST_P_VAL RAND_MAX / 4, MAX_LEVEL 32;//定义头结点Node head;//定义当前最大层数int maxlevel 1;//定义search子函数vectorNode* _search(int key) {Node* cur head;vectorNode * prevs(MAX_LEVEL);// through every level, from top to bottomfor (int i maxlevel - 1; i 0; i--) {// through elements in the current level with smaller valuewhile (cur-level[i] cur-level[i]-val key)cur cur-level[i];prevs[i] cur;}return prevs;}//定义随机产生层数子函数static int random_level() {int level 1;while (rand() SKIPLIST_P_VAL level MAX_LEVEL) level;return level;}public://初始化跳表的时候也需要初始化headSkiplist() : head(INT_MIN, MAX_LEVEL) {}bool search(int target) {Node* prev _search(target)[0];return prev-level[0] prev-level[0]-val target;}void add(int num) {auto prevs _search(num);int level random_level();if (level maxlevel) {for (int i maxlevel; i level; i)prevs[i] head;maxlevel level;}Node * cur new Node(num, level);for (int i level - 1; i 0; i--) {cur-level[i] prevs[i]-level[i];prevs[i]-level[i] cur;}}bool erase(int num) {auto prevs _search(num);if (!prevs[0]-level[0] || prevs[0]-level[0]-val ! num)return false;Node * del prevs[0]-level[0];for (int i 0; i maxlevel; i)if (prevs[i]-level[i] del)prevs[i]-level[i] del-level[i];delete del;while (maxlevel 1 !head.level[maxlevel - 1])maxlevel--;return true;}
};/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj new Skiplist();* bool param_1 obj-search(target);* obj-add(num);* bool param_3 obj-erase(num);*/
