Day15
学习内容主要为以下三点：
1.如何理解“跳表”？
跳表：链表加多级索引的结构。
跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。
2.用跳表查询到底有多快？
跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。
理解公式推导过程：
第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2k)。
假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。
3.跳表是不是很浪费内存？
看是否浪费内存，看空间复杂度。
比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。
跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
4.为什么 Redis 要用跳表来实现有序集合，而不是红黑树？
虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论