麻省理工大学算法导论lecture10

《麻省理工大学算法导论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