乐趣区

关于数据结构与算法:数据结构与算法跳表

jiezi

前言

跳表能够达到和红黑树一样的工夫复杂度 O(logN)，且实现简略，Redis 中的有序汇合对象的底层数据结构就应用了跳表。本篇文章将对跳表的实现进行学习。

注释

一. 跳表的根底概念

跳表，即跳跃表（Skip List），是基于并联的链表数据结构，操作效率能够达到O(logN)，对并发敌对，跳表的示意图如下所示。

跳表的特点，能够概括如下。

  • 跳表是多层（level）链表构造；
  • 跳表中的每一层都是一个有序链表，并且依照元素升序（默认）排列；
  • 跳表中的元素会在哪一层呈现是随机决定的，然而只有元素呈现在了第 k 层，那么 k 层以下的链表也会呈现这个元素；
  • 跳表的底层的链表蕴含所有元素；
  • 跳表头节点和尾节点不存储元素，且头节点和尾节点的层数就是跳表的最大层数；
  • 跳表中的节点蕴含两个指针，一个指针指向同层链表的后一节点，一个指针指向上层链表的同元素节点。

以上图中的跳表为例，如果要查找元素 71，那么查找流程如下图所示。

从顶层链表的头节点开始查找，查找到元素 71 的节点时，一共遍历了 4 个节点，然而如果依照传统链表的形式（即从跳表的底层链表的头节点开始向后查找），那么就须要遍历 7 个节点，所以跳表以空间换工夫，缩短了操作跳表所须要破费的工夫。

二. 跳表的节点

已知跳表中的节点，须要有指向以后层链表后一节点的指针，和指向上层链表的同元素节点的指针，所以跳表中的节点，定义如下。

public class SkiplistNode {

    public int data;
    public SkiplistNode next;
    public SkiplistNode down;
    public int level;

    public SkiplistNode(int data, int level) {
        this.data = data;
        this.level = level;
    }

}

上述是跳表中的节点的最简略的定义形式，存储的元素 data 为整数，节点之间进行比拟时间接比拟元素 data 的大小。

三. 跳表的初始化

跳表初始化时，将每一层链表的头尾节点创立进去并应用汇合将头尾节点进行存储，头尾节点的层数随机指定，且头尾节点的层数就代表以后跳表的层数。初始化后，跳表构造如下所示。

跳表初始化的相干代码如下所示。

public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;

public int curLevel;

public Random random;

public Skiplist() {random = new Random();

    //headNodes 用于存储每一层的头节点
    headNodes = new LinkedList<>();
    //tailNodes 用于存储每一层的尾节点
    tailNodes = new LinkedList<>();

    // 初始化跳表时，跳表的层数随机指定
    curLevel = getRandomLevel();
    // 指定了跳表的初始的随机层数后，就须要将每一层的头节点和尾节点创立进去并构建好关系
    SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
    SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
    for (int i = 0; i <= curLevel; i++) {
        head.next = tail;
        headNodes.addFirst(head);
        tailNodes.addFirst(tail);

        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;
    }
}

四. 跳表的增加办法

每一个元素增加到跳表中时，首先须要随机指定这个元素在跳表中的层数，如果随机指定的层数大于了跳表的层数，则在将元素增加到跳表中之前，还须要扩充跳表的层数，而扩充跳表的层数就是将头尾节点的层数扩充。上面给出须要扩充跳表层数的一次增加的过程。

初始状态时，跳表的层数为 2，如下图所示。

当初要往跳表中增加元素 120，并且随机指定的层数为 3，大于了以后跳表的层数 2，此时须要先扩充跳表的层数，如下图所示。

将元素 120 插入到跳表中时，从顶层开始，逐层向下插入，如下图所示。

跳表的增加办法的代码如下所示。

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.data
        while (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);
    }
}

五. 跳表的搜寻办法

在跳表中搜寻一个元素时，须要从顶层开始，逐层向下搜寻。搜寻时遵循如下规定。

  • 目标值大于以后节点的后一节点值时，持续在本层链表上向后搜寻；
  • 目标值大于以后节点值，小于以后节点的后一节点值时，向下挪动一层，从上层链表的同节点地位向后搜寻；
  • 目标值等于以后节点值，搜寻完结。

下图是一个搜寻过程的示意图。

跳表的搜寻的代码如下所示。

public boolean search(int target) {
    // 从顶层开始寻找，curNode 示意以后遍历到的节点
    SkiplistNode curNode = headNodes.getFirst();
    while (curNode != null) {if (curNode.next.data == target) {
            // 找到了目标值对应的节点，此时返回 true
            return true;
        } else if (curNode.next.data > target) {
            //curNode 的后一节点值大于 target
            // 阐明指标节点在 curNode 和 curNode.next 之间
            // 此时须要向上层寻找
            curNode = curNode.down;
        } else {
            //curNode 的后一节点值小于 target
            // 阐明指标节点在 curNode 的后一节点的前面
            // 此时在本层持续向后寻找
            curNode = curNode.next;
        }
    }
    return false;
}

