跳表

今天植树节，小雨。万物复苏，生机勃勃的春天来了。为了更好的自己，继续加油。

一、什么是跳表？

为一个值有序的链表建立多级索引，比如每 2 个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。像这种为链表建立多级索引的数据结构就称为跳表。

二、跳表的时间复杂度？

1. 计算跳表的高度

如果链表有 n 个节点，每 2 个节点抽取抽出一个节点作为上一级索引的节点，那第 1 级索引的节点个数大约是 n/2，第 2 级索引的节点个数大约是 n/4，依次类推，第 k 级索引的节点个数就是 n/(2^k)。假设索引有 h 级别，最高级的索引有 2 个节点，则有 n/(2^h)=2，得出 h=log2n-1，包含原始链表这一层，整个跳表的高度就是 log2n。

1. 计算跳表的时间复杂度

假设我们在跳表中查询某个数据的时候，如果每一层都遍历 m 个节点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。那这个 m 是多少呢？如下图所示，假设我们要查找的数据是 x，在第 k 级索引中，我们遍历到 y 节点之后，发现 x 大于 y，小于后面的节点 z，所以我们通过 y 的 down 指针，从第 k 级下降到第 k-1 级索引。在第 k-1 级索引中，y 和 z 之间只有 3 个节点（包含 y 和 z），所以，我们在 k-1 级索引中最多只需要遍历 3 个节点，以此类推，每一级索引都最多只需要遍历 3 个节点。所以 m=3。因此在跳表中查询某个数据的时间复杂度就是 O(logn)。

三、跳表的空间复杂度及如何优化？

1. 计算索引的节点总数

如果链表有 n 个节点，每 2 个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和 n-1，所以跳表的空间复杂度为 O(n)。

1. 如何优化时间复杂度

如果链表有 n 个节点，每 3 或 5 个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以 3 为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和 n/2，所以跳表的空间复杂度为 O(n)，和每 2 个节点抽取一次相比，时间复杂度要低不少呢。

四、高效的动态插入和删除？

跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为 O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是 O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是 O(logn)。

五、跳表索引动态更新？

当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值 K，那就可以把这个节点添加到第 1 级到第 K 级索引中。