文章目录

• 一、跳跃表简介
• • 1. 跳跃表引入
  • 2. 跳跃表定义
  • 3. 跳跃表的几种阶数
• 二、跳跃表分析
• • 1. 节点描述
  • 2. 查找算法
  • 3. 阶数选择
  • 4. 插入算法
  • 5. 删除算法
• 三、跳跃表实现
• • 1. 节点实现类`_SkipNode`
  • 2. 初始化方法`__init__`
  • 3. 返回跳跃表节点个数方法`__len__`
  • 4. 节点封装方法`_make_node`
  • 5. 节点最高阶数生成方法`_random_lvl`
  • 6. 跳跃表查找实用方法`_utility_search`
  • 7. 跳跃表节点查找方法`skip_search`
  • 8. 跳跃表节点插入方法`skip_insert`
  • 9. 跳跃表节点删除方法`skip_delete`
  • 10. 跳跃表按节点阶数遍历方法`skip_display`
• 四、跳跃表效率分析
• 五、跳跃表完整测试代码

对于之前通过列表保存键值对的方式所实现的类字典映射，当映射中的键值对按照键的大小排序时，由于可以利用二分查找算法，因此查找某键值对可实现$O(logn)$的最坏时间复杂度，但由于对映射进行增和删这样的修改类操作的最坏时间复杂度为$O(n)$（当在列表索引为0的位置增和删元素需要移动移动所有其他位置的元素），因此M[k] = v和del M[k]（M为映射实例对象）操作的最坏时间复杂度为$O(n)$。

事实上，在已知某节点位置的情况下，单链表可以在该位置处实现最坏时间复杂度为$O(1)$的节点增删等修改类操作，但单链表的缺点是不能像列表一样支持根据索引快速的进行查找操作，而是需要从头遍历链表。

因此，为了既能够实现快速的查找也能够实现快速的修改操作，本文即将介绍的跳跃表就通过改善链表在查找和修改操作之间找到了较好的效率平衡。

一、跳跃表简介

1. 跳跃表引入

首先，我们通过对普通单向线性链表进行一步一步的延展来引出跳跃表，假定单链表中元素有序排列：

• 如果需要对以下一般链表进行查找操作，则最坏时间复杂度为$O(n)$；

• 如果在上述一般链表基础上，每$2^1=2$个节点，都有1个节点还保存了从其位置往后第$2^1=2$个节点的引用（如头结点除保存了元素3所在节点的引用，还保存了元素6所在节点的引用），此时查找操作的最坏时间复杂度为$\lceil n/2^1\rceil +1$；

• 如果在上述链表基础上，每$2^2=4$个节点中，都有1个节点还保存了从其位置往后第$2^2=4$个节点的引用（如头结点除保存了元素3和6所在节点的引用，还保存了元素9所在节点的引用），此时查找操作的最坏时间复杂度为$\lceil n/2^2\rceil +2$；

• 如果在上述链表基础上，每$2^3=8$个节点中，都有1个节点还保存了从其位置往后第$2^3=8$个节点的引用（如头结点除保存了元素3、6和9所在节点的引用，还保存了元素21所在节点的引用），此时查找操作的最坏时间复杂度为$\lceil n/2^3\rceil +3$；

因此，一般地，如果在普通链表基础上，对于所有满足$2^i<n$的正整数$i$（即$i\le \lceil {\log }_{2}n\rceil$），每$2^i$个节点中，都有1个节点还保存了从其位置往后第$2^i$个节点的引用，此时查找操作的最坏时间复杂度为$\lceil {\log }_{2}n\rceil$。

2. 跳跃表定义

上述经逐步优化的链表虽然可实现较为高效的查找操作，但是增删节点等修改类操作却十分不易实现，为此下面正式引入跳跃表：

