数据结构与算法之美笔记——跳表

作者: Cloneable | 来源:发表于2019-07-07 16:42 被阅读0次

摘要:

跳表是基于链表的数据结构，查找、插入及删除数据时间复杂度都为 $O(\log{n})$ ，空间复杂度为 $O(n)$ ，也是利用了空间换时间的概念提高了链表的执行效率。

基于链表的二分查找

在之前的文章有提到过二分查找基于链表实现时会导致算法效率严重下降，但 $O(\log{n})$ 的执行效率实在诱人，难道链表没有办法在不降低二分查找执行效率的基础上实现它吗？链表肯定有相应的解决方案，但需要使用基于链表扩展的数据结构「跳表」（Skip list）。

跳表的英文名「Skip list」中的 list 表示它是基于链表的，那在链表的基础上是如何实现 Skip 的呢？链表随机访问某个结点效率低的原因是需要遍历目标结点之前的所有结点，如果我们将链表中的两个结点归为一个区域，查找结点时先查找所在区域，再在区域的小范围数据中查找目标结点，效率肯定提升很多，两个结点抽取形成的区域当然也使用链表实现。举个例子，如果当前链表有 10 个结点，此时查找第 8 个结点需要遍历 8 次，我们将每两个结点抽取成一个结点形成区域，区域的结点个数就是 5 个，查找原链表上第 6 个结点可以先在区域链表上查找，对应的是第 4 个结点的区域，再在此区域的原链表上查找，总共只用查找 5 次结点。

既然对链表抽取区域后可以提高执行效率，如果对区域链表进行同样的操作执行效率会发生怎样的变化？接着上面的例子，对第二级链表进行两个结点抽取成一个结点形成区域，形成的链表有 3 个结点，依然是查找第一级链表的第 8 个结点，这次只需要查找 4 次，所以执行效率是提升的。

其实抽取结点形成的区域链表和索引是类似的，也可以认为抽取出的链表都是原链表的索引链表。之前举的例子数据量不大，能够抽取的索引级数也较少，效果不太明显，如果将数据量扩大到 32 个，原始链表查找第 31 个结点时需要遍历 31 次，我们将索引的级数增加，直至索引链表的结点个数为 2，此时查找原链表上第 31 个结点只需要查找 5 次，可以看出查找的效率在提取索引后得到了极大的提升。

跳表的时间复杂度

从上面的例子中可以看出跳表的执行效率极高，但具体多高就需要分析一下跳表的时间复杂度了。我们从两个结点提取一个结点作为索引链表的结点，索引链表的结点数是前一级链表结点数的 $\frac{1}{2}$ ，假设有一个链表结点个数为 n，它的第一级至第 k 级索引链表的结点个数依次为 $\frac{n}{2}，\frac{n}{4}，\frac{n}{8}，...，\frac{n}{2^k}$ ，第 k 级索引链表为 2 个结点，所以满足如下数学关系。

$\frac{n}{2^k}=2$
$2^{k+1}=n$
$k=\log_2{n}-1$

因此一个结点个数为 n 的链表可以提取出 $\log_2{n}-1$ 级索引，加上原始链表这一级总共有 $\log_2{n}$ 级链表。当我们在此跳表中查找目标结点时每级链表最多需要遍历 m 个结点，总共需要查找 $m\times\log_2{n}$ 次结点，但 m 是多少呢？假设需要查找的目标数据为 x，从跳表的最高一级（以下称为 h 级）索引开始查找，h 级索引只有两个结点（从头结点开始，依次称为 y 和 z 结点），x 的情况要不就是处于 y 与 z 之间，要不就是大于 z，如果小于 y 那 x 肯定不存在于原始列表中。因为索引是由下一级索引抽取两个结点为一个结点形成，所以无论 x 处于 y 与 z 之间还是大于 z，在 h - 1 级索引中最多只需查找 3 个结点（y 结点，z 结点及 y 和 z 的中间结点）就可以知道 x 处于哪个区域，以此类推，每一级目标数据的查找最多只用遍历 3 个结点，所以 m 等于 3，跳表查找操作的时间复杂度也就是 $O(3\times\log_2{n})=O(\log{n})$ 。

跳表除了查找操作外还有插入和删除操作。链表进行插入和删除操作时间复杂度是 $O(1)$ ，但在插入和删除前需要查找数据插入位置或需要被删除的结点，导致时间复杂度降低为 $O(n)$ ，跳表通过索引将查找的时间复杂度提高到了 $O(\log{n})$ ，而单纯插入和删除操作的时间复杂度不变，依然是 $O(1)$ ，所以跳表插入和删除的时间复杂度是 $O(log{n})$ ，跳表无论是查找还是插入和删除操作都是极为高效的。

用了多少空间换时间

跳表利用索引获得了 $O(\log{n})$ 的高执行效率，但索引也是数据的一种，需要额外的存储空间，所以跳表利用了空间换时间，那跳表的空间复杂度是多少？

通过对跳表时间复杂度分析我们知道，一个 n 个结点的链表，它的第一级至第 k 级索引链表的结点个数依次为 $\frac{n}{2}，\frac{n}{4}，\frac{n}{8}，...，\frac{n}{2^k}$ ，且 $k=\log_2{n}-1$ ，所有的索引链表结点个数之和为 $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+...+\frac{n}{2^k}=\frac{n}{2}\times{\frac{1-\frac{1}{2^k}}{1-\frac{1}{2}}}=n-\frac{n}{2^k}=n-2$ ，所以跳表的时间复杂度为 $O(n)$ 。

