第03章查找樹SearchTrees資料講解

SearchTrees692418<>=1SearchTreesOrderedDictionariesKeysareassumedtocomefromatotalorder.Newoperations:closestKeyBefore(k)closestElemBefore(k)closestKeyAfter(k)closestElemAfter(k)2SearchTreesBinarySearch(§3.1.1)BinarysearchperformsoperationfindElement(k)onadictionaryimplementedbymeansofanarray-basedsequence,sortedbykeyateachstep,thenumberofcandidateitemsishalvedterminatesafterO(logn)stepsExample:findElement(7)134578911141618191345789111416181913457891114161819134578911141618190000mlhmlhmlhl=m=h3SearchTreesLookupTable(§3.1.1)AlookuptableisadictionaryimplementedbymeansofasortedsequenceWestoretheitemsofthedictionaryinanarray-basedsequence,sortedbykeyWeuseanexternalcomparatorforthekeysPerformance:findElementtakesO(logn)time,usingbinarysearchinsertItemtakesO(n)timesinceintheworstcasewehavetoshiftn/2itemstomakeroomforthenewitemremoveElementtakeO(n)timesinceintheworstcasewehavetoshiftn/2itemstocompacttheitemsaftertheremovalThelookuptableiseffectiveonlyfordictionariesofsmallsizeorfordictionariesonwhichsearchesarethemostcommonoperations,whileinsertionsandremovalsarerarelyperformed(e.g.,creditcardauthorizations)4SearchTreesSearch(§3.1.3)Tosearchforakeyk,wetraceadownwardpathstartingattherootThenextnodevisiteddependsontheoutcomeofthecomparisonofkwiththekeyofthecurrentnodeIfwereachaleaf,thekeyisnotfoundandwereturnNO_SUCH_KEYExample:findElement(4)Algorithm

findElement(k,v)

if

T.isExternal(v) return

NO_SUCH_KEYifk

<

key(v)

return

findElement(k,T.leftChild(v))elseifk

=

key(v)

return

element(v)else

{k

>

key(v)}

return

findElement(k,T.rightChild(v))692418<>=6SearchTreesInsertion(§3.1.4)ToperformoperationinsertItem(k,o),wesearchforkeykAssumekisnotalreadyinthetree,andletletwbetheleafreachedbythesearchWeinsertkatnodewandexpandwintoaninternalnodeExample:insert56924186924185<>>ww7SearchTreesDeletion(§3.1.5)ToperformoperationremoveElement(k),wesearchforkeykAssumekeykisinthetree,andletletvbethenodestoringkIfnodevhasaleafchildw,weremovevandwfromthetreewithoperationremoveAboveExternal(w)Example:remove46924185vw692518<>8SearchTreesDeletion(cont.)Weconsiderthecasewherethekeyktoberemovedisstoredatanodevwhosechildrenarebothinternalwefindtheinternalnodewthatfollowsvinaninordertraversalwecopykey(w)intonodevweremovenodewanditsleftchildz(whichmustbealeaf)bymeansofoperationremoveAboveExternal(z)Example:remove3318695vwz251869v29SearchTreesPerformance(§3.1.6)ConsideradictionarywithnitemsimplementedbymeansofabinarysearchtreeofheighththespaceusedisO(n)methodsfindElement,insertItemandremoveElementtakeO(h)timeTheheighthisO(n)intheworstcaseandO(logn)inthebestcase10SearchTreesAVLTrees6384vz11SearchTreesAVLTreeDefinitionAVLtreesarebalanced.AnAVLTreeisabinarysearchtreesuchthatforeveryinternalnodevofT,theheightsofthechildrenofvcandifferbyatmost1.AnexampleofanAVLtreewheretheheightsareshownnexttothenodes:12SearchTreesHeightofanAVLTreeFact:TheheightofanAVLtreestoringnkeysisO(logn).Proof:Letusboundn(h):theminimumnumberofinternalnodesofanAVLtreeofheighth.Weeasilyseethatn(1)=1andn(2)=2Forn>2,anAVLtreeofheighthcontainstherootnode,oneAVLsubtreeofheightn-1andanotherofheightn-2.Thatis,n(h)=1+n(h-1)+n(h-2)Knowingn(h-1)>n(h-2),wegetn(h)>2n(h-2).Son(h)>2n(h-2),n(h)>4n(h-4),n(h)>8n(n-6),…(byinduction),n(h)>2in(h-2i).Nowleti=(floorofh/2)-1Thenweget:n(h)>2h/2-1Takinglogarithms:h<2logn(h)+2ThustheheightofanAVLtreeisO(logn)34n(1)n(2)13SearchTreesInsertioninanAVLTreeInsertionisasinabinarysearchtreeAlwaysdonebyexpandinganexternalnode.Example:441778325088486254wb=xa=yc=z4417783250884862beforeinsertionafterinsertion14SearchTreesTrinodeRestructuringlet(a,b,c)beaninorderlistingofx,y,zperformtherotationsneededtomakebthetopmostnodeofthethreeb=ya=zc=xT0T1T2T3b=ya=zc=xT0T1T2T3c=yb=xa=zT0T1T2T3b=xc=ya=zT0T1T2T3case1:singlerotation(aleftrotationabouta)case2:doublerotation(arightrotationaboutc,thenaleftrotationabouta)(othertwocasesaresymmetrical)15SearchTreesInsertionExample,continued884417783250486224112231541T0T1T2T3xyzunbalanced......balancedT116SearchTreesRestructuring (asSingleRotations)SingleRotations:17SearchTreesRestructuring (asDoubleRotations)doublerotations:18SearchTreesRemovalinanAVLTreeRemovalbeginsasinabinarysearchtree,whichmeansthenoderemovedwillbecomeanemptyexternalnode.Itsparent,w,maycauseanimbalance.Example:4417783250884862544417785088486254beforedeletionof32afterdeletion19SearchTreesRebalancingafteraRemovalLetzbethefirstunbalancednodeencounteredwhiletravellingupthetreefromw.Also,letybethechildofzwiththelargerheight,andletxbethechildofywiththelargerheight.Weperformrestructure(x)torestorebalanceatz.Asthisrestructuringmayupsetthebalanceofanothernodehigherinthetree,wemustcontinuecheckingforbalanceuntiltherootofTisreached4417785088486254wc=xb=ya=z441778508848625420SearchTreesRunningTimesforAVLTreesasinglerestructureisO(1)usingalinked-structurebinarytreefindisO(logn)heightoftreeisO(logn),norestructuresneededinsertisO(logn)initialfindisO(logn)Restructuringupthetree,maintainingheightsisO(logn)removeisO(logn)initialfindisO(logn)Restructuringupthetree,maintainingheightsisO(logn)21SearchTreesBouned-DepthSearchTrees9101425722SearchTreesOutlineandReadingBounded-DepthSearchTreesMulti-waysearchtree(§3.3.1)DefinitionSearch(2,4)tree(§3.3.2)DefinitionSearchInsertionDeletion23SearchTreesMulti-WaySearchTreeAmulti-waysearchtreeisanorderedtreesuchthatEachinternalnodehasatleasttwochildrenandstoresd

