type-safe red-black trees with java generics

《type-safe red-black trees with java generics》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Type-SafeRed-BlackTreeswithJavaGenericsStefanKahrsUniversityofKentatCanterburyDepartmentofcomputerSciencesmk@kent.ac.ukAbstract.JavaGenerics[1]areapowerfulextensionofJava’sclasssys-tem,allowingthestatictypecheckertoensure(astheirmosttypicalapplication)thetype-safeusage

2、ofhomogeneouscollections.Thepapershowsthattheexpressivenessofgenericsgoesaverylongway,byusingthemtoenforcethetreebalancinginared-blacktreeimplementation.TheideaoriginatesfromFunctionalProgramming[2,3],thoughJavaGenericsaretoodifferenttoallowaone-to-oneadaptation.Basedon

3、experienceswiththisapplication,anumberofsuggestionsaremadefortheimprovementofJavaGenerics.1IntroductionJavaGenericscameaboutasaresponsetoalong-standingprobleminJava:theneedfordynamictypecastsusedtomakemanyJavaprogramspotentiallyunsafe,withthepossibilityofclasscastexcep

4、tionsatrun-time.Inthelate1990sPhilWadleretal.[4,5]showedhowtheJavalanguagecouldbeextendedtoprovidedforaricherstaticanalysisthatwouldallowtoeliminatedynamiccastsalmostentirely.SinceJava5theseideashaveenteredthelanguagestandard[6].Red-blacktreesprovideawell-knownwayofimp

5、lementingbalanced2-3-4treesasbinarytrees.Theywereoriginallyintroduced(underadifferentname)in[7]andarenowadaysextensivelydiscussedinthestandardliteratureonalgo-rithms[8,9].Thebasicoperationsforsearch-trees(search,insertion,deletion)arerealisedinO(log(n))time,fortreesizen

6、.Red-blacktreesarebinarysearchtreeswithanadditional“colour”fieldwhichiseitherredorblack.Therootofthetreewillalwaysbeblack.Inared-blacktreeeachrednodeisrequiredtohaveblacksubtreesandisregardedasanintermediateauxiliarynode.Allbinarynodesarerequiredtobeofthesameblackheight

7、,whichisthenestingdepthofbinaryblacknodes.Therefore,everybinaryblacknodehasablackheightofn+1,wherenistheblackheightofitssubtrees.Moreover,viewingrednodesonlyasauxiliarynodes,ablackbinarynodeofheightn+1hasbetween2and4blacksubtreesofheightn,dependingonwhether0,1or2ofitsd

8、irectsubtreeshaveredroots.Thisisthereasonwhyred-blacktreescanbeseenasanimplementationof2-3-4trees.Sincethemid1990sith