-
0046
算法笔记
——
【随机化算法】舍伍德随机化思想解决跳跃
表问题
问题描述
如果使用有序链表来表示包含
n
个元素的有序集
s
，在最坏的情况
下，
在
s
中搜索元素需要
O(n)
个计算时间一种提高有序链表效率的技
术是在有序链表的一些节点上添加额外的
指针，以提高其搜索性能。
当在具有附加指针的有序链表中搜索元素时，
可以通过附加指针跳过
链表中的几个节点来加快搜索速度。
这个带有前向附加指针的有序链
表被称为跳转表。
应该在跳转表的哪些节点添加额外的指针，以及应该在该节点
添加
多少指针完全由随机化方法决定这使得跳转表能够支持诸如在平均
< br>时间
0(logn)
内搜索、插入和删除有序集之类的操
作例如，如图所示，
(a)
是一个没
有附加指针的有序表，而图
(b)
在图
(a)
的基础上增加了一
个附加指针来跳转一个节点图
(c)
在图
(b)
的顶
部添加了额外的指针来
跳转
3
个节点<
/p>
在跳转表中，如果一个节点有
k+1
个指针，它被称为
k
级节点以图
(c)
中的跳转表为例，看看如何在修改后的跳转表中搜索元素
8
。搜索
从跳转表的最高级别开始，即级别<
/p>
2
。使用
2
级指
针发现元素
8
位于
节点
7
和
19
之间此时，在节点<
/p>
7
处下降到级别
1
的指针被搜索，并
且发现元素
8
位于
节点
7
和
13
之间最后，节的情况虽然它可以有效
地支持成员搜索操作，
但它
不适合集合中的动态变化。
集合元素的插
入和删除会破坏完整跳
转表的原始平衡状态，
影响后续元素搜索的效
率。
为了在动态变化中保持跳转表中附加指针的平衡
，跳转表中
K
级节
点的数量必须保持在
点数总和的一定比例内。
请注意，
在完整的跳转
表中，
50%
的指针是
0
级指针；
25%
的指针是
< br>1
级指针；
…
；
(100/2
(k+1))%
指针是
k
级指针因此，当插入元素时，以概率
1/2
引入
0
级
节点，以概率
1/4
引入
1
级节点，
...
并且以概率
1/2 <
/p>
(k+1)
引入
k
级节
点另一方面，
I
级节点指向同一
级别或更高级别的下一个节点，它跳
过的节点数不再精确地保持在
2
I-1
在这种修改之后，当插入或删除
< br>一个元素时，跳转表的平衡可以通过本地修改来维护。
跳转表中的节点级别在插入中确定，一旦确定就不会更改。下图是
遵循上述原则的跳转表示例。
搜索它就像搜索一个完整的跳转表一样
< br>如果要将元素
8
插入所示的跳转表中，
< br>现在应该在跳转表中搜索其插
入位置。在搜索之后，发现元素
8
应该被插入到节点
7
和
11
之间。
此时，在节点
7
和
11
之间添加新的节点存储元件
8
，并且以随机方
式确定新节点的级别
。例如，如果元素
8
作为
2
级节点插入，则图中虚线
所相交的指针应该被调整。如果新插入的节点是
1
级节点，则只需
要修改两个指针，
虚线交叉的指针是可以修改的指针。
当搜索插入期
间使用的元素的插入位置时，可以动态保存这些指针。
在一个
完整的跳转表中，一半具有
I
级指针的节点同时具有
i+1
级
指针为了保持跳转表的平衡，可以预先确
定一个实数
016)%
n
；
34.}
35.
36 . double random::f ra
ndom(void)//
生成随机实数
37
< br>。
{
38 .
return random(max short)/double(max
short)
；
39.}
2
，
7d3d3
。
CPP
[CPP]
视图普通副本
1
。
//
随机化算法跳转
表
2
。
#
包含
3
。
#
包含
4
。
#
包括
5
。
# include 6
.
使用命名空间标准；
7.
8
。模板类
SkipList9.
模板
10
。
SkipNo
de 11
类。
{
12
。朋友
SkipList13.
私人
:
<
/p>
14
。
SkipNode(int
大小
)15
。
{
16
。
next
=
新
Skipnode *[
大小
]
；
17.}
18
。
~SkipNode()
19
。
{
20
。删除
[]
下一步；
21.}
22
。
EType
数据；
//
元素
23
。
SkipNode
*
*
集合中的下一个；
//[
下一个指针数组是一级指针
24
。
}
；
25.
26
。模板
27
。
SkipList
28
级。
{
29
。公众
:
30
。
Sk
ipList(KType
大，
int MaxE =
10000
，浮点
p =
0.5)
；
31
。
~
Skiplist()
；
-
-
-
-
-
-
-
-
-
上一篇：matlab 常用指令
下一篇：圣诞节英文手抄报内容