跳表实现详解：一种概率型数据结构
需积分: 10 96 浏览量
更新于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页未读，继续阅读
点击了解资源详情
120 浏览量
点击了解资源详情
2012-03-20 上传
161 浏览量
151 浏览量
133 浏览量
2010-07-05 上传
陈明建
- 粉丝: 1
- 资源: 7
我的内容管理
展开
最新资源
- chromepass-stealer:该程序可从chrome数据库中提取密码，并通过解密并将其以表格形式呈现给人类，以可读的形式呈现。如果有未安装的模块错误，请执行-“ pip3 install pycryptodome pypiwin32”
- 英语单词字典-crx插件
- 高空
- 西储大学轴承故障数据读取GUI_gui数据_故障gui_故障_西储大学；故障诊断；GUI设计_西储
- 易语言超级列表框批量打印
- Hello-Python:最近，很多人向我询问他们可以学习的编程语言，这对于绝对的初学者来说并不难，并且确实可以帮助他们开发出出色的产品。 因此，我对他们的建议是“ Python”。 Python是一种通用的编程语言，它确实快速，强大，并且具有大量方便的库。 互联网是学习语言的重要资源，但是找到正确的材料可能是一项繁琐的工作。 这就像在大海捞针中找到一根针。 因此，我创建此网站的主要目的是帮助初学者轻松学习该语言。 计算机科学爱好者，快来看看！ 网站
- tellme:TellMe 是一个工具包，可根据代码中发生的事情创建*面向用户的报告*
- Tabs Navigator-crx插件
- jpbasic1:Java欢迎
- 打字稿-jwt-1
- Haraka：快速，高度可扩展的，事件驱动的SMTP服务器
- 易语言超级列表框批量删除
- 面向5G通信网的D2D技术综述_5gresource_5G资源分配_5G_5gD2D_基站缓存
- ongaku:本地文件的 http 音乐播放器可通过 chrome tab 流式传输到 chromecast
- search-extension:搜索扩展名以从Google驱动器和投递箱中获取结果
- 弹出多个动画菜单特效
