数据结构——查找树

.,Chapter8searchtrees,BinarysearchtreesandAVLtrees8-1BinarysearchtreesProblem:Storeordereddatainanarraystructure:efficientsearchalgorithm,inefficientinsertionanddeletionLinkedlist:efficientinsertionanddeletion,inefficientsearchBinarysearchtreescansatisfybothofthemDefinition:thepropertiesofabinarysearchtreeAllitemsintheleftsubtreearelessthantherootAllitemsintherightsubtreearegreaterthanorequaltotherootEachsubtreeisitselfabinarysearchtree.,.,Operationsonbinarysearchtrees,binarysearchtreetraversalsAlgorithmsareidenticaltotheonesinchapter7,binarysearchtreesearchalgorithmsFindsmallestnodeFindlargestnodeFindrequestednode,FollowtheleftbranchesuntilwegettoaleafAlgorithmfindsmallestBST(valroot)TofindthesmallestnodeinaBSTPrerootisapointertoanonemptyBSTorsubtreeReturnaddressofsmallestnode1if(root-leftnull)1return(root)2endif3returnfindsmallestBST(root-left)endfindsmallestBST,FollowtherightbranchestothelastnodeinthetreeAlgorithmfindlargestBST(valroot)TofindthelargestnodeinaBSTPrerootisapointertoanonemptyBSTorsubtreeReturnaddressoflargestnode1if(root-rightnull)1return(root)2endif3returnfindlargestBST(root-right)endfindlargestBST,Assume:TofindT,ComparingTwithroot,TrootgorightAlgorithmsearchBST(valroot,valargument)SearchabinarysearchtreeforagivenvaluePrerootistheroottoabinarytreeorsubtreeargumentisthekeyvaluerequestedReturnthenodeaddressifthevalueisfoundNullifthenodeisnotinthetree1if(rootisnull)1returnnull2endif3if(argumentkey)1returnsearchBST(root-left,argument)4elseif(argumentroot-key)1returnsearchBST(root-right,argument)5else1returnroot6endifendsearchBST,.,Insertnode,Steps:1.Followthebranchestoanemptysubtree2.InsertthenewnodeAllinsertstakeplaceataleaforaleaflikenodethathasonlyonenullbranch,Note:nodewithequalvaluesarefoundintherightsubtree,.,Iterativeinsert(algorithm),1if(rootisnull)1root=new2else1pwalk=root2loop(pwalknotnull)1parent=pwalk2if(new-keykey)1pwalk=pwalk-left3else1pwalk=pwalk-right4endif3endloopLocationfornewnodefound4if(new-keykey)1parent-left=new5else1parent-right=new6endif3endif4returnendinsertBST,AlgorithminsertBST(refroot,valnew)InsertnodecontainingnewdataintoBSTusingiterationPrerootisaddressoffirstnodeinaBSTnewisaddressofnodecontainingdatatobeinsertedPostnewnodeinsertedintothetree,Algorithm8-4iterativebinarysearchtreeinsert,.,Recursiveinsertnode(algorithm),AlgorithmaddBST(refroot,valnew)InsertnodecontainingnewdataintoBSTusingrecursionPrerootisaddressofcurrentnodeinaBSTnewisaddressofnodecontainingdatatobeinsertedPostnewnodeinsertedintothetree1if(rootisnull)1root=new2elselocatenullsubtreeforinsertion1if(new-keykey)1addBST(root-left,new)2else1addBST(root-right,new)3endif3endif4returnendinsertBSTalgorithm8-5addnodetoBSTrecursively,.,Deletenode,1.locateit2.delete:thereare4possiblecasesThenodehasnochildren:setthedeletenodesparenttonull,recycleitsmemory,andreturnHasonlyarightsubtree:attachtherightsubtreetothedeletenodesparentandrecycleitsmemory.Hasonlyaleftsubtree:attachtheleftsubtreetothedeletenodesparentandrecycleitsmemory.Hastwosubtree:todeleteanodefromthemiddleofatree,tokeepthebalance,wemustfindanode,twoways:Findthelargestnodeinthedeletednodesleftsubtree,moveitsdatatoreplacethedeletednodesdataFindthesmallestnodeinthedeletednodesrightsubtree,moveitsdatatoreplacethedeletednodesdataRegardlessofwhichlogicweuse,wewillbemovingdatafromaleaforleaflikenodethatcanbedeleted.,.,.,1if(rootisnull)1returnfalse2endif3if(dltkeydata.key)1returndeleteBST(root-left,dltkey)4elseif(dltkeyroot-data.key)1returndeleteBST(root-right,dltkey)5else/deletenodefoundtestforleafnode1if(root-leftnull)1dltptr=root2root=root-right3recycle(dltptr)4returntrue2elseif(root-rightnull)1dltptr=root2root=root-left3recycle(dltptr)4returntrue3else/nodetobedeletednotaleaf(orleaflike),findlargestnodeonleftsubtree1dltptr=root-left2loop(dltptr-rightnotnull)1dltptr=dltptr-right/nodefound,movedataanddeleteleafnode3root-data=dltptr-data4returndeleteBST(root-left,dltptr-data.key)4endif6endifenddeleteBST,AlgorithmdeleteBST(refroot,valdltKey)DeleteanodefromaBSTPrerootispointe