江苏龙网

  1. 主页 > 生活百科 > >

深入理解跳表及其在Redis中的应用( 二 )

Redis

四. 跳表的添加方法每一个元素添加到跳表中时，首先需要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素添加到跳表中之前，还需要扩大跳表的层数，而扩大跳表的层数就是将头尾节点的层数扩大 。下面给出需要扩大跳表层数的一次添加的过程 。
【深入理解跳表及其在Redis中的应用】初始状态时，跳表的层数为 2，如下图所示 。

深入理解跳表及其在Redis中的应用

文章插图
现在要往跳表中添加元素 120，并且随机指定的层数为 3，大于了当前跳表的层数 2，此时需要先扩大跳表的层数，2如 下图所示 。
深入理解跳表及其在Redis中的应用

文章插图
??将元素 120 插入到跳表中时，从顶层开始，逐层向下插入，如下图所示 。
深入理解跳表及其在Redis中的应用

文章插图
??跳表的添加方法的代码如下所示 。
public void add(int num) {//获取本次添加的值的层数int level = getRandomLevel();//如果本次添加的值的层数大于当前跳表的层数//则需要在添加当前值前先将跳表层数扩充if (level > curLevel) {expanLevel(level - curLevel);}//curNode表示num值在当前层对应的节点SkiplistNode curNode = new SkiplistNode(num, level);//preNode表示curNode在当前层的前一个节点SkiplistNode preNode = headNodes.get(curLevel - level);for (int i = 0; i <= level; i++) {//从当前层的head节点开始向后遍历，直到找到一个preNode//使得preNode.data < num <= preNode.next.datawhile (preNode.next.data < num) {preNode = preNode.next;}//将curNode插入到preNode和preNode.next中间curNode.next = preNode.next;preNode.next = curNode;//如果当前并不是0层，则继续向下层添加节点if (curNode.level > 0) {SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);//curNode指向下一层的节点curNode.down = downNode;//curNode向下移动一层curNode = downNode;}//preNode向下移动一层preNode = preNode.down;}}private void expanLevel(int expanCount) {SkiplistNode head = headNodes.getFirst();SkiplistNode tail = tailNodes.getFirst();for (int i = 0; i < expanCount; i++) {SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);headNew.down = head;tailNew.down = tail;head = headNew;tail = tailNew;headNodes.addFirst(head);tailNodes.addFirst(tail);}}五. 跳表的搜索方法在跳表中搜索一个元素时，需要从顶层开始，逐层向下搜索 。搜索时遵循如下规则 。
•目标值大于当前节点的后一节点值时，继续在本层链表上向后搜索；
•目标值大于当前节点值，小于当前节点的后一节点值时，向下移动一层，从下层链表的同节点位置向后搜索；
•目标值等于当前节点值，搜索结束 。
•下图是一个搜索过程的示意图 。
深入理解跳表及其在Redis中的应用

文章插图
•跳表的搜索的代码如下所示 。
public boolean search(int target) {//从顶层开始寻找，curNode表示当前遍历到的节点SkiplistNode curNode = headNodes.getFirst();while (curNode != null) {if (curNode.next.data =https://www.isolves.com/it/sjk/Redis/2023-03-02/= target) {//找到了目标值对应的节点，此时返回truereturn true;} else if (curNode.next.data > target) {//curNode的后一节点值大于target//说明目标节点在curNode和curNode.next之间//此时需要向下层寻找curNode = curNode.down;} else {//curNode的后一节点值小于target//说明目标节点在curNode的后一节点的后面//此时在本层继续向后寻找curNode = curNode.next;}}return false;}六. 跳表的删除方法当在跳表中需要删除某一个元素时，则需要将这个元素在所有层的节点都删除，具体的删除规则如下所示 。
•首先按照跳表的搜索的方式，搜索待删除节点，如果能够搜索到，此时搜索到的待删除节点位于该节点层数的最高层；
•从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除方式就是让待删除节点的前一节点直接指向待删除节点的后一节点 。
•下图是一个删除过程的示意图 。
深入理解跳表及其在Redis中的应用

文章插图
•跳表的删除的代码如下所示 。
public boolean erase(int num) {//删除节点的遍历过程与寻找节点的遍历过程是相同的//不过在删除节点时如果找到目标节点，则需要执行节点删除的操作SkiplistNode curNode = headNodes.getFirst();while (curNode != null) {if (curNode.next.data =https://www.isolves.com/it/sjk/Redis/2023-03-02/= num) {//preDeleteNode表示待删除节点的前一节点SkiplistNode preDeleteNode = curNode;while (true) {//删除当前层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点preDeleteNode.next = curNode.next.next;//当前层删除完后，需要继续删除下一层的待删除节点//这里让preDeleteNode向下移动一层//向下移动一层后，preDeleteNode就不一定是待删除节点的前一节点了preDeleteNode = preDeleteNode.down;//如果preDeleteNode为null，说明已经将底层的待删除节点删除了//此时就结束删除流程，并返回trueif (preDeleteNode == null) {return true;}//preDeleteNode向下移动一层后，需要继续从当前位置向后遍历//直到找到一个preDeleteNode，使得preDeleteNode.next的值等于目标值//此时preDeleteNode就又变成了待删除节点的前一节点while (preDeleteNode.next.data != num) {preDeleteNode = preDeleteNode.next;}}} else if (curNode.next.data > num) {curNode = curNode.down;} else {curNode = curNode.next;}}return false;}


推荐阅读


上一篇：没有了

下一篇：数据结构与算法：冒泡排序