首先，为描述方便，如果每$2^i$个节点中，都有1个节点还保存了从其位置往后第$2^i$个节点的引用，我们就称该节点具有$i$阶引用，需要注意的是，这意味该节点还具有$i-1$、$i-2$、$\cdot \cdot \cdot$、$1$阶引用。

基于以上假设，对于上述逐步优化的链表，其中100%的节点具有1阶引用，50%的节点具有2阶引用，25%的节点具有3阶引用，12.5%的节点具有4阶引用，以此类推。

然而，如果我们假设所有节点所具有的最高引用阶数为不大于$\lceil {\log }_{2}n\rceil$的随机值，且仅限定具有不同最高阶引用的节点数量间的比例保持不变（如下图所示），这就形成了所谓的跳跃表（Skip List）。

此时，任意节点的$i$阶引用并非一定指向从其位置开始第$2^{i-1}$个节点，而是任何下一个至少具有$i$阶引用节点或NIL（表示跳跃表的尾哨兵节点）。

事实上，上述跳跃表的特征是具有$i$阶引用的节点数量为具有$i-1$阶引用节点数量的$1/2$（其中$i$为正整数且$i\le \lceil {\log }_{2}n\rceil$），一般地跳跃表中该比例可以是$1/p$（其中$p$是任意正整数），且跳跃表中任意节点所具有的最高阶数为$\lceil lo{g}_{1/p}n\rceil$，其中$n$为跳跃表当前所能容纳节点的最大数量。

3. 跳跃表的几种阶数

关于跳跃表的引用阶数，有如下几个不同的定义：

• 跳跃表最大引用阶数：一般用MaxLevel表示，决定了跳跃表节点可能拥有的最高引用阶数，该阶数确保在跳跃表中的节点个数不超过$p^{MaxLevel}$个时，跳跃表的相关操作效率不会大幅降低；
• 节点最大引用阶数：一般用lvl表示，代表某具体节点所拥有的最高引用阶数；
• 跳跃表当前引用阶数：一般用level表示，代表跳跃表所有的节点中，最高引用阶数的最大值。

一般而言，上述三个值之间的相对大小关系为lvl <= level <= MaxLevel。

二、跳跃表分析

本节将开始介绍当跳跃表的每一个节点按照键的大小保存了键值对后，如何查找、插入和删除某键值对，其中：

• 查找操作将返回和键相关的键值对，或当键不存在时抛出异常；
• 插入操作将新增节点并保存键值对，当键已存在则替换原键对应的值；
• 删除操作将删除和键相关的键值对，或当键不存在时抛出异常。

1. 节点描述

一般地，一个跳跃表的节点可以如下图表示，即存在：

• 保存键值对的元素域；
• 保存后续若干个节点引用的指针域：

2. 查找算法

当需要查找跳跃表中某一个键值对时，需要从头节点的最高阶引用开始往后遍历，在当前节点最高阶引用所指向的下一个节点的键第一次大于待搜索的键时，沿着当前节点的次阶引用继续搜索，如果假定待搜索的键值对在跳跃表中，则要么一直到沿着节点的1阶引用进行搜索后找到了期望的节点，或者在此之前就已经可以找到。

为了对上述流程进行更清晰的描述，下图描述了当在跳跃表中搜索键为19的键值对时的搜索路径：

针对上述分析，下面先给出跳跃表的搜索算法的伪代码：

SkipSearch(list, searched_key)x := list->headerfor i := list->level downto 1 do:while x->forward[i]->key < searched_key do:x := x->forward[i]/* 执行上述代码后，必定有：x->key < searched_key <= x->forward[1]->key */x := x->forward[1]if x->key = searched_key then:return x-> valueelse:return False

3. 阶数选择

在介绍插入算法之前，需要确定后续新插入节点所具有的最高引用阶数。如前所述，对于新插入的节点，其最高引用阶数满足以下两点：

• 首先是小于$\lceil lo{g}_{1/p}n\rceil$的正整数即可；
• 其次是$1/p$具有$i$阶引用的节点也具有$i+1$阶引用。

