麻省理工大学算法导论lecture11

《麻省理工大学算法导论lecture11》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture11Prof.ErikDemaineDynamicorderstatisticsOS-SELECT(i,S):returnstheithsmallestelementinthedynamicsetS.OS-RANK(x,S):returnstherankofx∈SinthesortedorderofS’selements.IDEA:Useared-blacktreeforthesetS,butkeepsubtreesizesinthenode

2、s.keykeyNotationfornodes:sizesize©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.2ExampleofanOS-treeMM99CCPP5533AAFFNNQQ11331111DDHH1111size[x]=size[left[x]]+size[right[x]]+1©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.3SelectionImplementationtrick:Usea

3、sentinel(dummyrecord)forNILsuchthatsize[NIL]=0.OS-SELECT(x,i)⊳ithsmallestelementinthesubtreerootedatxk←size[left[x]]+1⊳k=rank(x)ifi=kthenreturnxifi

4、AlgorithmsDay20L11.4ExampleOS-SELECT(root,5)i=5MMk=699i=5CCPPk=25533AAFFi=3NNQQ1133k=21111DDHHi=11111k=1Runningtime=O(h)=O(lgn)forred-blacktrees.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.5DatastructuremaintenanceQ.Whynotkeeptheranksthemselvesinthenodesinsteado

5、fsubtreesizes?A.Theyarehardtomaintainwhenthered-blacktreeismodified.Modifyingoperations:INSERTandDELETE.Strategy:Updatesubtreesizeswheninsertingordeleting.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.6ExampleofinsertionINSERT(“K”)MM109109CCPP565633AAFFNNQQ1134341

6、111DDHH111212KK11©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.7HandlingrebalancingDon’tforgetthatRB-INSERTandRB-DELETEmayalsoneedtomodifythered-blacktreeinordertomaintainbalance.•Recolorings:noeffectonsubtreesizes.•Rotations:fixupsubtreesizesinO(1)time.Example:EE

7、CC16161616CCEE471111887334∴RB-INSERTandRB-DELETEstillruninO(lgn)time.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay20L11.8Data-structureaugmentationMethodology:(e.g.,order-statisticstrees)1.Chooseanunderlyingdatastructure(red-blacktrees).2.Determineadditionalinformation

8、tobestoredinthedatastructure(subtreesizes).3.Verifythatthisinformati