132
Chapter4 Trees
4.3 TheSearchTreeADT—Binary
SearchTrees
Animportantapplicationofbinarytreesistheiruseinsearching.Letusassumethateach
nodeinthetreestoresanitem.Inourexamples,wewillassume,forsimplicity,thatthese
areintegers,althougharbitrarilycomplexitemsareeasilyhandledinC
++
.Wewillalso
assumethatalltheitemsaredistinct,andwewilldealwithduplicateslater.
Thepropertythatmakesabinarytreeintoabinarysearchtreeisthatforeverynode,
X,inthetree,thevaluesofalltheitemsinitsleftsubtreearesmallerthantheiteminX,
andthevaluesofalltheitemsinitsrightsubtreearelargerthantheiteminX.Noticethat
thisimpliesthatalltheelementsinthetreecanbeorderedinsomeconsistentmanner.In
Figure4.15,thetreeontheleftisabinarysearchtree,butthetreeontherightisnot.The
treeontherighthasanodewithitem7intheleftsubtreeofanodewithitem6(which
happenstobetheroot).
Wenowgivebriefdescriptionsoftheoperationsthatareusuallyperformedonbinary
searchtrees.Notethatbecauseoftherecursivedefinitionoftrees,itiscommontowrite
theseroutinesrecursively.Becausetheaveragedepthofabinarysearchtreeturnsouttobe
O(logN),wegenerallydonotneedtoworryaboutrunningoutofstackspace.
Figure4.16showstheinterfaceforthe
BinarySearchTree
classtemplate.Therearesev-
eralthingsworthnoticing.Searchingisbasedonthe
<
operatorthatmustbedefinedforthe
particular
Comparable
type.Specifically,item
x
matches
y
ifboth
x<y
and
y<x
are
false
.This
allows
Comparable
tobeacomplextype(suchasanemployeerecord),withacomparison
functiondefinedononlypartofthetype(suchasthesocialsecuritynumberdatamem-
berorsalary).Section1.6.3illustratesthegeneraltechniqueofdesigningaclassthatcan
beusedasa
Comparable
.Analternative,describedinSection4.3.1,istoallowafunction
object.
Thedatamemberisa pointer totherootnode;this pointeris
nullptr
for empty
trees.The
public
memberfunctionsusethegeneraltechniqueofcalling
private
recursive
functions.Anexampleofhowthisisdonefor
contains
,
insert
,and
remove
isshownin
Figure4.17.
6
2
8
1
4
3
6
2
8
1
4
3
7
Figure4.15 Twobinarytrees(onlythelefttreeisasearchtree)
Change pdf to powerpoint on - 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
pdf to ppt converter online for large; convert pdf into ppt online
Change pdf to powerpoint on - 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 online; how to add pdf to powerpoint slide
1
template <typename Comparable>
2
class BinarySearchTree
3
{
4
public:
5
BinarySearchTree( );
6
BinarySearchTree( const BinarySearchTree & rhs );
7
BinarySearchTree( BinarySearchTree&& rhs);
8
~BinarySearchTree();
9
10
const Comparable &findMin( ) const;
11
const Comparable &findMax( ) const;
12
bool contains( const Comparable & x ) const;
13
bool isEmpty( ) const;
14
void printTree( ostream &out = cout ) const;
15
16
void makeEmpty( );
17
void insert( constComparable & x );
18
void insert( Comparable && x );
19
void remove( constComparable & x );
20
21
BinarySearchTree &operator=( const BinarySearchTree & rhs );
22
BinarySearchTree &operator=( BinarySearchTree && rhs );
23
24
private:
25
struct BinaryNode
26
{
27
Comparable element;
28
BinaryNode *left;
29
BinaryNode *right;
30
31
BinaryNode( const Comparable& theElement, BinaryNode *lt, BinaryNode *rt )
32
: element{ theElement }, left{ lt }, right{ rt } { }
33
34
BinaryNode( Comparable && theElement,BinaryNode *lt, BinaryNode *rt )
35
: element{ std::move( theElement ) }, left{ lt },right{ rt } { }
36
};
37
38
BinaryNode *root;
39
40
void insert( constComparable & x, BinaryNode * & t );
41
void insert( Comparable && x, BinaryNode * & t );
42
void remove( constComparable & x, BinaryNode * & t );
43
BinaryNode * findMin( BinaryNode*t ) const;
44
BinaryNode * findMax( BinaryNode*t ) const;
45
bool contains( const Comparable & x, BinaryNode *t ) const;
46
void makeEmpty( BinaryNode * & t);
47
void printTree( BinaryNode
*
t, ostream & out ) const;
48
BinaryNode * clone( BinaryNode *t ) const;
49
};
Figure4.16 Binarysearchtreeclassskeleton
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Then just wait until the conversion from Powerpoint to PDF is complete and download the file.
online pdf converter to powerpoint; how to change pdf to powerpoint slides
RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Able to view and edit PowerPoint rapidly. Convert. Convert PowerPoint to PDF. Convert PowerPoint to HTML5. Convert PowerPoint to Tiff. Convert PowerPoint to Jpeg
convert pdf slides to powerpoint; convert pdf back to powerpoint
134
Chapter4 Trees
1
/**
2
* Returns true if x is found in the e tree.
3
*/
4
bool contains( ( const t Comparable & & x x ) const
5
{
6
return contains( x, root t );
7
}
8
9
/**
10
* Insert x x into o the tree; duplicates are e ignored.
11
*/
12
void insert( const Comparable & x x )
13
{
14
insert( x, root t );
15
}
16
17
/**
18
* Remove x x from m the tree. Nothing is done if x x is s not found.
19
*/
20
void remove( const Comparable & x x )
21
{
22
remove( x, root t );
23
}
Figure4.17 Illustration of publicmemberfunction calling privaterecursive member
function
Severalofthe
private
memberfunctionsusethetechniqueofpassingapointervariable
usingcall-by-reference.Thisallowsthe
public
memberfunctionstopassapointertothe
roottothe
private
recursivememberfunctions.Therecursivefunctionscanthenchange
thevalueoftherootsothatthe
root
pointstoanothernode.Wewilldescribethetechnique
inmoredetailwhenweexaminethecodefor
insert
.
Wecannowdescribesomeofthe
private
methods.
4.3.1 contains
Thisoperationrequiresreturning
true
ifthereisanodeintreeTthathasitemX,or
false
ifthereisnosuchnode.Thestructureofthetreemakesthissimple.IfTisempty,thenwe
canjustreturn
false
.Otherwise,iftheitemstoredatTisX,wecanreturn
true
.Otherwise,
wemakearecursivecallonasubtreeofT,eitherleftorright,dependingontherelation-
shipofXtotheitemstoredinT.ThecodeinFigure4.18isanimplementationofthis
strategy.
C# WinForms Viewer: Load, View, Convert, Annotate and Edit
to PDF; Convert PowerPoint to PDF; Convert Image to PDF; Convert Jpeg to PDF; Merge PDF Files; Split PDF Document; Remove Password from PDF; Change PDF Permission
convert pdf to powerpoint; pdf into powerpoint
How to C#: Overview of Using XDoc.PowerPoint
How to C#: Overview of Using XDoc.PowerPoint. Overview for How to Use XDoc.PowerPoint in C# .NET Programming Project. PowerPoint Conversion.
pdf picture to powerpoint; add pdf to powerpoint slide
4.3 TheSearchTreeADT—BinarySearchTrees
135
1
/**
2
* Internal method to test if an item is in a a subtree.
3
* x x is s item m to search h for.
4
* t t is s the node that roots the e subtree.
5
*/
6
bool contains( ( const t Comparable & & x, BinaryNode e *t ) ) const
7
{
8
if( t t == nullptr )
9
return false;
10
else if( ( x x < t->element )
11
return contains( x, t->left );
12
else if( ( t->element < < x )
13
return contains( x, t->right );
14
else
15
return true;
// Match
16
}
Figure4.18 containsoperationforbinarysearchtrees
Noticetheorderofthetests.Itiscrucialthatthetestforanemptytreebeperformed
first,sinceotherwise,wewouldgeneratearun timeerrorattempting toaccess adata
memberthrougha
nullptr
pointer.Theremainingtestsarearrangedwiththeleastlikely
caselast.Alsonotethatbothrecursivecallsareactuallytailrecursionsandcanbeeasily
removedwitha
while
loop.Theuseoftailrecursionisjustifiableherebecausethesim-
plicityofalgorithmicexpressioncompensatesforthedecreaseinspeed,andtheamountof
stackspaceusedisexpectedtobeonlyO(logN).
Figure4.19showsthetrivialchangesrequiredtouseafunctionobjectratherthan
requiringthattheitemsbe
Comparable
.ThismimicstheidiomsinSection1.6.4.
4.3.2 findMinandfindMax
These
private
routinesreturnapointertothenodecontainingthesmallestandlargest
elementsinthetree,respectively.Toperforma
findMin
,startattherootandgoleftaslong
asthereisaleftchild.Thestoppingpointisthesmallestelement.The
findMax
routineis
thesame,exceptthatbranchingistotherightchild.
Manyprogrammersdonotbotherusingrecursion.Wewillcodetheroutinesboth
waysbydoing
findMin
recursivelyand
findMax
nonrecursively(seeFigs.4.20and4.21).
Noticehowwecarefullyhandlethedegeneratecaseofanemptytree.Althoughthisis
alwaysimportanttodo,itisespeciallycrucialinrecursiveprograms.Alsonoticethatitis
safetochange
t
in
findMax
,sinceweareonlyworkingwithacopyofapointer.Alwaysbe
extremelycareful,however,becauseastatementsuchas
t->right = = t->right->right
will
makechanges.
C# HTML5 Viewer: Load, View, Convert, Annotate and Edit PowerPoint
Such as load and view PowerPoint without Microsoft Office software installed, convert PowerPoint to PDF file, Tiff image and HTML file, as well as add
conversion of pdf into ppt; changing pdf to powerpoint file
VB.NET PowerPoint: Read, Edit and Process PPTX File
create image on desired PowerPoint slide, merge/split PowerPoint file, change the order of How to convert PowerPoint to PDF, render PowerPoint to SVG
how to convert pdf into powerpoint slides; images from pdf to powerpoint
136
Chapter4 Trees
1
template <typename Object, typename Comparator=less<Object>>
2
class BinarySearchTree
3
{
4
public:
5
6
// Same methods, , with h Object t replacing Comparable
7
8
private:
9
10
BinaryNode *root;
11
Comparator isLessThan;
12
13
// Same methods, , with h Object t replacing Comparable
14
15
/**
16
* Internal l method d to test t if f an item is in a a subtree.
17
* x x is s item m to search for.
18
* t t is s the e node that t roots s the subtree.
19
*/
20
bool contains( const Object & & x, BinaryNode *t t ) ) const
21
{
22
if( t t == nullptr )
23
return false;
24
else if( isLessThan( ( x, , t->element ) ) )
25
return contains( ( x, , t->left );
26
else if( isLessThan( ( t->element, , x ) ) )
27
return contains( ( x, , t->right );
28
else
29
return true;
// Match
30
}
31
};
Figure4.19 Illustratesuseofafunctionobjecttoimplementbinarysearchtree
4.3.3 insert
Theinsertionroutineisconceptuallysimple.ToinsertXintotreeT,proceeddownthetree
asyouwouldwitha
contains
.IfXisfound,donothing.Otherwise,insertXatthelastspot
onthepathtraversed.Figure4.22showswhathappens.Toinsert5,wetraversethetreeas
thougha
contains
wereoccurring.Atthenodewithitem4,weneedtogoright,butthere
isnosubtree,so5isnotinthetree,andthisisthecorrectspottoplace5.
Duplicatescan behandledbykeepinganextrafieldinthenoderecordindicating
thefrequencyofoccurrence.Thisaddssomeextraspacetotheentiretreebutisbetter
thanputtingduplicatesinthetree(whichtendstomakethetreeverydeep).Ofcourse,
VB.NET PDF Password Library: add, remove, edit PDF file password
Add password to PDF. Change PDF original password. Remove password from PDF. Set PDF security level. VB: Change and Update PDF Document Password.
how to change pdf to powerpoint format; converting pdf to ppt online
C# powerpoint - Convert PowerPoint to PDF in C#.NET
C# PowerPoint - Convert PowerPoint to PDF in C#.NET. Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint to PDF Conversion Overview.
adding pdf to powerpoint slide; adding pdf to powerpoint
4.3 TheSearchTreeADT—BinarySearchTrees
137
1
/**
2
* Internal method to find the smallest t item m in a subtree t.
3
* Return n node e containing the smallest item.
4
*/
5
BinaryNode * * findMin( ( BinaryNode *t ) const
6
{
7
if( t t == nullptr )
8
return nullptr;
9
if( t->left t == = nullptr )
10
return t;
11
return findMin( t->left );
12
}
Figure4.20 RecursiveimplementationoffindMinforbinarysearchtrees
1
/**
2
* Internal method to find the largest item in a subtree t.
3
* Return n node e containing the largest item.
4
*/
5
BinaryNode * * findMax( ( BinaryNode *t ) const
6
{
7
if( t t != nullptr )
8
while( t->right t != = nullptr r )
9
t = = t->right;
10
return t;
11
}
Figure4.21 NonrecursiveimplementationoffindMaxforbinarysearchtrees
6
2
8
1
4
3
6
2
8
1
4
3
5
Figure4.22 Binarysearchtreesbeforeandafterinserting5
138
Chapter4 Trees
thisstrategydoesnotworkifthekeythatguidesthe
<
operatorisonlypartofalarger
structure.Ifthatisthecase,thenwecankeepallofthestructuresthathavethesamekey
inanauxiliarydatastructure,suchasalistoranothersearchtree.
Figure4.23showsthecodefortheinsertionroutine.Lines12and14recursivelyinsert
andattach
x
intotheappropriatesubtree.Noticethatintherecursiveroutine,theonlytime
that
t
changesiswhenanewleafiscreated.Whenthishappens,itmeansthattherecursive
routinehasbeencalledfromsomeothernode,
p
,whichistobetheleaf’sparent.Thecall
1
/**
2
* Internal l method d to insert t into a a subtree.
3
* x is the e item m to insert.
4
* t is the e node e that roots the subtree.
5
* Set t the e new w root t of f the e subtree.
6
*/
7
void insert( const Comparable & x, BinaryNode * * & & t )
8
{
9
if( t == nullptr )
10
t = = new w BinaryNode{ x, nullptr, nullptr r };
11
else if( x x < < t->element )
12
insert( x, t->left );
13
else if( t->element < < x x )
14
insert( x, t->right );
15
else
16
; // / Duplicate; do nothing
17
}
18
19
/**
20
* Internal l method d to insert t into a a subtree.
21
* x is the e item m to insert by moving.
22
* t is the e node e that roots the subtree.
23
* Set t the e new w root t of f the e subtree.
24
*/
25
void insert( Comparable && x, BinaryNode * & & t t )
26
{
27
if( t == nullptr )
28
t = = new w BinaryNode{ std::move( x ), nullptr, , nullptr };
29
else if( x x < < t->element )
30
insert( std::move( x x ), , t->left );
31
else if( t->element < < x x )
32
insert( std::move( x x ), , t->right );
33
else
34
; // / Duplicate; do nothing
35
}
Figure4.23 Insertionintoabinarysearchtree
4.3 TheSearchTreeADT—BinarySearchTrees
139
willbe
insert(x,p->left)
or
insert(x,p->right)
.Eitherway,
t
isnowareferencetoeither
p->left
or
p->right
,meaningthat
p->left
or
p->right
willbechangedtopointatthenew
node.Allinall,aslickmaneuver.
4.3.4 remove
Asiscommonwithmanydatastructures,thehardestoperationisdeletion.Oncewehave
foundthenodetobedeleted,weneedtoconsiderseveralpossibilities.
Ifthenodeisaleaf,itcanbedeletedimmediately.Ifthenodehasonechild,thenode
canbedeletedafteritsparentadjustsalinktobypassthenode(wewilldrawthelink
directionsexplicitlyforclarity).SeeFigure4.24.
Thecomplicatedcasedealswithanodewithtwochildren.Thegeneralstrategyisto
replacethedataofthisnodewiththesmallestdataoftherightsubtree(whichiseasily
found)andrecursivelydeletethatnode(whichisnowempty).Becausethesmallestnode
intherightsubtreecannothavealeftchild,thesecond
remove
isaneasyone.Figure4.25
showsaninitialtreeandtheresultofadeletion.Thenodetobedeletedistheleftchildof
theroot;thekeyvalueis2.Itisreplacedwiththesmallestdatainitsrightsubtree(3),and
thenthatnodeisdeletedasbefore.
ThecodeinFigure4.26performsdeletion.Itisinefficientbecauseitmakestwopasses
downthetreetofindanddeletethesmallestnodeintherightsubtreewhenthisisappro-
priate.Itiseasytoremovethisinefficiencybywritingaspecial
removeMin
method,andwe
haveleftitinonlyforsimplicity.
Ifthenumberofdeletionsisexpectedtobesmall,thenapopularstrategytouseis
lazydeletion:Whenanelementistobedeleted,itisleftinthetreeandmerelymarked
asbeingdeleted.Thisisespeciallypopularifduplicateitemsarepresent,becausethenthe
datamemberthatkeepscountofthefrequencyofappearancecanbedecremented.Ifthe
numberofrealnodesinthetreeisthesameasthenumberof“deleted”nodes,thenthe
depthofthetreeisonlyexpectedtogoupbyasmallconstant(why?),sothereisavery
smalltimepenaltyassociatedwithlazydeletion.Also,ifadeleteditemisreinserted,the
overheadofallocatinganewcellisavoided.
6
2
8
1
4
3
6
2
8
1
4
3
Figure4.24 Deletionofanode(4)withonechild,beforeandafter
140
Chapter4 Trees
6
2
8
1
5
3
4
6
3
8
1
5
3
4
Figure4.25 Deletionofanode(2)withtwochildren,beforeandafter
1
/**
2
* Internal l method d to remove e from a a subtree.
3
* x is the e item m to remove.
4
* t is the e node e that roots the subtree.
5
* Set t the e new w root t of f the e subtree.
6
*/
7
void remove( const Comparable & x, BinaryNode * * & & t )
8
{
9
if( t == nullptr )
10
return;
// Item m not t found; ; do o nothing
11
if( x < < t->element )
12
remove( x, t->left );
13
else if( t->element < < x x )
14
remove( x, t->right );
15
else if( t->left != nullptr && t->right != nullptr ) // Two o children
16
{
17
t->element = findMin( t->right )->element;
18
remove( t->element, t->right t );
19
}
20
else
21
{
22
BinaryNode *oldNode = t;
23
t = = ( ( t->left != nullptr ) ? ? t->left : : t->right;
24
delete oldNode;
25
}
26
}
Figure4.26 Deletionroutineforbinarysearchtrees
4.3 TheSearchTreeADT—BinarySearchTrees
141
4.3.5 DestructorandCopyConstructor
Asusual,thedestructorcalls
makeEmpty
.Thepublic
makeEmpty
(notshown)simplycallsthe
privaterecursiveversion.AsshowninFigure4.27,afterrecursivelyprocessing
t
’schildren,
acallto
delete
ismadefor
t
.Thusallnodesarerecursivelyreclaimed.Noticethatatthe
end,
t
,and thus
root
,ischangedtopointat
nullptr
.Thecopyconstructor,shown in
Figure4.28,followstheusualprocedure,firstinitializing
root
to
nullptr
andthenmaking
acopyof
rhs
.Weuseaveryslickrecursivefunctionnamed
clone
todoallthedirtywork.
4.3.6 Average-CaseAnalysis
Intuitively,weexpectthatalloftheoperationsdescribedinthissection,except
makeEmpty
andcopying,shouldtakeO(logN)time,becauseinconstanttimewedescendalevelinthe
tree,thusoperatingonatreethatisnowroughlyhalfaslarge.Indeed,therunningtimeof
alltheoperations(except
makeEmpty
andcopying)isO(d),wheredisthedepthofthenode
containingtheaccesseditem(inthecaseof
remove
,thismaybethereplacementnodein
thetwo-childcase).
WeproveinthissectionthattheaveragedepthoverallnodesinatreeisO(logN)on
theassumptionthatallinsertionsequencesareequallylikely.
Thesumofthedepthsofallnodesinatreeisknownastheinternalpathlength.
Wewillnowcalculatetheaverageinternalpathlengthofabinarysearchtree,wherethe
averageistakenoverallpossibleinsertionsequencesintobinarysearchtrees.
1
/**
2
* Destructor for the tree
3
*/
4
~BinarySearchTree( )
5
{
6
makeEmpty( );
7
}
8
/**
9
* Internal method to make subtree e empty.
10
*/
11
void makeEmpty( BinaryNode e * * & & t )
12
{
13
if( t t != nullptr )
14
{
15
makeEmpty( t->left );
16
makeEmpty( t->right );
17
delete t;
18
}
19
t = nullptr;
20
}
Figure4.27 DestructorandrecursivemakeEmptymemberfunction
Documents you may be interested
Documents you may be interested