针对上述分析，下面给出生成节点最高引用阶数的伪代码：

randomLevel()lvl := 1// random()函数生成[0.0, 1.0)之间的随机浮点数while random() < p and lvl < MaxLevel do:lvl := lvl + 1return lvl

需要注意的是，对于一个跳跃表，任意节点所具有的最高阶数为$\lceil lo{g}_{1/p}n\rceil$，一般将其记为MaxLevel。

4. 插入算法

为正确地向跳跃表中插入一个节点，需要：

• 先查找到从左起最后一个满足特定条件的节点，即该节点元素域的键小于待插入节点元素域的键；
• 然后将待插入节点置于上述节点之后，最后将待插入节点和其前后节点之间进行链接。

为更清晰地对跳跃表插入算法进行描述，下图给出了对跳跃表进行节点17进行插入前后的描述：

需要注意的是，为了能够在上述插入算法的第二步正确地进行节点链接，在第一步查找的过程中，需要使用数组变量cursor，使得cursor[i]保存至少具有$i$阶引用的节点，且该节点不仅需要满足在待插入节点左侧，还需满足距离待插入节点距离最近。例如：

• cursor[4]保存了元素域的键为6的节点引用；
• cursor[3]保存了元素域的键为6的节点引用；
• cursor[2]保存了元素域的键为9的节点引用；
• cursor[1]保存了元素域的键为12的节点引用；

针对上述分析，下面先给出跳跃表的插入算法的伪代码：

SkipInsert(list, key2search, value2insert)cursor[1..MaxLevel]x := list->headerfor i := list->level downto 1 do:while x->forward[i]->key < key2search do:x := x->forward[i]/* 执行上述代码后，必定有：x->key < searched_key <= x->forward[1]->key */cursor[i] = xx := x->forward[1]if x->key = key2search then:x->value := value2insertelse:lvl := randomLevel()if lvl > list->level then:for i := list->level + 1 to lvl do:cursor[i] := list->headerlist->level := lvlx := makeNode(lvl, key2search, value2insert)for i := 1 to list->level do:// 先将新节点和其右侧节点进行链接x->forward[i] := cursor[i]->forward[i]// 然后将新节点和其左侧节点进行链接cursor[i]->forward[i] := x

5. 删除算法

跳跃表的节点删除算法可以视为插入算法的逆操作，只需要：

• 先遍历整个跳跃表找到从左起最后一个满足特定条件的节点，即该节点元素域的键小于待删除节点元素域的键；
• 然后同样需要使用数组变量cursor，使得cursor[i]保存至少具有$i$阶引用的节点，且该节点不仅需要满足在待插入节点左侧，还需满足距离待插入节点距离最近；
• 最后将待删除节点的左右节点进行直接链接以旁路待删除节点即可（如使用需程序员手动管理内存的语言实现如：C语言，还需要释放待删除节点的内存空间）。

下面是节点删除算法的伪代码：

SkipDelete(list, key2search)cursor[1..MaxLevel]x := list->headerfor i := list->level downto 1 do:while x->forward[i]->key < key2search do:x := x->forward[i]cursor[i] := xx := x->forward[1]if x->key == key2search then:for i := 1 to list->level do:if cursor[i]->forward[i] != x then:// 循环从i = 0开始，如从i = self.level开始则使用continue，但不如使用break相对高效breakelse:// 直接通过链接待删除节点的左右节点cursor[i]->forward[i] := x->forward[i]free(x)// 当跳跃表中存在头节点的某阶引用直接指向尾部哨兵节点时，跳跃表当前阶数需降低while list->level > 1 and list->header->forward[list->level] == NIL do:list->level := list->level - 1

三、跳跃表实现

1. 节点实现类_SkipNode

class _SkipNode:"""表示跳跃表节点的类"""def __init__(self, key, value, level):self.key = keyself.value = valueself.forward = [None] * (level + 1)def __str__(self):return '(' + str(self.key) + ', ' + str(self.value) + ')'

