跳表实现详解：一种概率型数据结构
需积分: 10 150 浏览量
更新于2024-09-09
收藏 64KB PDF 举报
"A skip list cookbook."
跳表（Skip List）是一种高效的数据结构，由William Pugh在1989年提出。它通过概率性方法来平衡查找、插入和删除操作的时间复杂度，使得这些操作的平均时间复杂度与二叉平衡树相同，都是O(log n)。然而，跳表在实现上更为简单，执行速度更快，并且通常占用更少的内存空间。跳表的结构是由多层链表组成，每一层都是下一层的子集，最高层包含所有元素，而较低层则包含部分元素。
原始的跳表论文主要关注搜索、插入和删除操作。但在"A Skip List Cookbook"这篇文档中，作者扩展了跳表的应用范围，展示了它们在更多场景下的灵活性和实用性。
1. 搜索手指（Search Fingers）：在跳表中，搜索手指是一种优化搜索性能的技术。它允许我们在进行多次相似搜索时快速定位，减少了搜索的平均步骤。搜索手指可以在已有搜索路径的基础上移动，提高连续查询的效率。
2. 合并（Merge）：跳表可以合并两个独立的跳表，创建一个新的跳表，其中包含了两个原始跳表的所有元素。这个合并算法在时间复杂度上优于之前针对二叉平衡树的合并算法，使得在处理大量数据集合的合并时更为高效。
3. 分割（Split）：跳表的分割操作允许我们将一个跳表拆分为两个，这在需要将数据集分成两个独立部分或进行分布式计算时非常有用。这个过程快速且简单，保持了原有的时间复杂度。
4. 连接（Concatenate）：跳表的连接操作可以将两个跳表串接在一起，形成一个新的跳表。这对于数据的有序合并或者处理动态变化的数据流很有帮助。
5. 线性列表操作：跳表还可以用于实现线性列表的常见操作，如插入、删除和遍历，而且这些操作的效率和简便性都优于传统的线性列表实现。例如，跳表在插入新元素时，只需要沿着各级链表向上移动，找到合适的位置进行插入，无需像线性列表那样从头到尾扫描。
"A Skip List Cookbook"深入探讨了跳表的高级用法，提供了更多关于如何利用跳表解决实际问题的策略。这些扩展的算法不仅保持了跳表的基本优势，还增加了其在各种复杂场景中的适应性。对于那些需要处理大规模数据并寻求高效解决方案的程序员和系统设计者来说，跳表是一个非常有价值的工具。
A Skip List Cookbook
4
Search(list, searchKey)
x := list→header
-- loop invariant: x→key < searchKey
for i := list→level downto 1 do
while x→forward[i]→key < searchKey do
x := x→forward[i]
-- x→key < searchKey
≤
x→forward[1]→key
x := x→forward[1]
if x→key = searchKey then return x→value
else return failure
FIGURE 2 - Skip list search algorithm
Insert(list, searchKey, newValue)
local update[1..MaxLevel]
x := list→header
for i := list→level downto 1 do
while x→forward[i]→key < searchKey do
x := x→forward[i]
update[i] := x
x := x→forward[1]
if x→key = searchKey then x→value := newValue
else
newLevel := randomLevel()
if newLevel > list→level then
for i := list→level + 1 to newLevel do
update[i] := list→header
list→level := newLevel
x := makeNode(newLevel , searchKey, value)
for i := 1 to newLevel do
x→forward[i] := update[i]→forward[i]
update[i]→forward[i] := x
Delete(list, searchKey)
local update[1..MaxLevel]
x := list→header
for i := list→level downto 1 do
while x→forward[i]→key < searchKey do
x := x→forward[i]
update[i] := x
x := x→forward[1]
if x→key = searchKey then
for i := 1 to list→level do
if update[i]→forward[i] ≠ x then break
update[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
FIGURE 3 - Insertion and deletion algorithms
The Delete operation deletes the specified key.
Each element is represented by a node, the level of
which is chosen randomly when the node is inserted
without regard for the number of elements in the data
structure. A level i node has i forward pointers, indexed
1 through i. We do not need to store the level of a node
in the node. Levels are capped at some appropriate con-
stant MaxLevel. The level of a list is the maximum level
currently in the list (or 1 if the list is empty). The
header of a list has forward pointers at levels one
through MaxLevel. The forward pointers of the header
at levels higher than the current maximum level of the
list point to NIL.
Initialization
An element NIL is given a key greater than any legal
key. All levels of all skip lists are terminated with NIL.
A new list is initialized so that the level of the list is
equal to 1 and all forward pointers of the list’s header
point to NIL.
Search Algorithm
We search for an element by traversing forward
pointers that do not overshoot the node containing the
element being searched for (Figure 2). When no more
progress can be made at the current level of forward
pointers, the search moves down to the next level.
When we can make no more progress at level 1, we
must be immediately in front of the node that contains
the desired element (if it is in the list).
Insertion and Deletion Algorithms
To insert or delete a node, we simply search and splice.
Figure 3 gives algorithms for insertion and deletion. A
vector update is maintained so that when the search is
complete (and we are ready to perform the splice),
update[i] contains a pointer to the rightmost node of
level i or higher that is to the left of the location of the
insertion/deletion. If an insertion generates a node with
a level greater than the previous maximum level of the
list, we update the maximum level of the list and
initialize the appropriate portions of the update vector.
After each deletion, we check if we have deleted the
maximum element of the list and if so, decrease the
maximum level of the list.
Generating a Random Level
Initially, we discussed a probability distribution where half of the nodes that have level i pointers also have level i+1
pointers. To get away from magic constants, we say that a fraction p of the nodes with level i pointers also have
level i+1 pointers. (for our original discussion, p = 1/2). Levels are generated randomly by an algorithm equivalent
to the one in Figure 4. Levels are generated without reference to the number of elements in the list.
剩余12页未读，继续阅读
2017-08-21 上传
2012-03-20 上传
2017-09-25 上传
2016-12-20 上传
2010-08-12 上传
2010-07-05 上传
2018-07-30 上传
164 浏览量
陈明建
- 粉丝: 1
- 资源: 7
我的内容管理
展开
最新资源
- Android圆角进度条控件的设计与应用
- mui框架实现带侧边栏的响应式布局
- Android仿知乎横线直线进度条实现教程
- SSM选课系统实现：Spring+SpringMVC+MyBatis源码剖析
- 使用JavaScript开发的流星待办事项应用
- Google Code Jam 2015竞赛回顾与Java编程实践
- Angular 2与NW.js集成：通过Webpack和Gulp构建环境详解
- OneDayTripPlanner：数字化城市旅游活动规划助手
- TinySTM 轻量级原子操作库的详细介绍与安装指南
- 模拟PHP序列化:JavaScript实现序列化与反序列化技术
- ***进销存系统全面功能介绍与开发指南
- 掌握Clojure命名空间的正确重新加载技巧
- 免费获取VMD模态分解Matlab源代码与案例数据
- BuglyEasyToUnity最新更新优化：简化Unity开发者接入流程
- Android学生俱乐部项目任务2解析与实践
- 掌握Elixir语言构建高效分布式网络爬虫