-1key-elementitems(ki,oi),wheredisthenumberofchildrenForanodewithchildrenv1v2…vd

storingkeysk1k2…kd-1keysinthesubtreeofv1arelessthank1keysinthesubtreeofviarebetweenki-1andki

(i=2,…,d-1)keysinthesubtreeofvd

aregreaterthankd-1Theleavesstorenoitemsandserveasplaceholders11242681530273224SearchTreesMulti-WayInorderTraversalWecanextendthenotionofinordertraversalfrombinarytreestomulti-waysearchtreesNamely,wevisititem(ki,oi)ofnodevbetweentherecursivetraversalsofthesubtreesofvrootedatchildrenviandvi

+

1Aninordertraversalofamulti-waysearchtreevisitsthekeysinincreasingorder1124268153027321357911131915172461418812101625SearchTreesMulti-WaySearchingSimilartosearchinabinarysearchtreeAeachinternalnodewithchildrenv1v2…vdandkeysk1k2…kd-1k

=

ki(i=1,…,d-1):thesearchterminatessuccessfullyk

<

k1:wecontinuethesearchinchildv1ki-1<

k

<

ki(i=2,…,d-1):wecontinuethesearchinchildvik

>kd-1:wecontinuethesearchinchildvdReachinganexternalnodeterminatesthesearchunsuccessfullyExample:searchfor3011242681530273226SearchTrees(2,4)TreeA(2,4)tree(alsocalled2-4treeor2-3-4tree)isamulti-waysearchwiththefollowingpropertiesNode-SizeProperty:everyinternalnodehasatmostfourchildrenDepthProperty:alltheexternalnodeshavethesamedepthDependingonthenumberofchildren,aninternalnodeofa(2,4)treeiscalleda2-node,3-nodeor4-node101524281227321827SearchTreesHeightofa(2,4)TreeTheorem:A(2,4)treestoringn

itemshasheightO(logn) Proof:Lethbetheheightofa(2,4)treewithnitemsSincethereareatleast2iitemsatdepthi

=

0,…,h-1andnoitemsatdepthh,wehave

n

1+2+4+…+2h-1=

2h-1Thus,h

log(n+1)Searchingina(2,4)treewithnitemstakesO(logn)time122h-10items01h-1hdepth28SearchTreesInsertionWeinsertanewitem(k,o)attheparentvoftheleafreachedbysearchingforkWepreservethedepthpropertybutWemaycauseanoverflow(i.e.,nodevmaybecomea5-node)Example:insertingkey30causesanoverflow27323510152428121810152428122730323518vv29SearchTreesOverflowandSplitWehandleanoverflowata5-nodevwithasplitoperation:letv1…v5bethechildrenofvandk1…k4bethekeysofvnodevisreplacednodesv'andv"v'isa3-nodewithkeysk1

k2andchildrenv1

v2

v3v"isa2-nodewithkeyk4

andchildrenv4

v5keyk3isinsertedintotheparentuofv(anewrootmaybecreated)Theoverflowmaypropagatetotheparentnodeu1524122730323518vuv1v2v3v4v515243212273018v'uv1v2v3v4v535v"30SearchTreesAnalysisofInsertionAlgorithm

insertItem(k,o)

1. Wesearchforkeyktolocatetheinsertionnodev

2. Weaddthenewitem(k,o)atnodev

3.while

overflow(v)ifisRoot(v) createanewemptyrootabovevv

split(v)LetTbea(2,4)treewithnitemsTreeThasO(logn)height

Step1takesO(logn)timebecausewevisitO(logn)nodesStep2takesO(1)timeStep3takesO(logn)timebecauseeachsplittakesO(1)timeandweperformO(logn)splitsThus,aninsertionina(2,4)treetakesO(logn)time31SearchTreesDeletionWereducedeletionofanitemtothecasewheretheitemisatthenodewithleafchildrenOtherwise,wereplacetheitemwithitsinordersuccessor(or,equivalently,withitsinorderpredecessor)anddeletethelatteritemExample:todeletekey24,wereplaceitwith27(inordersuccessor)273235101524281218323510152728121832SearchTreesUnderflowandFusionDeletinganitemfromanodevmay