182
Chapter4 Trees
Searchtreesareofgreatimportanceinalgorithmdesign.Theysupportalmostallthe
usefuloperations,andthelogarithmicaveragecostisverysmall.Nonrecursiveimplemen-
tationsofsearchtreesaresomewhatfaster,buttherecursiveversionsaresleeker,more
elegant,andeasiertounderstandanddebug.Theproblemwithsearchtreesisthattheir
performancedependsheavilyontheinputbeingrandom.Ifthisisnotthecase,therun-
ningtimeincreasessignificantly,tothepointwheresearchtreesbecomeexpensivelinked
lists.
Wesawseveralwaystodealwiththisproblem.AVLtreesworkbyinsistingthatall
nodes’leftandrightsubtreesdifferinheightsbyatmostone.Thisensuresthatthetree
cannotgettoodeep.Theoperationsthatdonotchangethetree,asinsertiondoes,can
allusethestandardbinarysearchtreecode.Operationsthatchangethetreemustrestore
thetree.Thiscanbesomewhatcomplicated,especiallyinthecaseofdeletion.Weshowed
howtorestorethetreeafterinsertionsinO(logN)time.
Wealsoexaminedthesplaytree.Nodesinsplaytreescangetarbitrarilydeep,butafter
everyaccessthetreeisadjustedinasomewhatmysteriousmanner.Theneteffectisthat
anysequenceofMoperationstakesO(MlogN)time,whichisthesameasabalancedtree
wouldtake.
B-trees arebalancedM-way (asopposedto2-wayorbinary)trees,whicharewell
suitedfordisks;aspecialcaseisthe2–3tree(M=3),whichisanotherwaytoimplement
balancedsearchtrees.
Inpractice,therunning timeofallthebalanced-treeschemes,whileslightly faster
forsearching,isworse(byaconstantfactor)forinsertionsanddeletionsthanthesimple
binarysearchtree,butthisisgenerallyacceptableinviewoftheprotectionbeinggiven
againsteasilyobtainedworst-caseinput.Chapter12discussessomeadditionalsearchtree
datastructuresandprovidesdetailedimplementations.
Afinalnote:Byinsertingelementsintoasearchtreeandthenperforminganinorder
traversal,weobtaintheelementsinsortedorder.ThisgivesanO(NlogN)algorithmto
sort,whichisaworst-caseboundifanysophisticatedsearchtreeisused.Weshallsee
betterwaysinChapter 7,butnonethathavealowertimebound.
Exercises
4.1
ForthetreeinFigure4.74:
a. Whichnodeistheroot?
b.Whichnodesareleaves?
4.2
ForeachnodeinthetreeofFigure4.74:
a. Nametheparentnode.
b.Listthechildren.
c. Listthesiblings.
d.Computethedepth.
e. Computetheheight.
4.3
WhatisthedepthofthetreeinFigure4.74?
4.4
ShowthatinabinarytreeofNnodes,thereareN+1
nullptr
linksrepresenting
children.
How to add pdf to powerpoint slide - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
export pdf to powerpoint; conversion of pdf to ppt online
How to add pdf to powerpoint slide - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
how to convert pdf to ppt using; how to convert pdf to ppt online
Exercises
183
A
B
D
G
H
E
I
J
L
M
C
F
K
Figure4.74 TreeforExercises4.1to4.3
4.5
Showthatthemaximumnumberofnodesinabinarytreeofheighthis2
h+1
−1.
4.6
Afullnodeisanodewithtwochildren.Provethatthenumberoffullnodesplus
oneisequaltothenumberofleavesinanonemptybinarytree.
4.7
Supposeabinarytreehasleavesl
1
,l
2
,...,l
M
atdepthsd
1
,d
2
,...,d
M
,respectively.
Provethat
M
i=1
2d
i
≤1anddeterminewhentheequalityistrue.
4.8
Give the prefix, infix, and postfix expressions s corresponding to o the tree e in
Figure4.75.
4.9
a. Showtheresultofinserting3,1,4,6,9,2,5,7intoaninitiallyemptybinary
searchtree.
b.Showtheresultofdeletingtheroot.
a
*
b
*
+
c
d
-
e
Figure4.75 TreeforExercise4.8
VB.NET PowerPoint: Read, Edit and Process PPTX File
How to convert PowerPoint to PDF, render PowerPoint to and effective VB.NET solution to add desired watermark on source PowerPoint slide at specified
pdf to powerpoint converter online; how to change pdf file to powerpoint
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
& editing library SDK, this VB.NET PowerPoint processing control add-on can to provide powerful & profession imaging controls, PDF document, image
change pdf to powerpoint online; convert pdf file into ppt
184
Chapter4 Trees
4.10 Letf(N)betheaveragenumberoffullnodesinanN-nodebinarysearchtree.
a. Determinethevaluesoff(0)andf(1).
b.ShowthatforN>1
f(N)=
N−2
N
+
1
N
N−1
i=0
(f(i)+f(Ni−1))
c. Show(byinduction)thatf(N)=(N−2)/3isasolutiontotheequationinpart
(b),withtheinitialconditionsinpart(a).
d.UsetheresultsofExercise4.6todeterminetheaveragenumberofleavesinan
N-nodebinarysearchtree.
4.11 Writeanimplementationofthe
set
class,withassociatediteratorsusingabinary
searchtree.Addtoeachnodealinktotheparentnode.
4.12 Write an implementation of f the
map
class by storing a a data member of type
set<Pair<KeyType,ValueType>>
.
4.13 Writeanimplementationofthe
set
class,withassociatediteratorsusingabinary
searchtree.Addtoeachnodealinktothenextsmallestandnextlargestnode.
Tomakeyourcodesimpler,addaheaderandtailnodewhicharenotpartofthe
binarysearchtree,buthelpmakethelinkedlistpartofthecodesimpler.
4.14 Supposeyouwanttoperformanexperimenttoverifytheproblemsthatcanbe
causedbyrandom
insert
/
remove
pairs.Hereisastrategythatisnotperfectlyran-
dom,butcloseenough.YoubuildatreewithNelementsbyinsertingNelements
chosenatrandomfromtherange1toMN.YouthenperformN
2
pairsofinser-
tionsfollowedbydeletions.Assumetheexistenceofaroutine,
randomInteger(a,b)
,
whichreturnsauniformrandomintegerbetween
a
and
b
inclusive.
a. Explainhowtogeneratearandomintegerbetween1andMthatisnotalready
inthetree(soarandominsertioncanbeperformed).IntermsofNandα,what
istherunningtimeofthisoperation?
b.Explainhowtogeneratearandomintegerbetween1andMthatisalreadyin
thetree(soarandomdeletioncanbeperformed).Whatistherunningtimeof
thisoperation?
c. Whatisagoodchoiceofα?Why?
4.15 Writeaprogramtoevaluateempiricallythefollowingstrategiesforremovingnodes
withtwochildren:
a. Replacewiththelargestnode,X,inT
L
andrecursivelyremoveX.
b.AlternatelyreplacewiththelargestnodeinT
L
andthesmallestnodeinT
R
,and
recursivelyremovetheappropriatenode.
c. ReplacewitheitherthelargestnodeinT
L
orthesmallestnodeinT
R
(recursively
removingtheappropriatenode),makingthechoicerandomly.
Whichstrategyseemstogivethemostbalance?WhichtakestheleastCPUtimeto
processtheentiresequence?
4.16 Redothebinarysearchtreeclasstoimplementlazydeletion.Notecarefullythat
thisaffectsalloftheroutines.Especiallychallengingare
findMin
and
findMax
,which
mustnowbedonerecursively.
C# PowerPoint - How to Process PowerPoint
With our C#.NET PowerPoint control, developers are able to split a PowerPoint into two or more small files. Add & Insert PowerPoint Page/Slide in C#.
convert pdf into ppt; converting pdf to powerpoint online
VB.NET PowerPoint: Edit PowerPoint Slide; Insert, Add or Delete
NET PowerPoint slide modifying control add-on enables view more VB.NET PowerPoint slide processing functions & profession imaging controls, PDF document, image
convert pdf to powerpoint online for; how to change pdf to powerpoint format
Exercises
185