2. 初始化方法__init__

def __init__(self, max_level, portion):"""创建一个空的跳跃表:param max_level: 跳跃表所有节点引用所可能达到的最高阶数:param portion: 具有i-1阶节点引用同时具有i阶引用的比例"""self.MAX_LEVEL = max_levelself.portion = portionself.header = self._make_node(self.MAX_LEVEL, None, None)self.level = 0  # 跳跃表当前引用阶数self.n = 0

3. 返回跳跃表节点个数方法__len__

def __len__(self):"""返回跳跃表的节点个数"""return self.n

4. 节点封装方法_make_node

def _make_node(self, lvl, key, value):"""创建新的跳跃表节点:param lvl: 新节点所具有的最高引用阶数:param key: 键:param value: 值:return: 新节点的引用"""node = _SkipNode(key, value, lvl)return node

5. 节点最高阶数生成方法_random_lvl

def _random_lvl(self):"""生成新节点的最高引用阶数:return: 新节点的最高引用阶数"""lvl = 0while random.random() < self.portion and lvl < self.MAX_LEVEL:lvl += 1return lvl

6. 跳跃表查找实用方法_utility_search

def _utility_search(self, key2search):"""查找的实用非公有方法:param key2search: 待查找节点的键:return: 元组"""cursor = [None] * (self.MAX_LEVEL + 1)current = self.headerfor i in range(self.level, -1, -1):# 当跳跃表为空时，current.forward[0]为Nonewhile current.forward[i] and current.forward[i].key < key2search:current = current.forward[i]cursor[i] = currentcurrent = current.forward[0]return current, cursor

7. 跳跃表节点查找方法skip_search

def skip_search(self, key2search):"""在跳跃表中查找并返回键为key2search的键值对，当不存在时抛出KeyError异常"""current, _ = self._utility_search(key2search)if current and current.key == key2search:return currentelse:raise KeyError('key {} does not exist!'.format(key2search))

8. 跳跃表节点插入方法skip_insert

def skip_insert(self, key2search, value2insert):"""向跳跃表中插入由键值对封装后得到的节点"""current, cursor = self._utility_search(key2search)if current and current.key == key2search:current.value = value2insertelse:lvl = self._random_lvl()if lvl > self.level:for i in range(self.level + 1, lvl + 1):cursor[i] = self.headerself.level = lvlnode = self._make_node(lvl, key2search, value2insert)for i in range(lvl + 1):node.forward[i] = cursor[i].forward[i]cursor[i].forward[i] = nodeself.n += 1

9. 跳跃表节点删除方法skip_delete

def skip_delete(self, key2search):"""从跳跃表中删除键为key2search的节点"""current, cursor = self._utility_search(key2search)if current is not None and current.key == key2search:ret = currentfor i in range(self.level + 1):if cursor[i].forward[i] != current:break  # 循环从i = 0开始，如从i = self.level开始则使用continue，但不如使用break相对高效cursor[i].forward[i] = current.forward[i]while self.level > 0 and self.header.forward[self.level] is None:self.level -= 1self.n -= 1return ret

10. 跳跃表按节点阶数遍历方法skip_display

def skip_display(self):print("\n*****Skip List******")header = self.headerfor lvl in range(self.level + 1):print("Level {}: ".format(lvl), end=" ")node = header.forward[lvl]while node is not None:print(node.key, end=" ")node = node.forward[lvl]print('')

四、跳跃表效率分析

方法名称	时间复杂度
__len__	$O(1)$
skip_search	$O(logn)$
skip_insert	$O(logn)$
skip_delete	$O(logn)$

五、跳跃表完整测试代码

