0046算法笔记随机化算法舍伍德随机化思想解决跳跃表问题.docx
- 文档编号:11012891
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:16
- 大小:64.11KB
0046算法笔记随机化算法舍伍德随机化思想解决跳跃表问题.docx
《0046算法笔记随机化算法舍伍德随机化思想解决跳跃表问题.docx》由会员分享,可在线阅读,更多相关《0046算法笔记随机化算法舍伍德随机化思想解决跳跃表问题.docx(16页珍藏版)》请在冰点文库上搜索。
0046算法笔记随机化算法舍伍德随机化思想解决跳跃表问题
问题描述
如果用有序链表来表示一个含有n个元素的有序集S,则在最坏情况下,搜索S中一个元素需要O(n)计算时间。
提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。
在增设附加指针的有序链表中搜索一个元素时,可借助于附加指针跳过链表中若干结点,加快搜索速度。
这种增加了向前附加指针的有序链表称为跳跃表。
应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。
这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。
例如:
如图,(a)是一个没有附加指针的有序表,而图(b)在图(a)的基础上增加了跳跃一个节点的附加指针。
图(c)在图(b)的基础上又增加了跳跃3个节点的附加指针。
在跳跃表中,如果一个节点有k+1个指针,则称此节点为一个k级节点。
以图(c)中跳跃表为例,看如何在改跳跃表中搜索元素8。
从该跳跃表的最高级,即第2级开始搜索。
利用2级指针发现元素8位于节点7和19之间。
此时在节点7处降至1级指针进行搜索,发现元素8位于节点7和13之间。
最后,在节点7降至0级指针进行搜索,发现元素8位于节点7和11之间,从而知道元素8不在搜索的集合S中。
相关原理
在一般情况下,给定一个含有n个元素的有序链表,可以将它改造成一个完全跳跃表,使得每一个k级结点含有k+1个指针,分别跳过2^k-1,2^(k-1)-1,…,2^0-1个中间结点。
第i个k级结点安排在跳跃表的位置i2^k处,i>=0。
这样就可以在时间O(logn)内完成集合成员的搜索运算。
在一个完全跳跃表中,最高级的结点是
级结点。
完全跳跃表与完全二叉搜索树的情形非常类似。
它虽然可以有效地支持成员搜索运算,但不适应于集合动态变化的情况。
集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态,影响后继元素搜索的效率。
为了在动态变化中维持跳跃表中附加指针的平衡性,必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。
注意到在一个完全跳跃表中,50%的指针是0级指针;25%的指针是1级指针;…;(100/2^(k+1))%的指针是k级指针。
因此,在插入一个元素时,以概率1/2引入一个0级结点,以概率1/4引入一个1级结点,…,以概率1/2^(k+1)引入一个k级结点。
另一方面,一个i级结点指向下一个同级或更高级的结点,它所跳过的结点数不再准确地维持在2^i-1。
经过这样的修改,就可以在插入或删除一个元素时,通过对跳跃表的局部修改来维持其平衡性。
跳跃表中节点的级别在插入是确定,一旦确定便不再更改。
下图是遵循上述原则的跳跃表的例子。
对其进行搜索与对完全跳跃表所作的搜索是一样的。
如果希望在所示跳跃表中插入一个元素8,则应现在跳跃表中搜索其插入位置。
经搜索发现应在节点7和11之间插入元素8.此时在节点7和11之间增加1个存储元素8的新节点,并以随机的方式确定新节点的级别。
例如,如果元素8是作为一个2级节点插入,则应对图中虚线相交的指针进行调整,如果新插入的节点是一个1级节点,则只要修改2个指针,虚线相交的指针是有可能被修改的指针,这些指针可在搜索元素插入位置时动态地保存起来,以供插入时使用。
在一个完全跳跃表中,具有i级指针的结点中有一半同时具有i+1级指针。
为了维持跳跃表的平衡性,可以事先确定一个实数0
为此目的,在插入一个新结点时,先将其结点级别初始化为0,然后用随机数生成器反复地产生一个[0,1]间的随机实数q。
如果q
=p。
由此产生新结点级别的过程可知,所产生的新结点的级别为0的概率为1-p,级别为1的概率为p(1-p),…,级别为i的概率为p^i(1-p)。
如此产生的新结点的级别有可能是一个很大的数,甚至远远超过表中元素的个数。
为了避免这种情况,用
作为新结点级别的上界。
其中n是当前跳跃表中结点个数。
当前跳跃表中任一结点的级别不超过
。
算法具体实现如下:
1、RandomNumber.h
[cpp] viewplain copy
1.#include"time.h"
2.//随机数类
3.const unsigned long maxshort = 65536L;
4.const unsigned long multiplier = 1194211693L;
5.const unsigned long adder = 12345L;
6.
7.class RandomNumber
8.{
9. private:
10. //当前种子
11. unsigned long randSeed;
12. public:
13. RandomNumber(unsigned long s = 0);//构造函数,默认值0表示由系统自动产生种子
14. unsigned short Random(unsigned long n);//产生0:
n-1之间的随机整数
15. double fRandom(void);//产生[0,1)之间的随机实数
16.};
17.
18.RandomNumber:
:
RandomNumber(unsigned long s)//产生种子
19.{
20. if(s == 0)
21. {
22. randSeed = time(0);//用系统时间产生种子
23. }
24. else
25. {
26. randSeed = s;//由用户提供种子
27. }
28.}
29.
30.unsigned short RandomNumber:
:
Random(unsigned long n)//产生0:
n-1之间的随机整数
31.{
32. randSeed = multiplier * randSeed + adder;//线性同余式
33. return (unsigned short)((randSeed>>16)%n);
34.}
35.
36.double RandomNumber:
:
fRandom(void)//产生[0,1)之间的随机实数
37.{
38. return Random(maxshort)/double(maxshort);
39.}
2、7d3d3.cpp
[cpp] viewplain copy
1.//随机化算法 跳跃表
2.#include "stdafx.h"
3.#include "RandomNumber.h"
4.#include
5.#include
6.using namespace std;
7.
8.template
9.template
10.class SkipNode
11.{
12. friend SkipList
13. private:
14. SkipNode(int size)
15. {
16. next = new SkipNode
17. }
18. ~SkipNode()
19. {
20. delete []next;
21. }
22. EType data;//集合中的元素
23. SkipNode
24.};
25.
26.template
27.class SkipList
28.{
29. public:
30. SkipList(KType Large,int MaxE = 10000,float p = 0.5);
31. ~SkipList();
32. bool Search(const KType& k,EType& e) const;
33. SkipList
34. SkipList
35. void Output();
36. private:
37. int Level();
38. SkipNode
39. int MaxLevel; //跳跃表级别上界
40. int Levels; //当前最大级别
41. RandomNumber rnd; //随机数产生器
42. float Prob; //用于分配节点级别
43. KType TailKey; //元素键值上界
44. SkipNode
45. SkipNode
46. SkipNode
47.};
48.
49.//构造函数
50.template
51.SkipList
:
SkipList(KType Large,int MaxE,float p)
52.{
53. Prob = p;
54. MaxLevel = ceil(log(float(MaxE))/log(1/p))-1; //初始化跳跃表级别上界
55. TailKey = Large; //元素键值上界
56. Levels = 0; //初始化当前最大级别
57.
58. //创建头、尾节点和数组 last
59. head = new SkipNode
60. NIL = new SkipNode
61. last = new SkipNode
62. NIL->data = Large;
63.
64. //将跳跃表初始化为空表
65. for(int i=0; i<=MaxLevel; i++)
66. {
67. head->next[i] = NIL;
68. }
69.}
70.
71.//析构函数
72.template
73.SkipList
:
~SkipList()
74.{
75. SkipNode
76.
77. //删除所有节点
78. while(head!
=NIL)
79. {
80. next = head->next[0];
81. delete head;
82. head = next;
83. }
84.
85. delete NIL;
86. delete []last;
87.}
88.
89.class element
90.{
91. friend int main(void);
92. public:
93. operator long() const
94. {
95. return key;
96. }
97. element& operator = (long y)
98. {
99. key = y;
100. return *this;
101. }
102. private:
103. int data;
104. long key;
105.};
106.
107.//搜索指定元素k
108.template
109.bool SkipList
:
Search(const KType& k,EType& e) const
110.{
111. if(k>=TailKey)
112. {
113. return false;
114. }
115. //位置p恰好位于指定元素k之前
116. SkipNode
117. for(int i=Levels; i>=0; i--)//逐渐向下搜索
118. {
119. while(p->next[i]->data 120. { 121. p = p->next[i];//每次搜索尽可能滴接近要搜索的元素 122. } 123. } 124. e = p->next[0]->data; 125. return (e==k); 126.} 127. 128.//搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中 129.template 130.SkipNode : SaveSearch(const KType& k) 131.{ 132. //位置p恰好位于指定元素k之前 133. SkipNode 134. for(int i = Levels; i>=0; i--) 135. { 136. while(p->next[i]->data 137. { 138. p = p->next[i]; 139. } 140. last[i] = p; //上一个第i级结点 141. } 142. return (p->next[0]); 143.} 144. 145.//产生不超过MaxLevel 的随机级别 146.template 147.int SkipList : Level() 148.{ 149. int lev = 0; 150. while(rnd.fRandom() 151. { 152. lev++; 153. } 154. return (lev<=MaxLevel)? lev: MaxLevel; 155.} 156. 157.//插入指定元素e 158.template 159.SkipList : Insert(const EType& e) 160.{ 161. KType k = e;//取得元素键值 162. if(k>=TailKey) 163. { 164. cout<<"元素键值超界! "< 165. return *this; 166. } 167. //检查元素是否已存在 168. SkipNode 169. if(p->data == e) 170. { 171. cout<<"元素已存在! "< 172. return *this; 173. } 174. 175. //元素不存在,确定新节点级别 176. int lev = Level(); 177. //调整个级别指针 178. if(lev>Levels) 179. { 180. for(int i=Levels+1; i<=lev; i++) 181. { 182. last[i] = head; 183. } 184. Levels = lev; 185. } 186. 187. //产生新节点,并将新节点插入p之后 188. SkipNode 189. y->data = e; 190. 191. for(int i=0; i<=lev; i++) 192. { 193. //插入第i级链 194. y->next[i] = last[i]->next[i]; 195. last[i]->next[i] = y; 196. } 197. return *this; 198.} 199. 200.//删除键值为k的元素,并将所删除的元素存入e 201.template 202.SkipList : Delete(const KType& k,EType& e) 203.{ 204. if(k>=TailKey) 205. { 206. cout<<"元素键值超界! "< 207. } 208. //搜索待删除元素 209. SkipNode 210. if(p->data! =k) 211. { 212. cout<<"未找到待删除元素! "< 213. } 214. //从跳跃表中删除节点 215. for(int i=0; i<=Levels && last[i]->next[i] == p; i++) 216. { 217. last[i]->next[i] = p->next[i]; 218. } 219. //更新当前级别 220. while(Levels>0 && head->next[Levels] == NIL) 221. { 222. Levels--; 223. } 224. e = p->data; 225. delete p; 226. return *this; 227.} 228. 229.//输出集合中的元素 230.template 231.void SkipList : Output() 232.{ 233. SkipNode 234. for(;y! =NIL; y=y->next[0]) 235. { 236. cout< 237. } 238. cout< 239.} 240. 241.int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 0046 算法 笔记 随机化 舍伍德 思想 解决 跳跃 问题