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
sizedependsonlyontherelativerankofthefirstelementinsertedintothetree),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
theleftsubtreesdeeperthantheright,becausewearealwaysreplacingadeletednode
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
4.3 TheSearchTreeADT—BinarySearchTrees
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-
allyextremelydifficultandcanrequireassumptionsthatmayormaynotbevalid.Inthe
absenceofdeletions,orwhenlazydeletion isused,wecan concludethattheaverage
runningtimesoftheoperationsaboveareO(logN).Exceptforstrangecasesliketheone
discussedabove,thisresultisveryconsistentwithobservedbehavior.
Iftheinputcomesintoatreepresorted,thenaseriesof
insert
swilltakequadratic
timeandgiveaveryexpensiveimplementationofalinkedlist,sincethetreewillconsist
onlyofnodeswithnoleftchildren.Onesolutiontotheproblemistoinsistonanextra
structuralconditioncalledbalance:Nonodeisallowedtogettoodeep.
Therearequiteafewgeneralalgorithmstoimplementbalancedtrees.Mostarequite
abitmorecomplicatedthanastandardbinarysearchtree,andalltakelongeronaverage
forupdates.Theydo,however,provideprotectionagainsttheembarrassinglysimplecases.
Below,wewillsketchoneoftheoldestformsofbalancedsearchtrees,theAVLtree.
Asecondmethodistoforgothebalanceconditionandallowthetreetobearbitrarily
deep,butaftereveryoperation,arestructuringruleisappliedthattendstomakefuture
operationsefficient.Thesetypesofdatastructuresaregenerallyclassifiedasself-adjusting.
Inthecaseofabinarysearchtree,wecannolongerguaranteeanO(logN)boundonany
singleoperationbutcanshowthatanysequenceofMoperationstakestotaltimeO(MlogN)
in theworst case.Thisis generally sufficient protection againstabadworstcase.The
datastructurewewilldiscussisknownasasplaytree;itsanalysisisfairlyintricateandis
discussedinChapter11.
4.4 AVLTrees
AnAVL(Adelson-VelskiiandLandis)treeisabinarysearchtreewithabalancecondition.
Thebalanceconditionmustbeeasytomaintain,anditensuresthatthedepthofthetree
isO(logN).Thesimplestideaistorequirethattheleftandrightsubtreeshavethesame
height.AsFigure4.31shows,thisideadoesnotforcethetreetobeshallow.
Figure4.31 Abadbinarytree.Requiringbalanceattherootisnotenough.
.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 subtreeisdefined tobe−1(asis
usual),thenonlyperfectlybalancedtreesof2
k
−1nodeswouldsatisfythis criterion.
Thus,althoughthisguaranteestreesofsmalldepth,thebalanceconditionistoorigidto
beusefulandneedstoberelaxed.
AnAVLtreeisidenticaltoabinarysearchtree,exceptthatforeverynodeinthetree,
theheightoftheleftandrightsubtreescandifferbyatmost1.(Theheightofanempty
treeisdefinedtobe−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
ispotentiallydifficultisthatinsertinganodecould violatetheAVLtreeproperty.(For
instance,inserting6intotheAVLtreeinFigure4.32woulddestroythebalancecondition
atthenodewithkey8.)Ifthisisthecase,thenthepropertyhastoberestoredbeforethe
insertionstepisconsideredover.Itturnsoutthatthiscanalwaysbedonewithasimple
modificationtothetree,knownasarotation.
Afteraninsertion,onlynodesthatareonthepathfromtheinsertionpointtotheroot
mighthavetheirbalancealteredbecauseonlythosenodeshavetheirsubtreesaltered.As
wefollowthepathuptotherootandupdatethebalancinginformation,wemayfinda
nodewhosenewbalanceviolatestheAVLcondition.Wewillshowhowtorebalancethe
treeatthefirst(i.e.,deepest)suchnode,andwewillprovethatthisrebalancingguarantees
thattheentiretreesatisfiestheAVLproperty.
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.
Thefirstcase,inwhichtheinsertionoccursonthe“outside”(i.e.,left–leftorright–
right),isfixedbyasinglerotationofthetree.Thesecondcase,inwhichtheinsertion
occursonthe“inside”(i.e.,left–rightorright–left)ishandledbytheslightlymorecomplex
doublerotation.Thesearefundamentaloperationsonthetreethatwe’llseeusedseveral
timesinbalanced-treealgorithms.Theremainderofthissectiondescribestheserotations,
provesthattheysufficetomaintainbalance,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.34showsthesinglerotationthatfixescase1.Thebeforepictureisontheleftand
theafterisontheright.Letusanalyzecarefullywhatisgoingon.Nodek
2
violatesthe
AVLbalancepropertybecauseitsleftsubtreeistwolevelsdeeperthanitsrightsubtree
(thedashedlinesinthemiddleofthediagrammarkthelevels).Thesituationdepicted
istheonlypossiblecase1scenariothatallowsk
2
tosatisfytheAVLpropertybeforean
insertionbutviolateitafterwards.SubtreeXhasgrowntoanextralevel,causingittobe
exactlytwolevelsdeeperthanZ.YcannotbeatthesamelevelasthenewXbecausethen
k
2
wouldhavebeenoutofbalancebeforetheinsertion,andYcannotbeatthesamelevelas
Zbecausethenk
1
wouldbethefirstnodeonthepathtowardtherootthatwasinviolation
oftheAVLbalancingcondition.
Toideallyrebalancethetree,wewouldliketomoveXupalevelandZdownalevel.
NotethatthisisactuallymorethantheAVLpropertywouldrequire.Todothis,werear-
rangenodesintoanequivalenttreeasshowninthesecondpartofFigure4.34.Hereis
anabstractscenario:Visualizethetreeasbeingflexible,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
originaltree,canbeplacedask
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.Thefirstproblemoccurswhenitistimetoinsertitem1becausetheAVL
k
2
k
1
Z
Y
X
k
1
k
2
X
Z
Y
Figure4.34 Singlerotationtofixcase1
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,thenfixedbyasinglerotation
k
2
k
1
Z
Y
X
k
1
k
2
X
Z
Y
Figure4.36 Singlerotationfixescase4
propertyisviolatedattheroot.Weperformasinglerotationbetweentherootanditsleft
childtofixtheproblem.Herearethebeforeandaftertrees:
3
2
2
3
1
1
before
after
Adashedlinejoinsthetwonodesthatarethesubjectoftherotation.Nextweinsert4,
whichcausesnoproblems,buttheinsertionof5createsaviolationatnode3thatisfixed
byasinglerotation.Besidesthelocalchangecausedbytherotation,theprogrammermust
rememberthattherestofthetreehastobeinformedofthischange.Herethismeansthat
2’srightchildmustberesettolinkto4insteadof3.Forgettingtodosoiseasyandwould
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.
ThefactthatsubtreeYinFigure4.37hashadaniteminsertedintoitguaranteesthatit
isnonempty.Thus,wemayassumethatithasarootandtwosubtrees.Consequently,the
150
Chapter4 Trees
k
2
k
1
Z
Y
X
k
1
k
2
Z
Y
X
Figure4.37 Singlerotationfailstofixcase2
D
C
B
k
2
k
1
k
1
k
2
k
3
k
3
A
A
D
B
C
Figure4.38 Left–rightdoublerotationtofixcase2
treemaybeviewedasfoursubtreesconnectedbythreenodes.Asthediagramsuggests,
exactlyoneoftreeBorCistwolevelsdeeperthanD(unlessallareempty),butwecannot
besurewhichone.Itturnsoutnottomatter;inFigure4.38,bothBandCaredrawnat
1
1
2
levelsbelowD.
Torebalance,weseethatwecannotleavek
3
astheroot,andarotationbetweenk
3
and
k
1
wasshowninFigure4.37tonotwork,sotheonlyalternativeistoplacek
2
asthenew
root.Thisforcesk
1
tobek
2
’sleftchildandk
3
tobeitsrightchild,anditalsocompletely
determinestheresultinglocationsofthefoursubtrees.Itiseasytoseethattheresulting
treesatisfiestheAVLtreeproperty,andaswasthecasewiththesinglerotation,itrestores
theheighttowhatitwasbeforetheinsertion,thusguaranteeingthatallrebalancingand
heightupdatingiscomplete.Figure4.39showsthatthesymmetriccase3canalsobefixed
k
1
k
3
k
2
A
B
C
k
2
k
1
k
3
A
D
D
B
C
Figure4.39 Right–leftdoublerotationtofixcase3
4.4 AVLTrees
151
byadoublerotation.Inbothcasestheeffectisthesameasrotatingbetweenα’schildand
grandchild,andthenbetweenαanditsnewchild.
Wewillcontinueourpreviousexamplebyinserting10through16inreverseorder,
followedby8andthen9.Inserting16iseasy,sinceitdoesnotdestroythebalanceproperty,
butinserting15causesaheightimbalanceatnode7.Thisiscase3,whichissolvedbya
right–leftdoublerotation.Inourexample,theright–leftdoublerotationwillinvolve7,16,
and15.Inthiscase,k
1
isthenodewithitem7,k
3
isthenodewithitem16,andk
2
isthe
nodewithitem15.SubtreesA,B,C,andDareempty.
4
2
6
1
3
5
7
15
4
2
6
1
3
5
15
7
16
16
k
1
k
3
k
2
k
1
k
2
k
3
before
after
Nextweinsert14,whichalsorequiresadoublerotation.Herethedoublerotation
thatwillrestorethetreeisagainaright–leftdoublerotationthatwillinvolve6,15,and
7.Inthiscase,k
1
isthenodewithitem6,k
2
isthenodewithitem7,andk
3
isthenode
withitem15.SubtreeAisthetreerootedatthenodewithitem5;subtreeBistheempty
subtreethatwasoriginallytheleftchildofthenodewithitem7,subtreeCisthetree
rootedatthenodewithitem14,andfinally,subtreeDisthetreerootedatthenodewith
item16.
4
4
2
2
6
1
3
5
15
7
5
14
16
16
14
7
1
3
6
15
k
1
k
2
k
3
before
after
k
1
k
3
k
2
If13isnowinserted,thereisanimbalanceattheroot.Since13isnotbetween4and
7,weknowthatthesinglerotationwillwork.
Documents you may be interested
Documents you may be interested