面对跳表的多级索引需要如此多额外存储空间的情况我们需要优化一下。因为之前分析的都是两个结点抽取为一个索引结点的情况，如果将 3 个结点抽取一个索引结点，索引结点的数量肯定会下降，这种情况下最高级索引有一个结点，所以索引级数 k 等于 $\log_3{n}$ ，而索引结点个数为 $\frac{n-1}{2}$ ，虽然空间复杂度也是 $O(n)$ ，但 3 个结点抽取一个索引结点需要的额外存储只有两个结点抽取一个索引时的一半，但这种方式会使查找的执行效率出现下降，所以时间和空间消耗上需要做出平衡。

索引动态更新

跳表不仅支持查找操作，同时也支持插入和删除操作，但插入和删除操作会产生一些意外情况。当一直插入数据时，会导致索引结点间的结点数量增加，极端情况下会使跳表退化为链表；当被删除结点也是索引结点时，索引结点也应该被删除，所以跳表的插入和删除操作都应该对跳表索引动态更新。

对跳表进行插入操作时，为了避免索引结点间的结点数量不平衡情况，在插入结点时需要决策此结点是否要抽取为索引结点以及抽取到哪级索引，跳表使用「随机法」解决这个问题。随机法是生成一个随机数 k，k 表示当前插入结点需要抽取为第 1 至 k 级索引的索引结点，跳表的插入操作通过这种方式维持索引的平衡。

代码实现

public class SkipList {
    private static final int MAX_LEVEL = 16;

    private Node head = new Node();
    private int levelCount = 1;
    private Random random = new Random();

    public void insert(int value) {
        // get random level and init node
        int level = randomLevel();
        Node node = new Node();
        node.value = value;
        node.maxLevel = level;

        // init update arrays
        Node[] update = new Node[levelCount > level ? levelCount : level];
        for(int i = 0; i < level; i++) {
            update[i] = head;
        }

        // get all previous node of inserted node
        Node prev = head;
        for(int i = levelCount - 1; i >= 0; i--) {
            while(prev.forwards[i] != null && prev.forwards[i].value < value) {
                prev = prev.forwards[i];
            }
            update[i] = prev;
        }

        // insert node to all level linked list
        for(int i = 0; i < level; i++) {
            node.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = node;
        }

        if(levelCount < level) {
            levelCount = level;
        }
    }

    public Node find(int value) {
        // find previous node of target node
        Node prev = head;
        for(int i = levelCount - 1; i >= 0; i--) {
            while(prev.forwards[i] != null && prev.forwards[i].value < value) {
                prev = prev.forwards[i];
            }
        }

        if(prev.forwards[0] != null && prev.forwards[0].value == value) {
            return prev.forwards[0];
        }

        return null;
    }

    public void delete(int value) {
        // get all previous node of deleted node
        Node[] update = new Node[levelCount];
        Node prev = head;
        for(int i = levelCount - 1; i >= 0; i--) {
            while(prev.forwards[i] != null && prev.forwards[i].value < value) {
                prev = prev.forwards[i];
            }
            update[i] = prev;
        }

        if(prev.forwards[0] != null && prev.forwards[0].value == value) {
            int i = 0;
            while(update[i].forwards[i] != null && update[i].forwards[i].value == value) {
                update[i].forwards[i] = update[i].forwards[i].forwards[i];
                i++;
            }
        }
    }

    private int randomLevel() {
        int level = 1;
        for(int i = 1; i < MAX_LEVEL; i++) {
            if(random.nextInt() % 2 == 1) {
                level++;
            }
        }

        return level;
    }

    public class Node {
        private int value = -1;
        private int maxLevel = 0;
        private Node[] forwards = new Node[MAX_LEVEL];

        public int getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "{value: " + value +", maxLevel: " + maxLevel + "}";
        }
    }
}

代码中比较不好理解的就是 Node 中 forwards 的作用，forwards 是个 Node 数组，它是用来存储此结点在每一级链表中的下一结点，第 n 级链表就对应 forwards 中的第 n 个元素，只要理解了 forwards 的作用也就能够理解跳表各个操作的逻辑。

总结

跳表就是在链表之上建立了多级索引结构，多级索引虽然导致空间复杂度下降为 $O(n)$ ，但时间复杂度复杂被极好地提升为 $O(\log{n})$ 。

为了优化跳表的存储消耗，可以考虑 3 个、5 个或更多的点抽取为一个索引点，但这样会使查找操作执行效率下降，所以需要根据实际情况寻找平衡。

跳表除了支持高效的查找操作还支持插入和删除操作，插入和删除操作依然很高效，时间复杂度都是 $O(\log{n})$ ，但插入和删除时需要对索引进行动态更新，插入时利用随机法解决这一问题。

文章中如有问题欢迎留言指正
本章节代码已经上传GitHub，可点击跳转查看代码详情。
数据结构与算法之美笔记系列将会做为我对王争老师此专栏的学习笔记，如想了解更多王争老师专栏的详情请到极客时间自行搜索。

数据结构与算法之美笔记——跳表

基于链表的二分查找

跳表的时间复杂度

用了多少空间换时间

索引动态更新

代码实现

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读