lecture 10 red-black trees, rotations, insertions, deletions

《lecture 10 red-black trees, rotations, insertions, deletions》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY).Licens

2、e:CreativeCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall20

3、05Transcript–Lecture10Goodmorning.Itlookslike9:30isgettingearlierandearlierforeveryone.Hellotoallthepeoplewatchingathome.Ithinkthereshouldbearequirementthatifyou'rewatchingthevideo,youcanonlywatchit9:30-11:00onSunday,oratleaststartwatchingthenjustsoyoucanallfeelourmornings.Today,

4、we'regoingtotalkaboutbalancedsearchtrees.Now,we'vehintedatthisforawhile.Ourgoaltodayistogetasearchtreedatastructure,sowecaninsert,delete,andsearchallatlogntimeforoperations.So,wewantatreethat'sguaranteedtobelogninheight.So,that'sabalancedsearchtreedatastructure.And,wewantadatastr

5、ucturethatcanmaintainadynamicsetofnelementsinlogntimeforoperation.So,we'llsay,usingatreeofheightorderlogn.Now,ifyoulookveryclosely,wehaven'tactuallydefinedwhatasearchtreedatastructureis.We'vedefinedwhatabinarysearchtreedatastructureis,andthat'soneparticularkind.Andthat'swhatwewil

6、lbefocusingontoday.InrecitationonFriday,wewilllookat,oryouwilllikethat,balancedsearchtreesthatarenotnecessarilybinary.Eachnodecanhaveaconstantnumberofchildren,notjusttwo.So,I'mdefiningisgenerally.Youactuallyseewhatasearchtreeisinthegeneralcaselateron.Today,wewilljustbefocusingont

7、hebinarycase.So,Iwon'tdefinethisyet.So,therearealotofdifferentbalancedsearchtreedatastructures.So,thesearethemainonesthatIknowof.ThefirstonewasAVLtrees.Thiswasinventedin1962.So,thatwasthebeginningoffastdatastructures.Thenextthreesortofcometogetherandthisiswhatyouwillcoverinrecita

8、tionthisweek.So,thesearenonbinarytrees.I