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级指针。为了维持跳跃表的平衡性，可以事先确定一个实数0p1，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例约为p。为此目的，在插入一个新结点时，先将其结点级别初始化为0，然后用随机数生成器反复地产生一个[0，1]间的随机实数q。如果qp，则使新结点级别增加1，直至q=p。由此产生新结点级别的过程可知，所产生的新结点的级别为0的概率为1-p，级别为1的概率为p(1-p)，…，级别为i的概率为p^i(1-p)。如此产生的新结点的级别有可能是一个很大的数，甚至远远超过表中元素的个数。为了避免这种情况，用作为新结点级别的上界。其中n是当前跳跃表中结点个数。当前跳跃表中任一结点的级别不超过。算法具体实现如下：1、RandomNumber.h[cpp]viewplaincopy1.#includetime.h2.//随机数类3.constunsignedlongmaxshort=65536L;4.constunsignedlongmultiplier=1194211693L;5.constunsignedlongadder=12345L;6.7.classRandomNumber8.{9.private:10.//当前种子11.unsignedlongrandSeed;12.public:13.RandomNumber(unsignedlongs=0);//构造函数，默认值0表示由系统自动产生种子14.unsignedshortRandom(unsignedlongn);//产生0：n-1之间的随机整数15.doublefRandom(void);//产生[0,1)之间的随机实数16.};17.18.RandomNumber::RandomNumber(unsignedlongs)//产生种子19.{20.if(s==0)21.{22.randSeed=time(0);//用系统时间产生种子23.}24.else25.{26.randSeed=s;//由用户提供种子27.}28.}29.30.unsignedshortRandomNumber::Random(unsignedlongn)//产生0：n-1之间的随机整数31.{32.randSeed=multiplier*randSeed+adder;//线性同余式33.return(unsignedshort)((randSeed16)%n);34.}35.36.doubleRandomNumber::fRandom(void)//产生[0,1)之间的随机实数37.{38.returnRandom(maxshort)/double(maxshort);39.}2、7d3d3.cpp[cpp]viewplaincopy1.//随机化算法跳跃表2.#includestdafx.h3.#includeRandomNumber.h4.#includecmath5.#includeiostream6.usingnamespacestd;7.8.templateclassEType,classKTypeclassSkipList;9.templateclassEType,classKType10.classSkipNode11.{12.friendSkipListEType,KType;13.private:14.SkipNode(intsize)15.{16.next=newSkipNodeEType,KType*[size];17.}18.~SkipNode()19.{20.delete[]next;21.}22.ETypedata;//集合中的元素23.SkipNodeEType,EType**next;//指针数组next[i]是第i级指针24.};25.26.templateclassEType,classKType27.classSkipList28.{29.public:30.SkipList(KTypeLarge,intMaxE=10000,floatp=0.5);31.~SkipList();32.boolSearch(constKType&k,EType&e)const;33.SkipListEType,KType&Insert(constEType&e);34.SkipListEType,KType&Delete(constKType&k,EType&e);35.voidOutput();36.private:37.intLevel();38.SkipNodeEType,KType*SaveSearch(constKType&k);39.intMaxLevel;//跳跃表级别上界40.intLevels;//当前最大级别41.RandomNumberrnd;//随机数产生器42.floatProb;//用于分配节点级别43.KTypeTailKey;//元素键值上界44.SkipNodeEType,KType*head;//头结点指针45.SkipNodeEType,KType*NIL;//尾节点指针46.SkipNodeEType,KType**last;//指针数组47.};48.49.//构造函数50.templateclassEType,classKType51.SkipListEType,KType::SkipList(KTypeLarge,intMaxE,floatp)52.{53.Prob=p;54.MaxLevel=ceil(log(float(MaxE))/log(1/p))-1;//初始化跳跃表级别上界55.TailKey=Large;//元素键值上界56.Levels=0;//初始化当前最大级别57.58.//创建头、尾节点和数组last59.head=newSkipNodeEType,KType(MaxLevel+1);60.NIL=newSkipNodeEType,KType(0);61.last=newSkipNodeEType,KType*[MaxLevel+1];62.NIL-data=Large;63.64.//将跳跃表初始化为空表65.for(inti=0;i=MaxLevel;i++)66.{67.head-next[i]=NIL;68.}69.}70.71.//析构函数72.templateclassEType,classKType73.SkipListEType,KType::~SkipList()74.{75.SkipNodeEType,KType*next;76.77.//删除所有节点78.while(head!=NIL)79.{80.next=head-next[0];81.deletehead;82.head=next;83.}84.85.deleteNIL;86.delete[]last;87.}88.89.classelement90.{91.friendintmain(void);92.public:93.operatorlong()const94.{95.returnkey;96.}97.element&operator=(longy)98.{99.key=y;100.return*this;101.}102.private:103.intdata;104.longkey;105.};106.107.//搜索指定元素k108.templateclassEType,classKType109.boolSkipListEType,KType::Search(constKType&k,EType&e)const110.{111.if(k=TailKey)112.{113.returnfalse;114.}115.//位置p恰好位于指定元素k之前116.SkipNodeEType,KType*p=head;117.for(inti=Levels;i=0;i--)//逐渐向下搜索118.{119.while(p-next[i]-datak)//在第i级链中搜索120.{121.p=p-next[i];//每次搜索尽可能滴接近要搜索的元素122.}123.}124.e=p-next[0]-data;125.return(e==k);126.}127.128.//搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中129.templateclassEType,classKType130.SkipNodeEType,KType*SkipListEType,KType::SaveSearch