aps审核-第二部分英审德审绕道算法设计与分析

IntroductiontoAlgorithms刘东林

华东理工大学信息学院计算机系Lecture05StructuresBinarySearchTreesReview:DynamicSetsfocusondatastructuresratherthanstraightalgorithmsInparticular,structuresfordynamicsetsElementshaveakeyandsatellitedataDynamicsetssupportqueriessuchas:Search(S,k),Minimum(S),Maximum(S),Successor(S,x),Predecessor(S,x)Theymayalsosupportmodifyingoperationslike:Insert(S,x),Delete(S,x)Review:BinarySearchTreesBinarySearchTrees(BSTs)areanimportantdatastructurefordynamicsetsInadditiontosatellitedata,elementshave:key:anidentifyingfieldinducingatotalorderingleft:pointertoaleftchild(maybeNULL)right:pointertoarightchild(maybeNULL)p:pointertoaparentnode(NULLforroot)Review:BinarySearchTreesBSTproperty:

key[leftSubtree(x)]key[x]key[rightSubtree(x)]Example:FBHKDAInorderTreeWalkWhatdoesthefollowingcodedo?TreeWalk(x)TreeWalk(left[x]);print(x);TreeWalk(right[x]);A:printselementsinsorted(increasing)orderThisiscalledaninordertreewalkPreordertreewalk:printroot,thenleft,thenrightPostordertreewalk:printleft,thenright,thenrootInorderTreeWalkExample:Howlongwillatreewalktake?ProvethatinorderwalkprintsinmonotonicallyincreasingorderFBHKDAOperationsonBSTs:SearchGivenakeyandapointertoanode,returnsanelementwiththatkeyorNULL:TreeSearch(x,k)if(x=NULLork=key[x])returnx;if(k<key[x])returnTreeSearch(left[x],k);elsereturnTreeSearch(right[x],k);BSTSearch:ExampleSearchforDandC:FBHKDAOperationsonBSTs:SearchHere’sanotherfunctionthatdoesthesame:TreeSearch(x,k)while(x!=NULLandk!=key[x])if(k<key[x])x=left[x];elsex=right[x];returnx;Whichofthesetwofunctionsismoreefficient?OperationsofBSTs:InsertAddsanelementxtothetreesothatthebinarysearchtreepropertycontinuestoholdThebasicalgorithmLikethesearchprocedureaboveInsertxinplaceofNULLUsea“trailingpointer”tokeeptrackofwhereyoucamefrom(likeinsertingintosinglylinkedlist)BSTInsert:ExampleExample:InsertCFBHKDACBSTSearch/Insert:RunningTimeWhatistherunningtimeofTreeSearch()orTreeInsert()?A:O(h),whereh=heightoftreeWhatistheheightofabinarysearchtree?A:worstcase:h=O(n)whentreeisjustalinearstringofleftorrightchildrenWe’llkeepallanalysisintermsofhfornowLaterwe’llseehowtomaintainh=O(lgn)SortingWithBinarySearchTreesInformalcodeforsortingarrayAoflengthn:BSTSort(A)fori=1tonTreeInsert(A[i]);InorderTreeWalk(root);Arguethatthisis(nlgn)WhatwillbetherunningtimeintheWorstcase?Averagecase?(hint:remindyouofanything?)SortingWithBSTsAveragecaseanalysisIt’saformofquicksort!fori=1tonTreeInsert(A[i]);InorderTreeWalk(root);31826755712867526753182657SortingwithBSTsSamepartitionsaredoneaswithquicksort,butinadifferentorderInpreviousexampleEverythingwascomparedto3onceThenthoseitems<3werecomparedto1onceEtc.Samecomparisonsasquicksort,differentorder!Example:considerinserting5SortingwithBSTsSinceruntimeisproportionaltothenumberofcomparisons,sametimeasquicksort:O(nlgn)Whichdoyouthinkisbetter,quicksortorBSTsort?Why?SortingwithBSTsSinceruntimeisproportionaltothenumberofcomparisons,sametimeasquicksort:O(nlgn)Whichdoyouthinkisbetter,quicksortorBSTSort?Why?A:quicksortBetterconstantsSortsinplaceDoesn’tneedtobuilddatastructureMoreBSTOperationsBSTsaregoodformorethansorting.Forexample,canimplementapriorityqueueWhatoperationsmustapriorityqueuehave?InsertMinimumExtract-MinBSTOperations:MinimumHowcanweimplementaMinimum()query?Whatistherunningtime?BSTOperations:SuccessorFordeletion,wewillneedaSuccessor()operationDrawFig13.2Whatisthesuccessorofnode3?Node15?Node13?Whatarethegeneralrulesforfindingthesuccessorofnodex?(hint:twocases)BSTOperations:SuccessorTwocases:xhasarightsubtree:successorisminimumnodeinrightsubtreexhasnorightsubtree:successorisfirstancestorofxwhoseleftchildisalsoancestorofxIntuition:Aslongasyoumovetotheleftupthetree,you’revisitingsmallernodes.Predecessor:similaralgorithmBSTOperations:DeleteDeletionisabittricky3cases:xhasnochildren:Removexxhasonechild:Spliceoutxxhastwochildren:SwapxwithsuccessorPerformcase1or2todeleteitFBHKDACExample:deleteK

