java语言程序设计解答例题复习题答案.pdf

Chapter47RedBlackTrees

1.

Ared-blacktreeisabinarysearchtree,whichisderivedfroma

2-4tree.Ared-blacktreecorrespondstoa2-4tree.Eachnode

inared-blacktreehasacolorattributeredorblack.Anodeis

calledexternalifitsleftorrightsubtreeisempty.Notethat

aleafnodeiternal,butanexternalnodeisnotnecessarily

aleafnode.blackdepthofanodeisdefinedasthenumber

ofblacknodesinapathfromthenodetotheroot.

2

Ared-blacktreehasthefollowingproperties:

1.Therootisblack.

2.Twoadjacentnodescannotbebothred.

3.Allexternalnodeshavethesameblackdepth.

3.Toconvertared-blacktreetoa2-4tree,simplymergeanyrednodeswithits

parenttocreatea3-nodeora4-node.Theresultingtreeisunique.

4.Toconverta2-4treetoared-blacktree,performthefollowingtransformations

foreachnode:

1.Ifisa2-node,coloritblack.

2.Ifisa3-nodewithelementvaluesand,thereare

twowaystoconvertit.Oneistomaketheparentof

andtheotheristomaketheparentof.Inanycase,

colortheparentblackandthechildred.

3.Ifisa4-nodewithelementvalues,,and,make

theparentofand.Colorblackandandred.

Theconversionfroma2-4treetoaredblacktreeisnotunique.

5.RBTreeNodeEextendsTreeNodeE.ThedatafieldsinTreeNodeEare

element,left,andright.TheadditionaldatafieldinRBTreeNodeEisredofthe

booleantype.

6.

Anewelementisalwaysinsertedasaleafnode.Ifthenewnode

istheroot,coloritblack.Otherwise,coloritred.Ifthe

parentofthenewnodeisred,itviolates