




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
IntroductiontoAlgorithms劉東林
華東理工大學(xué)信息學(xué)院計(jì)算機(jī)系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”&“l(fā)eft”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”&“l(fā)eft”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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 環(huán)境保護(hù)與綠色發(fā)展對(duì)縣域經(jīng)濟(jì)空間格局的挑戰(zhàn)與機(jī)遇
- 高附加值產(chǎn)品創(chuàng)新對(duì)羊絨產(chǎn)業(yè)鏈升級(jí)的驅(qū)動(dòng)
- 從教育政策看辦公行業(yè)的未來趨勢(shì)
- 大學(xué)生創(chuàng)業(yè)創(chuàng)新教育與跨境電商企業(yè)合作模式探討
- 江蘇省南京市建鄴三校聯(lián)合2024年化學(xué)九上期末統(tǒng)考模擬試題含解析
- 云南省曲靖市2025屆八年級(jí)物理第一學(xué)期期末考試試題含解析
- 山東省張店區(qū)七校聯(lián)考2025屆化學(xué)九上期末調(diào)研試題含解析
- 2025至2030沉香木行業(yè)運(yùn)營(yíng)態(tài)勢(shì)與投資前景調(diào)查研究報(bào)告
- 2025至2030中國(guó)自動(dòng)報(bào)警系統(tǒng)(AWS)行業(yè)市場(chǎng)占有率及投資前景評(píng)估規(guī)劃報(bào)告
- 2025至2030中國(guó)自動(dòng)升降機(jī)行業(yè)發(fā)展分析及前景趨勢(shì)與發(fā)展趨勢(shì)分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- JJG 693-2011可燃?xì)怏w檢測(cè)報(bào)警器
- (完整版)第七章發(fā)酵食品加工技術(shù)
- 糞便無害化處理廠建設(shè)方案
- 恢復(fù)執(zhí)行申請(qǐng)書
- 智慧的光芒普照每位學(xué)生 論文
- 銷售行業(yè)跑業(yè)務(wù)計(jì)劃書
- 政府采購詢價(jià)采購函報(bào)價(jià)單格式及論大學(xué)生寫作能力
- 建筑物拆除工程監(jiān)理實(shí)施細(xì)則
- LY/T 3256-2021全國(guó)優(yōu)勢(shì)喬木樹種(組)基本木材密度測(cè)定
- GB/T 25760-2010滾動(dòng)軸承滾針和推力球組合軸承外形尺寸
- 特勞特-定位課件
評(píng)論
0/150
提交評(píng)論