﻿
142
Chapter4 Trees
1
/**
2
* Copy y constructor
3
*/
4
BinarySearchTree( const t BinarySearchTree & & rhs ) ) : : root{ { nullptr r }
5
{
6
root = = clone( ( rhs.root t );
7
}
8
9
/
**
10
*
Internal method to o clone e subtree.
11
*/
12
BinaryNode * * clone( ( BinaryNode e *t ) ) const
13
{
14
if( t t == = nullptr )
15
return nullptr;
16
else
17
return new BinaryNode{ { t->element, clone( ( t->left ), clone( ( t->right ) ) };
18
}
Figure4.28 Copyconstructorandrecursiveclonememberfunction
LetD(N)betheinternalpathlengthforsometreeTofNnodes.D(1)=0.AnN-node
treeconsistsofani-nodeleftsubtreeandan(Ni−1)-noderightsubtree,plusarootat
depthzerofor0≤i<N.D(i)istheinternalpathlengthoftheleftsubtreewithrespectto
itsroot.Inthemaintree,allthesenodesareoneleveldeeper.Thesameholdsfortheright
subtree.Thus,wegettherecurrence
D(N)=D(i)+D(Ni−1)+N−1
Ifallsubtreesizesareequallylikely,whichistrueforbinarysearchtrees(sincethesubtree
sizedependsonlyontherelativerankoftheﬁrstelementinsertedintothetree),butnot
binarytrees,thentheaveragevalueofbothD(i)andD(Ni−1)is(1/N)
N−1
j=0
D(j).
Thisyields
D(N)=
2
N
N−1
j=0
D(j)
+N−1
ThisrecurrencewillbeencounteredandsolvedinChapter7,obtaininganaveragevalueof
D(N)=O(NlogN).Thus,theexpecteddepthofanynodeisO(logN).Asanexample,the
randomlygenerated500-nodetreeshowninFigure4.29hasnodesatexpecteddepth9.98.
Itistemptingtosayimmediatelythatthisresultimpliesthattheaveragerunningtime
ofalltheoperationsdiscussedintheprevioussectionisO(logN),butthisisnotentirely
true.Thereasonforthisisthatbecauseofdeletions,itisnotclearthatallbinarysearch
treesareequallylikely.Inparticular,thedeletionalgorithmdescribedabovefavorsmaking
withanodefromtherightsubtree.Theexacteffectofthisstrategyisstillunknown,but
Pdf to powerpoint conversion - 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
convert pdf to powerpoint online; convert pdf file to powerpoint
Pdf to powerpoint conversion - 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 file to powerpoint presentation; conversion of pdf to ppt online
143
Figure4.29 Arandomlygeneratedbinarysearchtree
itseemsonlytobeatheoreticalnovelty.Ithasbeenshownthatifwealternateinsertions
anddeletions(N
2
)times,thenthetreeswillhaveanexpecteddepthof(
N).After
aquarter-millionrandom
insert
/
remove
pairs,thetreethatwassomewhatright-heavyin
Figure4.29looksdecidedlyunbalanced(averagedepth=12.51)inFigure4.30.
Wecouldtrytoeliminatetheproblembyrandomlychoosingbetweenthesmallest
elementintherightsubtreeandthelargestintheleftwhenreplacingthedeletedelement.
Thisapparentlyeliminatesthebiasandshouldkeepthetreesbalanced,butnobodyhas
Figure4.30 Binarysearchtreeafter(N
2)
insert
/
remove
pairs
Online Convert PowerPoint to PDF file. Best free online export
area. Then just wait until the conversion from Powerpoint to PDF is complete and download the file. The perfect conversion tool.
how to add pdf to powerpoint presentation; convert pdf to powerpoint using
C# powerpoint - PowerPoint Conversion & Rendering in C#.NET
And detailed C# demo codes for these conversions are offered below. C# Demo Codes for PowerPoint Conversions. PowerPoint to PDF Conversion.
how to convert pdf slides to powerpoint; change pdf to powerpoint
144
Chapter4 Trees
actuallyprovedthis.Inanyevent,thisphenomenonappearstobemostlyatheoretical
novelty,becausetheeffectdoesnotshowupatallforsmalltrees,and,strangerstill,if
o(N
2
)
insert
/
remove
pairsareused,thenthetreeseemstogainbalance!
Themain point of thisdiscussion isthatdeciding what “average”meansisgener-
allyextremelydifﬁcultandcanrequireassumptionsthatmayormaynotbevalid.Inthe
absenceofdeletions,orwhenlazydeletion isused,wecan concludethattheaverage
runningtimesoftheoperationsaboveareO(logN).Exceptforstrangecasesliketheone
discussedabove,thisresultisveryconsistentwithobservedbehavior.
Iftheinputcomesintoatreepresorted,thenaseriesof
insert
onlyofnodeswithnoleftchildren.Onesolutiontotheproblemistoinsistonanextra
structuralconditioncalledbalance:Nonodeisallowedtogettoodeep.
Therearequiteafewgeneralalgorithmstoimplementbalancedtrees.Mostarequite
abitmorecomplicatedthanastandardbinarysearchtree,andalltakelongeronaverage
Below,wewillsketchoneoftheoldestformsofbalancedsearchtrees,theAVLtree.
Asecondmethodistoforgothebalanceconditionandallowthetreetobearbitrarily
deep,butaftereveryoperation,arestructuringruleisappliedthattendstomakefuture
Inthecaseofabinarysearchtree,wecannolongerguaranteeanO(logN)boundonany
singleoperationbutcanshowthatanysequenceofMoperationstakestotaltimeO(MlogN)
in theworst case.Thisis generally sufﬁcient protection againstabadworstcase.The
datastructurewewilldiscussisknownasasplaytree;itsanalysisisfairlyintricateandis
discussedinChapter11.
4.4 AVLTrees
Thebalanceconditionmustbeeasytomaintain,anditensuresthatthedepthofthetree
isO(logN).Thesimplestideaistorequirethattheleftandrightsubtreeshavethesame
.NET PDF Document Viewing, Annotation, Conversion & Processing
XDoc.PDF SDK for .NET. RasterEdge XDoc.PDF for .NET is a professional .NET PDF solution that provides complete and advanced PDF document processing features.
table from pdf to powerpoint; pdf to powerpoint converter online
VB.NET PDF Converter Library SDK to convert PDF to other file
Conversion of MS Office to PDF. This guide give a series of demo code directly for converting MicroSoft Office Word, Excel and PowerPoint document to PDF file
pdf to powerpoint conversion; pdf page to powerpoint
4.4 AVLTrees
145
Anotherbalanceconditionwouldinsistthateverynodemusthaveleftandrightsub-
treesofthesameheight.Iftheheightofanempty subtreeisdeﬁned tobe−1(asis
usual),thenonlyperfectlybalancedtreesof2
k
−1nodeswouldsatisfythis criterion.
Thus,althoughthisguaranteestreesofsmalldepth,thebalanceconditionistoorigidto
beusefulandneedstoberelaxed.
AnAVLtreeisidenticaltoabinarysearchtree,exceptthatforeverynodeinthetree,
theheightoftheleftandrightsubtreescandifferbyatmost1.(Theheightofanempty
treeisdeﬁnedtobe−1.)InFigure4.32thetreeontheleftisanAVLtreebutthetreeon
therightisnot.Heightinformationiskeptforeachnode(inthenodestructure).Itcanbe
shownthattheheightofanAVLtreeisatmostroughly1.44log(N+2)−1.328,butin
practiceitisonlyslightlymorethanlogN.Asanexample,theAVLtreeofheight9with
thefewestnodes(143)isshowninFigure4.33.ThistreehasasaleftsubtreeanAVLtree
ofheight7ofminimumsize.TherightsubtreeisanAVLtreeofheight8ofminimumsize.
Thistellsusthattheminimumnumberofnodes,S(h),inanAVLtreeofheighthisgiven
byS(h)=S(h−1)+S(h−2)+1.Forh=0,S(h)=1.Forh=1,S(h)=2.Thefunction
S(h)iscloselyrelatedtotheFibonaccinumbers,fromwhichtheboundclaimedaboveon
theheightofanAVLtreefollows.
Thus, allthe tree operations can n be performed in O(logN)time,except possibly
insertionanddeletion.Whenwedoaninsertion,weneedtoupdateallthebalancing
informationforthenodesonthe path back to theroot,but thereasonthatinsertion
ispotentiallydifﬁcultisthatinsertinganodecould violatetheAVLtreeproperty.(For
instance,inserting6intotheAVLtreeinFigure4.32woulddestroythebalancecondition
atthenodewithkey8.)Ifthisisthecase,thenthepropertyhastoberestoredbeforethe
insertionstepisconsideredover.Itturnsoutthatthiscanalwaysbedonewithasimple
modiﬁcationtothetree,knownasarotation.
Afteraninsertion,onlynodesthatareonthepathfromtheinsertionpointtotheroot
mighthavetheirbalancealteredbecauseonlythosenodeshavetheirsubtreesaltered.As
wefollowthepathuptotherootandupdatethebalancinginformation,wemayﬁnda
nodewhosenewbalanceviolatestheAVLcondition.Wewillshowhowtorebalancethe
treeattheﬁrst(i.e.,deepest)suchnode,andwewillprovethatthisrebalancingguarantees
thattheentiretreesatisﬁestheAVLproperty.
5
2
8
1
4
3
7
7
2
8
1
4
3
5
Figure4.32 Twobinarysearchtrees.OnlythelefttreeisAVL.
C# PDF Converter Library SDK to convert PDF to other file formats
C#.NET PDF - PDF Conversion & Rendering SDK for C#.NET. A best C# PDF converter control for adobe PDF document conversion in Visual Studio .NET applications.
changing pdf to powerpoint; pdf to ppt
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document. Provide Free Demo Code for PDF Conversion from Microsoft PowerPoint in C# Program.
convert pdf to powerpoint slide; how to convert pdf into powerpoint slides
146
Chapter4 Trees
Figure4.33 SmallestAVLtreeofheight9
Letuscallthenodethatmustberebalancedα.Sinceanynodehasatmosttwochil-
dren,andaheightimbalancerequiresthatα’stwosubtrees’heightsdifferbytwo,itiseasy
toseethataviolationmightoccurinfourcases:
1. Aninsertionintotheleftsubtreeoftheleftchildofα
2. Aninsertionintotherightsubtreeoftheleftchildofα
3. Aninsertionintotheleftsubtreeoftherightchildofα
4. Aninsertionintotherightsubtreeoftherightchildofα
Cases1and 4are mirrorimagesymmetrieswithrespecttoα,asare cases 2and
3.Consequently,asamatteroftheory,therearetwobasiccases.Fromaprogramming
perspective,ofcourse,therearestillfourcases.
Theﬁrstcase,inwhichtheinsertionoccursonthe“outside”(i.e.,left–leftorright–
right),isﬁxedbyasinglerotationofthetree.Thesecondcase,inwhichtheinsertion
occursonthe“inside”(i.e.,left–rightorright–left)ishandledbytheslightlymorecomplex
doublerotation.Thesearefundamentaloperationsonthetreethatwe’llseeusedseveral
timesinbalanced-treealgorithms.Theremainderofthissectiondescribestheserotations,
provesthattheysufﬁcetomaintainbalance,andgivesacasualimplementationoftheAVL
tree.Chapter12describesotherbalanced-treemethodswithaneyetowardamorecareful
implementation.
C# PDF Convert: How to Convert Word, Excel, PowerPoint, Tiff
In addition to Word and Excel, Office PowerPoint is also supported by our SDK. Please click to see detailed C# programming demo for PPT to PDF conversion.
convert pdf to ppt; pdf to powerpoint converter
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
resolution, bit depth, scaling, etc. Implement Conversion from PowerPoint to PDF in VB.NET, Converting PowerPoint document to PDF
convert pdf file to powerpoint presentation; converting pdf to powerpoint
4.4 AVLTrees
147
4.4.1 SingleRotation
Figure4.34showsthesinglerotationthatﬁxescase1.Thebeforepictureisontheleftand
theafterisontheright.Letusanalyzecarefullywhatisgoingon.Nodek
2
violatesthe
AVLbalancepropertybecauseitsleftsubtreeistwolevelsdeeperthanitsrightsubtree
(thedashedlinesinthemiddleofthediagrammarkthelevels).Thesituationdepicted
istheonlypossiblecase1scenariothatallowsk
2
tosatisfytheAVLpropertybeforean
insertionbutviolateitafterwards.SubtreeXhasgrowntoanextralevel,causingittobe
exactlytwolevelsdeeperthanZ.YcannotbeatthesamelevelasthenewXbecausethen
k
2
wouldhavebeenoutofbalancebeforetheinsertion,andYcannotbeatthesamelevelas
Zbecausethenk
1
wouldbetheﬁrstnodeonthepathtowardtherootthatwasinviolation
oftheAVLbalancingcondition.
Toideallyrebalancethetree,wewouldliketomoveXupalevelandZdownalevel.
NotethatthisisactuallymorethantheAVLpropertywouldrequire.Todothis,werear-
rangenodesintoanequivalenttreeasshowninthesecondpartofFigure4.34.Hereis
anabstractscenario:Visualizethetreeasbeingﬂexible,grabthechildnodek
1
,closeyour
eyes,and shakeit,lettinggravitytakehold.Theresultisthatk
1
willbethenewroot.
Thebinarysearchtreepropertytellsusthatintheoriginaltreek
2
k
1
,sok
2
becomes
therightchildofk
1
inthenew tree.Xandremainastheleftchildofk
1
andright
childofk
2
,respectively.SubtreeY,whichholdsitemsthatarebetweenk
1
andk
2
inthe
2
’sleftchildinthenewtreeandsatisfyalltheordering
requirements.
Asaresultofthiswork,whichrequiresonlyafewpointerchanges,wehaveanother
binarysearch treethatisanAVLtree.Thishappens becausemovesuponelevel,Y
staysatthesamelevel,andZmovesdownonelevel.k
2
andk
1
notonlysatisfytheAVL
requirements,buttheyalsohavesubtreesthatareexactlythesameheight.Furthermore,
thenewheightoftheentiresubtreeisexactlythesameastheheightoftheoriginalsubtree
priortotheinsertionthatcausedXtogrow.Thusnofurtherupdatingofheightsonthe
pathtotherootisneeded,andconsequentlynofurtherrotationsareneeded.Figure4.35
showsthataftertheinsertionof6intotheoriginalAVLtreeontheleft,node8becomes
unbalanced.Thus,wedoasinglerotationbetween7and8,obtainingthetreeontheright.
Aswementionedearlier,case4representsasymmetriccase.Figure4.36showshow
asinglerotationisapplied.Letusworkthrougharatherlongexample.Supposewestart
withaninitiallyemptyAVLtreeandinserttheitems3,2,1,andthen 4through7in
sequentialorder.Theﬁrstproblemoccurswhenitistimetoinsertitem1becausetheAVL
k
2
k
1
Z
Y
X
k
1
k
2
X
Z
Y
Figure4.34 Singlerotationtoﬁxcase1
C# powerpoint - Convert PowerPoint to PDF in C#.NET
PowerPoint to PDF Conversion Overview. RasterEdge XDoc.PowerPoint empowers your C#.NET application with advanced PowerPoint to PDF conversion functionality.
convert pdf to powerpoint online for; how to change pdf to powerpoint format
C# Windows Viewer - Image and Document Conversion & Rendering in
CSV Document Conversion. RasterEdge Windows Viewer SDK provides how to convert TIFF: Convert to PDF. Convert to Various Images. PDF Document Conversion.
change pdf to ppt; how to convert pdf slides to powerpoint presentation
148
Chapter4 Trees
5
2
8
1
4
3
7
6
5
2
7
1
4
3
6
8
Figure4.35 AVLpropertydestroyedbyinsertionof6,thenﬁxedbyasinglerotation
k
2
k
1
Z
Y
X
k
1
k
2
X
Z
Y
Figure4.36 Singlerotationﬁxescase4
propertyisviolatedattheroot.Weperformasinglerotationbetweentherootanditsleft
childtoﬁxtheproblem.Herearethebeforeandaftertrees:
3
2
2
3
1
1
before
after
whichcausesnoproblems,buttheinsertionof5createsaviolationatnode3thatisﬁxed
byasinglerotation.Besidesthelocalchangecausedbytherotation,theprogrammermust
rememberthattherestofthetreehastobeinformedofthischange.Herethismeansthat
destroythetree(4wouldbeinaccessible).
4.4 AVLTrees
149
2
1
3
4
5
2
1
4
3
5
before
after
Nextweinsert6.Thiscausesabalanceproblemattheroot,sinceitsleftsubtreeisof
height0anditsrightsubtreewouldbeheight2.Therefore,weperformasinglerotationat
therootbetween2and4.
2
1
4
3
5
6
4
2
5
1
3
6
before
after
Therotationisperformedbymaking2achildof4and4’soriginalleftsubtreethenewright
subtreeof2.Everyiteminthissubtreemustliebetween2and4,sothistransformation
makessense.Thenextitemweinsertis7,whichcausesanotherrotation:
4
2
5
1
3
6
7
4
2
6
1
3
5
7
before
after
4.4.2 DoubleRotation
Thealgorithmdescribedabovehasoneproblem:AsFigure4.37shows,itdoesnotwork
forcases2or3.TheproblemisthatsubtreeYistoodeep,andasinglerotationdoesnot
makeitanylessdeep.ThedoublerotationthatsolvestheproblemisshowninFigure4.38.