欢迎来到天天文库
浏览记录
ID:33927374
大小:251.95 KB
页数:29页
时间:2019-02-28
《麻省理工大学算法导论lecture10》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture10Prof.ErikDemaineBalancedsearchtreesBalancedsearchtree:Asearch-treedatastructureforwhichaheightofO(lgn)isguaranteedwhenimplementingadynamicsetofnitems.•AVLtrees•2-3treesExamples:•2-3-4trees•B-trees•Red-blacktrees
2、©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.2Red-blacktreesThisdatastructurerequiresanextraone-bitcolorfieldineachnode.Red-blackproperties:1.Everynodeiseitherredorblack.2.Therootandleaves(NIL’s)areblack.3.Ifanodeisred,thenitsparentisblack.4.Allsimplepa
3、thsfromanynodextoadescendantleafhavethesamenumberofblacknodes=black-height(x).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.3Exampleofared-blacktree77331818NILNILh=410102222NIL8811112626NILNILNILNILNILNIL©2001byCharlesE.LeisersonIntroductiontoAlgorithmsD
4、ay18L10.4Exampleofared-blacktree77331818NILNIL10102222NIL8811112626NILNILNILNILNILNIL1.Everynodeiseitherredorblack.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.5Exampleofared-blacktree77331818NILNIL10102222NIL8811112626NILNILNILNILNILNIL2.Therootandleav
5、es(NIL’s)areblack.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.6Exampleofared-blacktree77331818NILNIL10102222NIL8811112626NILNILNILNILNILNIL3.Ifanodeisred,thenitsparentisblack.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.7Exampleofared-blac
6、ktree77bh=2331818bh=2NILNILbh=110102222NILbh=18811112626bh=0NILNILNILNILNILNIL4.Allsimplepathsfromanynodextoadescendantleafhavethesamenumberofblacknodes=black-height(x).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.8Heightofared-blacktreeTheorem.Ared-bla
7、cktreewithnkeyshasheighth≤2lg(n+1).Proof.(Thebookusesinduction.Readcarefully.)INTUITION:•Mergerednodesintotheirblackparents.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.9Heightofared-blacktreeTheorem.Ared-blacktreewithnkeyshasheighth≤2lg(n+1).Proof.(The
8、bookusesinduction.Readcarefully.)INTUITION:•Mergerednodesintotheirblackparents.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay18L10.1
此文档下载收益归作者所有