import randomclass _SkipNode:"""表示跳跃表节点的类"""def __init__(self, key, value, level):self.key = keyself.value = valueself.forward = [None] * (level + 1)def __str__(self):return '(' + str(self.key) + ', ' + str(self.value) + ')'class SkipList:"""跳跃表具体实现类"""def __init__(self, max_level, portion):"""创建一个空的跳跃表:param max_level: 跳跃表所有节点引用所可能达到的最高阶数:param portion: 具有i-1阶节点引用同时具有i阶引用的比例"""self.MAX_LEVEL = max_levelself.portion = portionself.header = self._make_node(self.MAX_LEVEL, None, None)self.level = 0  # 跳跃表当前引用阶数self.n = 0def __len__(self):"""返回跳跃表的节点个数"""return self.ndef _make_node(self, lvl, key, value):"""创建新的跳跃表节点:param lvl: 新节点所具有的最高引用阶数:param key: 键:param value: 值:return: 新节点的引用"""node = _SkipNode(key, value, lvl)return nodedef _random_lvl(self):"""生成新节点的最高引用阶数:return: 新节点的最高引用阶数"""lvl = 0while random.random() < self.portion and lvl < self.MAX_LEVEL:lvl += 1return lvldef _utility_search(self, key2search):"""查找的实用非公有方法:param key2search: 待查找节点的键:return: 元组"""cursor = [None] * (self.MAX_LEVEL + 1)current = self.headerfor i in range(self.level, -1, -1):# 当跳跃表为空时，current.forward[0]为Nonewhile current.forward[i] and current.forward[i].key < key2search:current = current.forward[i]cursor[i] = currentcurrent = current.forward[0]return current, cursordef skip_search(self, key2search):"""在跳跃表中查找并返回键为key2search的键值对，当不存在时抛出KeyError异常"""current, _ = self._utility_search(key2search)if current and current.key == key2search:return currentelse:raise KeyError('key {} does not exist!'.format(key2search))def skip_insert(self, key2search, value2insert):"""向跳跃表中插入由键值对封装后得到的节点"""current, cursor = self._utility_search(key2search)if current and current.key == key2search:current.value = value2insertelse:lvl = self._random_lvl()if lvl > self.level:for i in range(self.level + 1, lvl + 1):cursor[i] = self.headerself.level = lvlnode = self._make_node(lvl, key2search, value2insert)for i in range(lvl + 1):node.forward[i] = cursor[i].forward[i]cursor[i].forward[i] = nodeself.n += 1def skip_delete(self, key2search):"""从跳跃表中删除键为key2search的节点"""current, cursor = self._utility_search(key2search)if current is not None and current.key == key2search:ret = currentfor i in range(self.level + 1):if cursor[i].forward[i] != current:break  # 循环从i = 0开始，如从i = self.level开始则使用continue，但不如使用break相对高效cursor[i].forward[i] = current.forward[i]while self.level > 0 and self.header.forward[self.level] is None:self.level -= 1self.n -= 1return retdef skip_display(self):print("\n*****Skip List******")header = self.headerfor lvl in range(self.level + 1):print("Level {}: ".format(lvl), end=" ")node = header.forward[lvl]while node is not None:print(node.key, end=" ")node = node.forward[lvl]print('')if __name__ == '__main__':skip_list = SkipList(10, 0.5)skip_list.skip_insert(3, 5)skip_list.skip_insert(12, 9)skip_list.skip_insert(26, 7)skip_list.skip_insert(7, 13)skip_list.skip_insert(21, 3)skip_list.skip_insert(25, 4)skip_list.skip_insert(6, 6)skip_list.skip_insert(17, 8)skip_list.skip_insert(19, 10)skip_list.skip_insert(9, 14)print(len(skip_list))  # 10print(skip_list.skip_search(3))  # (3, 5)print(skip_list.skip_delete(19))  # (19, 10)print(len(skip_list))  # 9skip_list.skip_display()

*****Skip List******
Level 0: 3 6 7 9 12 17 21 25 26
Level 1: 6 12 17 21
Level 2: 17
Level 3: 17