資源描述：
《關(guān)于紅黑樹(Red-Black Tree)英文簡介》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
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
