资源描述：
《关于红黑树(Red-Black Tree)英文简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Red-BlackTreeRed-blackTreeTypeTreeInvented1972InventedbyRudolfBayerTimecomplexityinbigOnotationAverageWorstcaseSpaceO(n)O(n)SearchO(logn)O(logn)InsertO(logn)O(logn)DeleteO(logn)O(logn)Ared-blacktreeisatypeofself-balancingbinarysearchtree,adatastructureusedincomputingscience,typic
2、allyusedtoimplementassociativearrays.Theoriginalstructurewasinventedin1972byRudolfBayerwhocalledthem"symmetricbinaryB-trees",butacquireditsmodernnameinapaperin1978byLeonidasJ.GuibasandRobertSedgewick.Itiscomplex,buthasgoodworst-caserunningtimeforitsoperationsandisefficientinpract
3、ice:itcansearch,insert,anddeleteinO(logn)time,wherenistotalnumberofelementsinthetree.Putverysimply,ared-blacktreeisabinarysearchtreewhichinsertsandremovesintelligently,toensurethetreeisreasonablybalanced.TerminologyAred-blacktreeisaspecialtypeofbinarytree,usedincomputersciencetoo
4、rganizepiecesofcomparabledata,suchastextfragmentsornumbers.Theleafnodesofred-blacktreesdonotcontaindata.Theseleavesneednotbeexplicitincomputermemory—anullchildpointercanencodethefactthatthischildisaleaf—butitsimplifiessomealgorithmsforoperatingonred-blacktreesiftheleavesreallyare
5、explicitnodes.Tosavememory,sometimesasinglesentinelnodeperformstheroleofallleafnodes;allreferencesfrominternalnodestoleafnodesthenpointtothesentinelnode.Red-blacktrees,likeallbinarysearchtrees,allowefficientin-ordertraversalinthefashion,Left-Root-Right,oftheirelements.Thesearch-t
6、imeresultsfromthetraversalfromroottoleaf,andthereforeabalancedtree,havingtheleastpossibletreeheight,resultsinO(logn)searchtime.PropertiesAnexampleofared-blacktreeAred-blacktreeisabinarysearchtreewhereeachnodehasacolorattribute,thevalueofwhichiseitherredorblack.Inadditiontotheordi
7、naryrequirementsimposedonbinarysearchtrees,thefollowingadditionalrequirementsapplytored-blacktrees:1.Anodeiseitherredorblack.2.Therootisblack.(Thisruleisusedinsomedefinitionsandnotothers.Sincetherootcanalwaysbechangedfromredtoblackbutnotnecessarilyvice-versathisrulehaslittleeffec
8、tonanalysis.)3.Allleavesareblack.4.Bothc