orHorBBSTOperations:DeleteWhywillcase2alwaysgotocase0orcase1?A:becausewhenxhas2children,itssuccessoristheminimuminitsrightsubtreeCouldweswapxwithpredecessorinsteadofsuccessor?A:yes.Woulditbeagoodidea?A:mightbegoodtoalternateTheEndUpnext:guaranteeingaO(lgn)heighttreeRed-BlackTreesRed-BlackTreesRed-blacktrees:BinarysearchtreesaugmentedwithnodecolorOperationsdesignedtoguaranteethattheheight

h=O(lgn)Wedescribedthepropertiesofred-blacktreesWeprovedthattheseguaranteeh=O(lgn)Next:describeoperationsonred-blacktreesRed-BlackPropertiesThered-blackproperties:1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblackNote:thismeansevery“real”nodehas2children3. Ifanodeisred,bothchildrenareblackNote:can’thave2consecutiveredsonapath4. Everypathfromnodetodescendentleafcontainsthesamenumberofblacknodes5. TherootisalwaysblackBlack-Heightblack-height:#blacknodesonpathtoleafWhatistheminimumblack-heightofanodewithheighth?A:aheight-hnodehasblack-heighth/2Theorem:Ared-blacktreewithninternalnodeshasheighth2lg(n+1)Provedby(whatelse?)inductionProvingHeightBoundThusattherootofthered-blacktree:n 2bh(root)-1 n 2h/2-1 lg(n+1)h/2 h2lg(n+1) Thush=O(lgn) RBTrees:Worst-CaseTimeSowe’veprovedthatared-blacktreehasO(lgn)heightCorollary:TheseoperationstakeO(lgn)time:Minimum(),Maximum()Successor(),Predecessor()Search()Insert()andDelete():WillalsotakeO(lgn)timeButwillneedspecialcaresincetheymodifytreeRed-BlackTrees:AnExampleColorthistree:7591212597Red-blackproperties:1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. TherootisalwaysblackInsert8Wheredoesitgo?Red-BlackTrees:

TheProblemWithInsertion125971. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. TherootisalwaysblackInsert8Wheredoesitgo?Whatcolor

shoulditbe?Red-BlackTrees:

TheProblemWithInsertion1259781. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. TherootisalwaysblackInsert8Wheredoesitgo?Whatcolor

shoulditbe?Red-BlackTrees:

TheProblemWithInsertion1259781. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. TherootisalwaysblackRed-BlackTrees:

TheProblemWithInsertionInsert11Wheredoesitgo?1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack125978Red-BlackTrees:

TheProblemWithInsertionInsert11Wheredoesitgo?Whatcolor?1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack12597811Red-BlackTrees:

TheProblemWithInsertionInsert11Wheredoesitgo?Whatcolor?Can’tbered!(#3)1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack12597811Red-BlackTrees:

TheProblemWithInsertionInsert11Wheredoesitgo?Whatcolor?Can’tbered!(#3)Can’tbeblack!(#4)1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack12597811Red-BlackTrees:

TheProblemWithInsertionInsert11Wheredoesitgo?Whatcolor?Solution:

recolorthetree1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack12597811Red-BlackTrees:

TheProblemWithInsertionInsert10Wheredoesitgo?1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack12597811Red-BlackTrees:

TheProblemWithInsertionInsert10Wheredoesitgo?Whatcolor?1. Everynodeiseitherredorblack2. Everyleaf(NULLpointer)isblack3. Ifanodeisred,bothchildrenareblack4. Everypathfromnodetodescendentleaf

containsthesamenumberofblacknodes5. Therootisalwaysblack1259781110Red-BlackTrees:

TheProblemWithInsertionInsert10Wheredoesitgo?Whatcolor?A:nocolor!Tree

istooimbalancedMustchangetreestructure

toallowrecoloringGoal:restructuretreein

O(lgn)time1259781110RBTrees:RotationOurbasicoperationforchangingtreestructureiscalledrotation:Doesrotationpreserveinorderkeyordering?WhatwouldthecodeforrightRotate()actuallydo?yxCABxAyBCrightRotate(y)leftRotate(x)rightRotate(y)RBTrees:RotationAnswer:Alotofpointermanipulationxkeepsitsleftchildykeepsitsrightchildx’srightchildesy’sleftchildx’sandy’sparentschangeWhatistherunningtime?yxCABxAyBCRotationExampleRotateleftabout9:12597811RotationExampleRotateleftabout9:51279118Red-BlackTrees:InsertionInsertion:thebasicideaInsertxintotree,colorxredOnlyr-bproperty3mightbeviolated(ifp[x]red)Ifso,moveviolationuptreeuntilaplaceisfoundwhereitcanbefixedTotaltimewillbeO(lgn)rbInsert(x)treeInsert(x);x->color=RED;//Moveviolationof#3uptree,maintaining#4asinvariant:while(x!=root&&x->p->color==RED)if(x->p==x->p->p->left)y=x->p->p->right;if(y->color==RED)x->p->color=BLACK;y->color=BLACK;x->p->p->color=RED;x=x->p->p;else//y->color==BLACKif(x==x->p->right)x=x->p;leftRotate(x);x->p->color=BLACK;x->p->p->color=RED;rightRotate(x->p->p);else//x->p==x->p->p->right(sameasabove,butwith“right”&“left”exchanged)Case1Case2Case3rbInsert(x)treeInsert(x);x->color=RED;//Moveviolationof#3uptree,maintaining#4asinvariant:while(x!=root&&x->p->color==RED)if(x->p==x->p->p->left)y=x->p->p->right;if(y->color==RED)x->p->color=BLACK;y->color=BLACK;x->p->p->color=RED;x=x->p->p;else//y->color==BLACKif(x==x->p->right)x=x->p;leftRotate(x);x->p->color=BLACK;x->p->p->color=RED;rightRotate(x->p->p);else//x->p==x->p->p->right(sameasabove,butwith“right”&“left”exchanged)Case1:uncleisREDCase2Case3RBInsert:Case1if(y->color==RED)x->p->color=BLACK;y->color=BLACK;x->p->p->color=RED;x=x->p->p;Case1:“uncle”isredInfiguresbelow,all’sareequal-black-heightsubtreesCADBCADBxynewxChangecolorsofsomenodes,preserving#4:alldownwardpathshaveequalb.h.Thewhileloopnowco