4.17 Provethatthedepthofarandombinarysearchtree(depthofthedeepestnode)is
O(logN),onaverage.
4.18 a. GiveapreciseexpressionfortheminimumnumberofnodesinanAVLtreeof
heighth.
b.WhatistheminimumnumberofnodesinanAVLtreeofheight15?
4.19 Showtheresultofinserting2,1,4,5,9,3,6,7intoaninitiallyemptyAVLtree.
4.20 Keys1,2,...,2
k
−1areinsertedinorderintoaninitiallyemptyAVLtree.Prove
thattheresultingtreeisperfectlybalanced.
4.21 WritetheremainingprocedurestoimplementAVLsingleanddoublerotations.
4.22 Designalinear-timealgorithmthatverifiesthattheheightinformationinanAVL
treeiscorrectlymaintainedandthatthebalancepropertyisinorder.
4.23 WriteanonrecursivefunctiontoinsertintoanAVLtree.
4.24 ShowthatthedeletionalgorithminFigure4.47iscorrect
4.25 a. HowmanybitsarerequiredpernodetostoretheheightofanodeinanN-node
AVLtree?
b.WhatisthesmallestAVLtreethatoverflowsan8-bitheightcounter?
4.26 Writethefunctionstoperformthedoublerotationwithouttheinefficiencyofdoing
twosinglerotations.
4.27 Show the e resultof accessing thekeys 3,9,1,5 in order in the splay tree in
Figure4.76.
4.28 Showtheresultofdeletingtheelementwithkey6intheresultingsplaytreefor
thepreviousexercise.
4.29 a. Show w that if f all nodes in asplay treeare accessed in sequentialorder, the
resultingtreeconsistsofachainofleftchildren.
4
2
6
1
3
5
8
10
11
12
13
7
9
Figure4.76 TreeforExercise4.27
VB.NET PowerPoint: Read & Scan Barcode Image from PPT Slide
PDF-417 barcode scanning SDK to detect PDF-417 barcode How to customize VB.NET PowerPoint QR Code barcode scanning VB.NET PPT barcode scanner add-on to detect
embed pdf into powerpoint; how to change pdf to powerpoint slides
VB.NET PowerPoint: Convert & Render PPT into PDF Document
to convert one certain PowerPoint slide or a specified range of slides into .pdf document format using this VB.NET PowerPoint to PDF conversion library add-on.
pdf to ppt converter online; how to convert pdf slides to powerpoint
186
Chapter4 Trees