六. 跳表的删除办法

当在跳表中须要删除某一个元素时，则须要将这个元素在所有层的节点都删除，具体的删除规定如下所示。

  • 首先依照跳表的搜寻的形式，搜寻待删除节点，如果可能搜寻到，此时搜寻到的待删除节点位于该节点层数的最高层；
  • 从待删除节点的最高层往下，将每一层的待删除节点都删除掉，删除形式就是让待删除节点的前一节点间接指向待删除节点的后一节点。

下图是一个删除过程的示意图。

跳表的删除的代码如下所示。

public boolean erase(int num) {
    // 删除节点的遍历过程与寻找节点的遍历过程是雷同的
    // 不过在删除节点时如果找到指标节点，则须要执行节点删除的操作
    SkiplistNode curNode = headNodes.getFirst();
    while (curNode != null) {if (curNode.next.data == num) {
            //preDeleteNode 示意待删除节点的前一节点
            SkiplistNode preDeleteNode = curNode;
            while (true) {
                // 删除以后层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点
                preDeleteNode.next = curNode.next.next;
                // 以后层删除完后，须要持续删除下一层的待删除节点
                // 这里让 preDeleteNode 向下挪动一层
                // 向下挪动一层后，preDeleteNode 就不肯定是待删除节点的前一节点了
                preDeleteNode = preDeleteNode.down;

                // 如果 preDeleteNode 为 null，阐明曾经将底层的待删除节点删除了
                // 此时就完结删除流程，并返回 true
                if (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;
}

七. 跳表残缺代码

跳表残缺代码如下所示。

public class Skiplist {

    public LinkedList<SkiplistNode> headNodes;
    public LinkedList<SkiplistNode> tailNodes;

    public int curLevel;

    public Random random;

    public Skiplist() {random = new Random();

        //headNodes 用于存储每一层的头节点
        headNodes = new LinkedList<>();
        //tailNodes 用于存储每一层的尾节点
        tailNodes = new LinkedList<>();

        // 初始化跳表时，跳表的层数随机指定
        curLevel = getRandomLevel();
        // 指定了跳表的初始的随机层数后，就须要将每一层的头节点和尾节点创立进去并构建好关系
        SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
        SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
        for (int i = 0; i <= curLevel; i++) {
            head.next = tail;
            headNodes.addFirst(head);
            tailNodes.addFirst(tail);

            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;
        }
    }

    public boolean search(int target) {
        // 从顶层开始寻找，curNode 示意以后遍历到的节点
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {if (curNode.next.data == target) {
                // 找到了目标值对应的节点，此时返回 true
                return true;
            } else if (curNode.next.data > target) {
                //curNode 的后一节点值大于 target
                // 阐明指标节点在 curNode 和 curNode.next 之间
                // 此时须要向上层寻找
                curNode = curNode.down;
            } else {
                //curNode 的后一节点值小于 target
                // 阐明指标节点在 curNode 的后一节点的前面
                // 此时在本层持续向后寻找
                curNode = curNode.next;
            }
        }
        return false;
    }

    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.data
            while (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;
        }
    }

    public boolean erase(int num) {
        // 删除节点的遍历过程与寻找节点的遍历过程是雷同的
        // 不过在删除节点时如果找到指标节点，则须要执行节点删除的操作
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {if (curNode.next.data == num) {
                //preDeleteNode 示意待删除节点的前一节点
                SkiplistNode preDeleteNode = curNode;
                while (true) {
                    // 删除以后层的待删除节点，就是让待删除节点的前一节点指向待删除节点的后一节点
                    preDeleteNode.next = curNode.next.next;
                    // 以后层删除完后，须要持续删除下一层的待删除节点
                    // 这里让 preDeleteNode 向下挪动一层
                    // 向下挪动一层后，preDeleteNode 就不肯定是待删除节点的前一节点了
                    preDeleteNode = preDeleteNode.down;

                    // 如果 preDeleteNode 为 null，阐明曾经将底层的待删除节点删除了
                    // 此时就完结删除流程，并返回 true
                    if (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;
    }

    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);
        }
    }

    private int getRandomLevel() {
        int level = 0;
        while (random.nextInt(2) > 1) {level++;}
        return level;
    }

}

总结

跳表的工夫复杂度与 AVL 树和红黑树雷同，能够达到 O(logN)，然而AVL 树要维持高度的均衡，红黑树要维持高度的近似均衡，这都会导致插入或者删除节点时的一些工夫开销，所以跳表相较于 AVL 树和红黑树来说，省去了维持高度的均衡的工夫开销，然而相应的也付出了更多的空间来存储多个层的节点，所以跳表是用空间换工夫的数据结构。

退出移动版