b.Showthatifallnodesinasplaytreeareaccessedinsequentialorder,thenthe
totalaccesstimeisO(N),regardlessoftheinitialtree.
4.30 Writeaprogramtoperformrandomoperationson splaytrees.Countthetotal
numberofrotationsperformedoverthesequence.How doestherunningtime
comparetoAVLtreesandunbalancedbinarysearchtrees?
4.31 Writeefficientfunctionsthattakeonlyapointertotherootofabinarytree,T,and
compute
a. thenumberofnodesinT
b.thenumberofleavesinT
c. thenumberoffullnodesinT
Whatistherunningtimeofyourroutines?
4.32 Designarecursivelinear-timealgorithmthattestswhetherabinarytreesatisfies
thesearchtreeorderpropertyateverynode.
4.33 WritearecursivefunctionthattakesapointertotherootnodeofatreeTand
returnsapointertotherootnodeofthetreethatresultsfromremovingallleaves
fromT.
4.34 WriteafunctiontogenerateanN-noderandombinarysearchtreewithdistinct
keys1throughN.Whatistherunningtimeofyourroutine?
4.35 WriteafunctiontogeneratetheAVLtreeofheighthwithfewestnodes.Whatis
therunningtimeofyourfunction?
4.36 Writeafunctiontogenerateaperfectlybalancedbinarysearchtreeofheighthwith
keys1through2
h+1
−1.Whatistherunningtimeofyourfunction?
4.37 Writeafunctionthattakesasinputabinarysearchtree,T,andtwokeys,k
1
andk
2
,
whichareorderedsothatk
1
k
2
,andprintsallelementsXinthetreesuchthat
k
1
Key(X)≤k
2
.Donotassumeanyinformationaboutthetypeofkeysexcept
thattheycanbeordered(consistently).YourprogramshouldruninO(K+logN)
averagetime,whereKisthenumberofkeysprinted.Boundtherunningtimeof
youralgorithm.
4.38 Thelargerbinarytreesinthischapterweregeneratedautomaticallybyaprogram.
Thiswasdonebyassigningan(x,y)coordinatetoeachtreenode,drawingacircle
aroundeachcoordinate(thisishardtoseeinsomepictures),andconnectingeach
nodetoitsparent.Assumeyouhaveabinarysearchtreestoredinmemory(perhaps
generatedbyoneoftheroutinesabove)andthateachnodehastwoextrafieldsto
storethecoordinates.
a. Thexcoordinatecanbecomputedbyassigningtheinordertraversalnumber.
Writearoutinetodothisforeachnodeinthetree.
b.Theycoordinatecanbecomputedbyusingthenegativeofthedepthofthe
node.Writearoutinetodothisforeachnodeinthetree.
c. Intermsofsomeimaginaryunit,whatwillthedimensionsofthepicturebe?
Howcanyouadjusttheunitssothatthetreeisalwaysroughlytwo-thirdsas
highasitiswide?
d.Provethatusingthissystemnolinescross,andthatforanynode,X,allelements
inX’sleftsubtreeappeartotheleftofXandallelementsinX’srightsubtree
appeartotherightofX.
VB.NET PowerPoint: VB Code to Draw and Create Annotation on PPT
for limitations (other documents are compatible, including PDF, TIFF, MS to install and use Microsoft PowerPoint software and what would you do to add and draw
converter pdf to powerpoint; convert pdf to editable ppt online
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
InsertPage" and "DeletePage" to add, insert or delete any certain PowerPoint slide without affecting the & profession imaging controls, PDF document, tiff
and paste pdf into powerpoint; pdf to powerpoint
Exercises
187
4.39 Writeageneral-purposetree-drawingprogramthatwillconvert atreeinto the
followinggraph-assemblerinstructions:
a. Circle(X,Y)
b.DrawLine(i,j)
Thefirstinstructiondrawsacircleat(X,Y),andthesecondinstructionconnects
theithcircletothejthcircle(circlesarenumberedintheorderdrawn).Youshould
eithermakethisaprogramanddefinesomesortofinputlanguageormakethisa
functionthatcanbecalledfromanyprogram.Whatistherunningtimeofyour
routine?
4.40 Writearoutinetolistoutthenodesofabinarytreeinlevel-order.Listtheroot,then
nodesatdepth1,followedbynodesatdepth2,andsoon.Youmustdothisin
lineartime.Proveyourtimebound.
4.41
a. WritearoutinetoperforminsertionintoaB-tree.
b.WritearoutinetoperformdeletionfromaB-tree.Whenanitemisdeleted,isit
necessarytoupdateinformationintheinternalnodes?
c. Modifyyourinsertionroutinesothatifanattemptismadetoaddintoanode
thatalreadyhasMentries,asearchisperformedforasiblingwithlessthanM
childrenbeforethenodeissplit.
4.42 AB
-treeoforderMisaB-treeinwhicheachinteriornodehasbetween2M/3and
Mchildren.DescribeamethodtoperforminsertionintoaB
-tree.
4.43 Show how w the e tree in Figure 4.77 is represented using a child/sibling link
implementation.
4.44 Writeaproceduretotraverseatreestoredwithchild/siblinglinks.
4.45 Twobinarytreesaresimilariftheyarebothemptyorbothnonemptyandhave
similarleftandrightsubtrees.Writeafunctiontodecidewhethertwobinarytrees
aresimilar.Whatistherunningtimeofyourfunction?
4.46 Twotrees,T
1
andT
2
,areisomorphicifT
1
canbetransformedintoT
2
byswapping
leftandrightchildrenof(someofthe)nodesinT
1
.Forinstance,thetwotreesin
Figure4.78areisomorphicbecausetheyarethesameifthechildrenofA,B,and
G,butnottheothernodes,areswapped.
a. Giveapolynomialtimealgorithmtodecideiftwotreesareisomorphic.
A
B
C
O
P
Q
R
G
D
E
F
N
H
I
J
K
L
M
Figure4.77 TreeforExercise4.43
VB.NET PowerPoint: VB Codes to Create Linear and 2D Barcodes on
Here is a market-leading PowerPoint barcode add-on within VB.NET class, which means it as well as 2d barcodes QR Code, Data Matrix, PDF-417, etc.
changing pdf to powerpoint file; convert pdf to powerpoint
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
Add(tmpFilePath1) docPathList.Add(tmpFilePath2) PPTXDocument this VB.NET PowerPoint slide processing tutorial & profession imaging controls, PDF document, image
add pdf to powerpoint; changing pdf to powerpoint
188
Chapter4 Trees
A
A
B
B
C
C
G
G
D
D
E
E
F
H
F
H
Figure4.78 Twoisomorphictrees
b.Whatistherunningtimeofyourprogram(thereisalinearsolution)?
4.47
a. ShowthatviaAVLsinglerotations,anybinarysearchtreeT
1
canbetransformed
intoanothersearchtreeT
2
(withthesameitems).
b.GiveanalgorithmtoperformthistransformationusingO(NlogN)rotationson
average.

c. ShowthatthistransformationcanbedonewithO(N)rotations,worst-case.
4.48 Suppose we want t to o add theoperation
findKth
to our repertoire.The opera-
tion
findKth(k)
returnsthe
k
th smallestitemin thetree.Assume allitemsare
distinct. Explain n how w tomodify y the binary search tree to o support this opera-
tionin O(logN)averagetime,withoutsacrificingthetimeboundsofanyother
operation.
4.49 SinceabinarysearchtreewithNnodeshasN+1
nullptr
pointers,halfthespace
allocatedinabinarysearchtreeforpointerinformationiswasted.Supposethat
ifanodehasa
nullptr
leftchild,wemakeitsleftchildlinktoitsinorderprede-
cessor,andifanodehasa
nullptr
rightchild,wemakeitsrightchildlinktoits
inordersuccessor.Thisisknownasathreadedtreeandtheextralinksarecalled
threads.
a. Howcanwedistinguishthreadsfromrealchildrenpointers?
b.Writeroutinestoperforminsertion and deletionintoatreethreadedinthe
mannerdescribedabove.
c. Whatistheadvantageofusingthreadedtrees?
4.50 WriteaprogramthatreadsaC
++
sourcecodefileandoutputsalistofallidentifiers
(thatis,variablenames,butnotkeywords,thatarenotfoundincommentsorstring
constants)inalphabeticalorder.Eachidentifiershouldbeoutputwithalistofline
numbersonwhichitoccurs.
4.51 Generateanindexforabook.Theinputfileconsistsofasetofindexentries.Each
lineconsistsofthestring
IX:
,followedbyanindexentrynameenclosedinbraces,
followedbyapagenumberthatisenclosedinbraces.Each
!
inanindexentry
namerepresentsasublevel.A
|(
representsthestartofarange,anda
|)
represents
theendoftherange.Occasionally,thisrangewillbethesamepage.Inthatcase,
outputonlyasinglepagenumber.Otherwise,donotcollapseorexpandrangeson
yourown.Asanexample,Figure4.79showssampleinputandFigure4.80shows
thecorrespondingoutput.
References
189
IX: {Series|(}
{2}
IX: {Series!geometric|(} } {4}
IX: {Euler’s s constant}
{4}
IX: {Series!geometric|)} } {4}
IX: {Series!arithmetic|(} } {4}
IX: {Series!arithmetic|)} } {5}
IX: {Series!harmonic|(}
{5}
IX: {Euler’s s constant}
{5}
IX: {Series!harmonic|)}
{5}
IX: {Series|)}
{5}
Figure4.79 SampleinputforExercise4.51
Euler’s constant: 4, 5
Series: 2-5
arithmetic: 4-5
geometric: 4
harmonic: 5
Figure4.80 SampleoutputforExercise4.51
References
Moreinformationonbinarysearchtrees,andinparticularthemathematicalpropertiesof
trees,canbefoundinthetwobooksbyKnuth,[22]and[23].
Severalpapersdealwiththelackofbalancecausedbybiaseddeletionalgorithmsin
binarysearchtrees.Hibbard’spaper[19]proposed theoriginaldeletion algorithmand
establishedthatonedeletionpreservestherandomnessofthetrees.Acompleteanalysishas
beenperformedonlyfortreeswiththreenodes[20]andfournodes[5].Eppinger’spaper
[14]providedearlyempiricalevidenceofnonrandomness,andthepapersbyCulberson
andMunro[10],[11]providedsomeanalyticalevidence(butnotacompleteproofforthe
generalcaseofintermixedinsertionsanddeletions).
Adelson-VelskiiandLandis[1]proposedAVLtrees.Recentlyitwasshown thatfor
AVLtrees,ifrebalancingisperformedonly on insertions,andnotondeletions,under
certaincircumstancestheresultingstructurestillmaintainsadepthofO(logM)whereM
isthenumberofinsertions[28].SimulationresultsforAVLtrees,andvariantsinwhich
theheightimbalanceisallowedtobeatmostkforvariousvaluesofk,arepresentedin
[21].AnalysisoftheaveragesearchcostinAVLtreesisincomplete,butsomeresultsare
containedin[24].
[3]and[8]consideredself-adjustingtreeslikethetypeinSection4.5.1.Splaytreesare
describedin[29].
B-treesfirstappearedin[6].Theimplementationdescribedintheoriginalpaperallows
datatobestoredininternalnodesaswellasleaves.Thedatastructurewehavedescribed
190
Chapter4 Trees
issometimesknownasaB
+
-tree.AsurveyofthedifferenttypesofB-treesispresentedin
[9].Empiricalresultsofthevariousschemesarereportedin[17].Analysisof2–3treesand
B-treescanbefoundin[4],[13],and[32].
Exercise4.17isdeceptivelydifficult.Asolutioncanbefoundin[15].Exercise4.29
isfrom[32].InformationonB*-trees,describedinExercise4.42,canbefoundin[12].
Exercise4.46isfrom[2].AsolutiontoExercise4.47using2N−6rotationsisgivenin
[30].Usingthreads,àlaExercise4.49,wasfirstproposedin[27].k-dtrees,whichhandle
multidimensionaldata,werefirstproposedin[7]andarediscussedinChapter12.
Otherpopularbalancedsearchtreesarered-blacktrees[18]andweight-balancedtrees
[26].Morebalanced-treeschemescanbefoundinthebooks[16]and[25].
1.G.M.Adelson-VelskiiandE.M.Landis,“AnAlgorithmfortheOrganizationofInforma-
tion,”Soviet.Mat.Doklady,3(1962),1259–1263.
2.A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,TheDesignandAnalysisofComputerAlgorithms,
Addison-Wesley,Reading,Mass.,1974.
3.B.AllenandJ.I.Munro,“SelfOrganizingSearchTrees,”JournaloftheACM,25(1978),
526–535.
4.R.A.Baeza-Yates,“ExpectedBehaviourofB+-treesunderRandomInsertions,”ActaInfor-
matica,26(1989),439–471.
5.R. A.Baeza-Yates, “ATrivial Algorithm Whose Analysis Isn’t:AContinuation,” BIT, 29
(1989),88–113.
6.R.BayerandE.M.McCreight,“OrganizationandMaintenanceofLargeOrderedIndices,”
ActaInformatica,1(1972),173–189.
7.J. L. Bentley, “Multidimensional Binary y Search h Trees s Used d for r Associative e Searching,”
CommunicationsoftheACM,18(1975),509–517.
8.J. R. . Bitner, “Heuristics s that Dynamically Organize Data Structures,” SIAM Journal on
Computing,8(1979),82–110.
9.D.Comer,“TheUbiquitousB-tree,”ComputingSurveys,11(1979),121–137.
10.J. CulbersonandJ. I. Munro, “Explaining the Behavior of BinarySearchTrees s under
ProlongedUpdates:AModelandSimulations,”ComputerJournal,32(1989),68–75.
11.J.CulbersonandJ.I.Munro,“AnalysisoftheStandardDeletionAlgorithmsinExactFit
DomainBinarySearchTrees,”Algorithmica,5(1990),295–311.
12.K.Culik,T.Ottman,andD.Wood,“DenseMultiwayTrees,”ACMTransactionsonDatabase
Systems,6(1981),486–512.
13.B.Eisenbath,N.Ziviana,G.H.Gonnet,K.Melhorn,andD.Wood,“TheTheoryofFringe
AnalysisandItsApplicationto2–3TreesandB-trees,”InformationandControl,55(1982),
125–174.
14.J. L. Eppinger, “AnEmpirical StudyofInsertionandDeletioninBinarySearchTrees,”
CommunicationsoftheACM,26(1983),663–669.
15.P.FlajoletandA.Odlyzko,“TheAverageHeightofBinaryTreesandOtherSimpleTrees,”
JournalofComputerandSystemSciences,25(1982),171–213.
16.G. H. Gonnetand R. Baeza-Yates, Handbook of Algorithms andDataStructures,2ded.,
Addison-Wesley,Reading,Mass.,1991.
17.E. Gudes and d S. . Tsur, “Experiments with h B-tree Reorganization,” Proceedings of ACM
SIGMODSymposiumonManagementofData(1980),200–206.
References
191
18.L.J.GuibasandR.Sedgewick,“ADichromaticFrameworkforBalancedTrees,”Proceedings
oftheNineteenthAnnualIEEESymposiumonFoundationsofComputerScience(1978),8–21.
19.T. H. . Hibbard, “Some Combinatorial Properties s of Certain Trees s with h Applications s to
SearchingandSorting,”JournaloftheACM,9(1962),13–28.
20.A. T.JonassenandD. E.Knuth,“ATrivialAlgorithmWhoseAnalysis Isn’t,” Journalof
ComputerandSystemSciences,16(1978),301–322.
21.P.L.Karlton,S.H.Fuller,R.E.Scroggs,andE.B.Kaehler,“PerformanceofHeightBalanced
Trees,”CommunicationsoftheACM,19(1976),23–28.
22.D. E.Knuth, TheArtofComputer Programming:Vol.1:FundamentalAlgorithms, 3d ed.,
Addison-Wesley,Reading,Mass.,1997.
23.D.E.Knuth,TheArtofComputerProgramming:Vol.3:SortingandSearching,2ded.,Addison-
Wesley,Reading,Mass.,1998.
24.K.Melhorn,“APartialAnalysis of Height-BalancedTreesunderRandomInsertionsand
Deletions,”SIAMJournalofComputing,11(1982),748–760.
25.K.Melhorn,DataStructuresandAlgorithms1:SortingandSearching,Springer-Verlag,Berlin,
1984.
26.J.NievergeltandE.M.Reingold,“BinarySearchTreesofBoundedBalance,”SIAMJournal
onComputing,2(1973),33–43.
27.A.J.PerlisandC.Thornton,“SymbolManipulationinThreadedLists,”Communicationsof
theACM,3(1960),195–204.
28.S. Sen n and R. E. Tarjan, “Deletion Without Rebalancing in n Balanced Binary y Trees,”
ProceedingsoftheTwentiethSymposiumonDiscreteAlgorithms(2010),1490–1499.
29.D.D.SleatorandR.E.Tarjan,“Self-adjustingBinarySearchTrees,”JournaloftheACM,32
(1985),652–686.
30.D.D.Sleator,R.E. Tarjan,andW.P.Thurston,“RotationDistance,Triangulations,and
HyperbolicGeometry,”JournaloftheAMS(1988),647–682.
31.R.E.Tarjan,“SequentialAccessinSplayTreesTakesLinearTime,”Combinatorica,5(1985),
367–378.
32.A.C.Yao,“OnRandom2–3Trees,”ActaInformatica,9(1978),159–170.
Documents you may be interested
Documents you may be interested