602
Chapter12 AdvancedDataStructuresandImplementation
12.6 PairingHeaps
Thelastdatastructureweexamineisthepairingheap.Theanalysisofthepairingheap
isstillopen,butwhen
decreaseKey
operationsareneeded,itseemstooutperformother
heapstructures.Themostlikelyreasonforitsefficiencyisitssimplicity.Thepairingheap
isrepresentedasaheap-orderedtree.Figure12.42showsasamplepairingheap.
Theactualpairingheapimplementationusesaleftchild,rightsiblingrepresentationas
discussedinChapter4.The
decreaseKey
operation,aswewillsee,requiresthateachnode
containanadditionallink.Anodethatisaleftmostchildcontainsalinktoitsparent;
otherwisethenodeisarightsiblingandcontainsalinktoitsleftsibling.We’llrefertothis
datamemberas
prev
.Theclassskeletonandpairingheapnodedeclarationareomittedfor
brevity;theyarecompletelystraightforward.Figure12.43showstheactualrepresentation
ofthepairingheapinFigure12.42.
Webeginbysketchingthebasicoperations.Tomergetwopairingheaps,wemake
theheapwiththelargerrootaleftchildoftheheapwiththesmallerroot.Insertionis,
of course,aspecialcaseofmerging.Toperforma
decreaseKey
,welowerthevaluein
therequested node.Becausewearenotmaintaining parentpointersforallnodes,we
2
6
3
4
5
9
7
19
17
12
14
15
11
8
13
10
16
18
Figure12.42 Samplepairingheap:abstractrepresentation
2
7
9
5
4
8
3
6
10
13
11
15
16
18  
14
12
17
19
Figure12.43 Actualrepresentationofpreviouspairingheap
Adding pdf to powerpoint - 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
changing pdf to powerpoint; copying image from pdf to powerpoint
Adding pdf to powerpoint - 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 powerpoint; how to convert pdf file to powerpoint presentation
12.6 PairingHeaps
603
F
S  
A
B
C
F  
A
B
S  
C
+
S  
B
A
 
C
F   S
  S
Figure12.44 compareAndLinkmergestwosubheaps
don’tknowifthisviolatestheheaporder.Thuswecuttheadjustednodefromitspar-
entandcompletethe
decreaseKey
by merging thetwoheaps that result.Toperforma
deleteMin
,weremovetheroot,creatingacollectionofheaps.Iftherearecchildrenof
theroot,then c−1 callstothemergeprocedurewillreassembletheheap.Themost
importantdetailisthemethodusedtoperformthemergeandhowthec−1mergesare
applied.
Figure12.44showshowtwosubheapsarecombined.Theprocedureisgeneralizedto
allowthesecondsubheaptohavesiblings.Aswementionedearlier,thesubheapwiththe
largerrootismadealeftmostchildoftheothersubheap.Thecodeisstraightforwardand
showninFigure12.45.Noticethatwehaveseveralinstancesinwhichapointeristested
against
nullptr
beforeassigningits
prev
datamember;thissuggeststhatperhapsitwould
beusefultohavea
nullNode
sentinel,whichwascustomaryinthischapter’ssearchtree
implementations.
The
insert
and
decreaseKey
operations are, then, simple e implementations of f the
abstractdescription.
decreaseKey
requiresapositionobject,whichisjusta
PairNode
*
.Since
thisisdetermined(irrevocably)whenanitemisfirstinserted,
insert
returnsthepointer
toa
PairNode
itallocatesbacktothecaller.ThecodeisshowninFigure12.46.Ourroutine
for
decreaseKey
throwsanexceptionifthenewvalueisnotsmallerthantheold;otherwise,
theresultingstructuremightnotobeyheaporder.Thebasic
deleteMin
procedurefollows
directlyfromtheabstractdescriptionandisshowninFigure12.47.
Thedevil,ofcourse,isinthedetails:Howis
combineSiblings
implemented?Several
variantshavebeenproposed,butnonehasbeenshowntoprovidethesameamortized
boundsastheFibonacciheap.Ithasrecentlybeenshownthatalmostalloftheproposed
methodsareinfacttheoreticallylessefficientthantheFibonacciheap.Evenso,themethod
codedinFigure12.48onpage607alwaysseemstoperformaswellasorbetterthanother
heapstructures,includingthebinaryheap,forthetypicalgraphtheoryusesthatinvolvea
hostof
decreaseKey
operations.
This method, known as two-pass merging,is thesimplest and most practicalof
themanyvariantsthathavebeensuggested.Wefirstscanlefttoright,mergingpairsof
VB.NET PDF Library SDK to view, edit, convert, process PDF file
Capable of adding PDF file navigation features to your VB.NET program. Capable of adding PDF file navigation features to your VB.NET program. How To Tutorials.
how to convert pdf slides to powerpoint; image from pdf to powerpoint
VB.NET PDF Page Insert Library: insert pages into PDF file in vb.
Support adding PDF page number. Offer PDF page break inserting function. DLLs for Adding Page into PDF Document in VB.NET Class. Add necessary references:
how to change pdf to powerpoint format; how to convert pdf to ppt using
604
Chapter12 AdvancedDataStructuresandImplementation
1
/**
2
* Internal l method d that is the basic c operation n to maintain n order.
3
* Links first t and d second d together r to satisfy heap order.
4
* first is s root t of tree 1, which h may y not t be nullptr.
5
* first->nextSibling MUST be nullptr on entry.
6
* second is root t of f tree e 2, which h may be e nullptr.
7
* first becomes the result of the tree merge.
8
*/
9
void compareAndLink( PairNode * & & first, , PairNode *second )
10
{
11
if( second d == nullptr )
12
return;
13
14
if( second->element < < first->element t )
15
{
16
// Attach h first t as leftmost child d of second
17
second->prev = = first->prev;
18
first->prev = second;
19
first->nextSibling = = second->leftChild;
20
if( first->nextSibling != nullptr )
21
first->nextSibling->prev = = first;
22
second->leftChild = = first;
23
first = second;
24
}
25
else
26
{
27
// Attach h second d as leftmost t child d of first
28
second->prev = = first;
29
first->nextSibling = = second->nextSibling;
30
if( first->nextSibling != nullptr )
31
first->nextSibling->prev = = first;
32
second->nextSibling = first->leftChild;
33
if( second->nextSibling g != nullptr )
34
second->nextSibling->prev = second;
35
first->leftChild = second;
36
}
37
}
Figure12.45 Pairingheaps:routinetomergetwosubheaps
children.
4
Afterthefirstscan,wehavehalfasmanytreestomerge.Asecondscanisthen
performed,righttoleft.Ateachstepwemergetherightmosttreeremainingfromthefirst
4
Wemustbecarefulifthereisanoddnumberofchildren.Whenthathappens,wemergethelastchild
withtheresultoftherightmostmergetocompletethefirstscan.
C# PDF Library SDK to view, edit, convert, process PDF file for C#
Capable of adding PDF file navigation features to your C# program. Perform annotation capabilities to mark, draw, and visualize objects on PDF document page.
picture from pdf to powerpoint; convert pdf to powerpoint online
C# PDF insert image Library: insert images into PDF in C#.net, ASP
application? To help you solve this technical problem, we provide this C#.NET PDF image adding control, XDoc.PDF for .NET. Similar
change pdf to powerpoint online; convert pdf back to powerpoint
1
struct PairNode;
2
typedef PairNode * Position;
3
4
/**
5
* Insert t item m x into the priority y queue, , maintaining g heap order.
6
* Return n the e Position (a pointer to the node) containing the e new w item.
7
*/
8
Position insert( const Comparable & x )
9
{
10
PairNode *newNode e = = new w PairNode{ x x };
11
12
if( root t == nullptr )
13
root = = newNode;
14
else
15
compareAndLink( root, , newNode );
16
return newNode;
17
}
18
19
/**
20
* Change e the e value of the item m stored d in the e pairing heap.
21
* Throw invalid_argument t if newVal l is larger r than
22
*
currently stored d value.
23
* p p is s a a Position n returned by insert.
24
* newVal l is the e new w value, , which must be smaller
25
*
than the currently stored d value.
26
*/
27
void decreaseKey( Position n p, const Comparable & newVal )
28
{
29
if( p->element < < newVal l )
30
throw invalid_argument{ { "newVal too o large" " };
31
p->element = newVal;
32
if( p p != root )
33
{
34
if( p->nextSibling != nullptr )
35
p->nextSibling->prev = = p->prev;
36
if( p->prev->leftChild == p )
37
p->prev->leftChild = p->nextSibling;
38
else
39
p->prev->nextSibling = = p->nextSibling;
40
41
p->nextSibling = nullptr;
42
compareAndLink( root, , p p );
43
}
44
}
Figure12.46 Pairingheaps:insertanddecreaseKey
C# PDF Page Insert Library: insert pages into PDF file in C#.net
C# programmers are capable of adding and inserting (empty) PDF page or pages from various file formats, such as PDF, Tiff, Word, Excel, PowerPoint, Bmp, Jpeg
convert pdf into powerpoint online; and paste pdf to powerpoint
C# PDF insert text Library: insert text into PDF content in C#.net
Supports adding text to PDF in preview without adobe reader installed in ASP.NET. Powerful .NET PDF edit control allows modify existing scanned PDF text.
converting pdf to ppt online; conversion of pdf to ppt online
606
Chapter12 AdvancedDataStructuresandImplementation
1
void deleteMin{ }
2
{
3
if( isEmpty( ) )
4
throw UnderflowException{ { };
5
6
PairNode *oldRoot = root;
7
8
if( root->leftChild == nullptr )
9
root = = nullptr;
10
else
11
root = = combineSiblings( ( root->leftChild d );
12
13
delete oldRoot;
14
}
Figure12.47 PairingheapdeleteMin
scanwiththecurrentmergedresult.Asanexample,ifwehaveeightchildren,c
1
through
c
8
,thefirstscanperformsthemergesc
1
andc
2
,c
3
andc
4
,c
5
andc
6
,andc
7
andc
8
.Asa
result,weobtaind
1
,d
2
,d
3
,andd
4
.Weperformthesecondpassbymergingd
3
andd
4
;
d
2
isthenmergedwiththatresult,andthend
1
ismergedwiththeresultoftheprevious
merge.
Ourimplementationrequiresanarraytostorethesubtrees.Intheworstcase,N−1
itemscouldbechildrenoftheroot,butdeclaringa(non-
static
)arrayofsizeNinsideof
combineSiblings
wouldgiveanO(N)algorithm.Soweuseasingleexpandingarrayinstead.
Becauseitis
static
,itisreusedineachcall,withouttheoverheadofreinitialization.
Othermergingstrategiesarediscussedintheexercises.Theonlysimplemergingstrat-
egythatiseasilyseentobepoorisaleft-to-rightsingle-passmerge(Exercise12.29).The
pairingheapisagoodexampleof“simpleisbetter”andseemstobethemethodofchoice
forseriousapplicationsrequiringthe
decreaseKey
or
merge
operation.
Summary
In this s chapter, we’ve seen n several efficient variations of f the binary search h tree. The
top-downsplaytreeprovidesO(logN)amortizedperformance,thetreapgivesO(logN)
randomizedperformance,andthered-blacktreegivesO(logN)worst-caseperformance
forthebasicoperations.Thetrade-offsbetweenthevariousstructuresinvolvecodecom-
plexity,easeofdeletion,anddifferingsearchingandinsertioncosts.Itisdifficulttosaythat
anyonestructureisaclearwinner.Recurringthemesincludetreerotationsandtheuseof
sentinelnodestoeliminatemanyoftheannoyingtestsfor
nullptr
thatwouldotherwisebe
necessary.Thesuffixtreeandarrayareapowerfuldatastructurethatallowsquickrepeated
searchingforafixedtext.Thek-dtreeprovidesapracticalmethodforperformingrange
searches,eventhoughthetheoreticalboundsarenotoptimal.
Finally,wedescribedandcodedthepairingheap,whichseemstobethemostprac-
ticalmergeablepriorityqueue,especiallywhen
decreaseKey
operationsarerequired,even
thoughitistheoreticallylessefficientthantheFibonacciheap.
VB.NET PDF insert text library: insert text into PDF content in vb
VB.NET PDF - Insert Text to PDF Document in VB.NET. Providing Demo Code for Adding and Inserting Text to PDF File Page in VB.NET Program.
convert pdf to powerpoint slides; convert pdf to powerpoint presentation
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
add, insert or delete any certain PowerPoint slide without guide on C#.NET PPT image adding library. powerful & profession imaging controls, PDF document, tiff
pdf to powerpoint converter online; pdf page to powerpoint
1
/**
2
* Internal l method d that implements two-pass merging.
3
* firstSibling the e root t of f the e conglomerate e and d is assumed not t nullptr.
4
*/
5
PairNode * * combineSiblings( ( PairNode e *firstSibling )
6
{
7
if( firstSibling->nextSibling g == = nullptr r )
8
return firstSibling;
9
10
// Allocate the e array
11
static vector<PairNode *> treeArray( 5 5 );
12
13
// Store the e subtrees s in an array
14
int numSiblings = 0;
15
for( ; firstSibling g != = nullptr; ++numSiblings )
16
{
17
if( numSiblings s == = treeArray.size( ( ) ) )
18
treeArray.resize( numSiblings * 2 2 );
19
treeArray[ numSiblings ] = = firstSibling;
20
firstSibling->prev->nextSibling = = nullptr; ; // / break links
21
firstSibling = = firstSibling->nextSibling;
22
}
23
if( numSiblings == treeArray.size( ) )
24
treeArray.resize( numSiblings s + + 1 1 );
25
treeArray[ numSiblings ] ] = = nullptr;
26
27
// Combine subtrees two o at a a time, , going g left t to o right
28
int i i = = 0;
29
for( ; i i + + 1 < numSiblings; ; i i += 2 )
30
compareAndLink( treeArray[ i i ], , treeArray[ i i + 1 ] ] );
31
32
int j j = = i - - 2;
33
34
// j j has s the e result t of last compareAndLink.
35
// If an odd d number r of trees, get the e last one.
36
if( j j == numSiblings s - 3 3 )
37
compareAndLink( treeArray[ j j ], , treeArray[ j j + 2 ] ] );
38
39
// Now go right t to o left, merging last t tree with
40
// next t to o last. The e result t becomes the e new w last.
41
for( ; j j >= 2; ; j j -= 2 2 )
42
compareAndLink( treeArray[ j j - 2 ], treeArray[ j ] ] );
43
return treeArray[ 0 0 ];
44
}
Figure12.48 Pairingheaps:two-passmerging
C# PDF Annotate Library: Draw, edit PDF annotation, markups in C#.
Provide users with examples for adding text box to PDF and edit font size and color in text box field in C#.NET program. C#.NET: Draw Markups on PDF File.
pdf to powerpoint; copying image from pdf to powerpoint
VB.NET PDF File & Page Process Library SDK for vb.net, ASP.NET
page modifying page, you will find detailed guidance on creating, loading, merge and splitting PDF pages and Files, adding a page into PDF document, deleting
drag and drop pdf into powerpoint; conversion of pdf to ppt online
608
Chapter12 AdvancedDataStructuresandImplementation
Exercises
12.1
Provethattheamortizedcostofatop-downsplayisO(logN).

12.2
Provethatthereexistaccesssequencesthatrequire2logNrotationsperaccessfor
bottom-upsplaying.Showthatasimilarresultholdsfortop-downsplaying.
12.3
Modifythesplaytreetosupportqueriesforthekthsmallestitem.
12.4
Compare,empirically,thesimplifiedtop-downsplaywiththeoriginallydescribed
top-downsplay.
12.5
Writethedeletionprocedureforred-blacktrees.
12.6
Provethattheheightofared-blacktreeisatmost2logN,andthatthisbound
cannotbesubstantiallylowered.
12.7
ShowthateveryAVLtreecanbecoloredasared-blacktree.Areallred-black
treesAVL?
12.8
DrawasuffixtreeandshowthesuffixarrayandLCParrayforthefollowinginput
strings:
a. ABCABCABC
b.MISSISSIPPI
12.9
Oncethesuffixarrayisconstructed,theshortroutineshowninFigure12.49can
beinvokedfromFigure12.32tocreatethelongestcommonprefixarray.
a. Inthecode,whatdoes
rank[i]
represent?
b.Supposethat
LCP[rank[i]]
=h.Showthat
LCP[rank[i+1]]
h−1.
c. ShowthatthealgorithminFigure12.49correctlycomputestheLCParray.
d.ProvethatthealgorithminFigure12.49runsinlineartime.
12.10 Supposethatinthelinear-timesuffixarray construction algorithm,instead of
constructingthreegroups,weconstructsevengroups,usingfork= 0,1,2,3,
4,5,6
S
k
=<S[7i+k]S[7i+k+1]S[7i+k+2]...S[7i+k+6]fori=0,1,2,...>
a. ShowthatwitharecursivecalltoS
3
S
5
S
6
,wehaveenoughinformationtosort
theotherfourgroupsS
0
,S
1
,S
2
,andS
4
.
b.Showthatthispartitioningleadstoalinear-timealgorithm.
12.11 Implementtheinsertionroutinefortreapsnonrecursivelybymaintainingastack.
Isitworththeeffort?
12.12 Wecanmaketreapsself-adjustingbyusingthenumberofaccessesasapriority
andperformingrotationsasneededaftereachaccess.Comparethismethodwith
therandomizedstrategy.Alternatively,generatearandomnumbereachtimean
itemXisaccessed.IfthisnumberissmallerthanX’scurrentpriority,useitasX’s
newpriority(performingtheappropriaterotation).
12.13
Showthatiftheitemsaresorted,thenatreapcanbeconstructedinlineartime,
eveniftheprioritiesarenotsorted.
12.14 Implementsomeofthetreestructureswithoutusingthe
nullNode
sentinel.How
muchcodingeffortissavedbyusingthesentinel?
Exercises
609
1
/*
2
* Create e the e LCP array y from m the suffix array
3
* s is the input array y populated d from 0..N-1, , with h available pos N
4
* sa is an already-computed suffix array 0..N-1
5
* LCP is s the e resulting g LCP P array 0..N-1
6
*/
7
void makeLCPArray( vector<int> > & & s, const vector<int> > & & sa, vector<int> & LCP )
8
{
9
int N N = = sa.size( );
10
vector<int> rank( N N );
11
12
s[ N ] = -1;
13
for( int i = = 0; ; i < < N; ; ++i i )
14
rank[ sa[ i ] ] ] = = i;
15
16
int h h = = 0;
17
for( int i = = 0; ; i < < N; ; ++i i )
18
if( rank[ i ] > > 0 0 )
19
{
20
int j = sa[ [ rank[ [ i ] - 1 1 ];
21
22
while( s[ i i + + h ] == s[ j j + + h ] )
23
++h;
24
25
LCP[ rank[ [ i ] ] = = h;
26
if( h > 0 )
27
--h;
28
}
29
}
Figure12.49 LCParrayconstructionfromsuffixarray
12.15 Supposewestore,foreachnode,thenumberof
nullptr
linksinitssubtree;call
thisthenode’sweight.Adoptthefollowingstrategy:Iftheleftandrightsubtrees
haveweights thatarenotwithinafactorof2ofeach other,then completely
rebuildthesubtreerootedatthenode.Showthefollowing:
a. WecanrebuildanodeinO(S),whereSistheweightofthenode.
b.ThealgorithmhasamortizedcostofO(logN)perinsertion.
c. Wecanrebuildanodeinak-dtreeinO(SlogS)time,whereSistheweightof
thenode.
d.Wecanapplythealgorithmtok-dtrees,atacostofO(log
2
N)perinsertion.
12.16 Supposewecall
rotateWithLeftChild
onanarbitrary2-dtree.Explainindetailall
thereasonsthattheresultisnolongerausable2-dtree.
12.17 Implementtheinsertionandrangesearchforthek-dtree.Donotuserecursion.
610
Chapter12 AdvancedDataStructuresandImplementation
12.18 Determinethetimeforpartialmatchqueryforvaluesofpcorrespondingtok=3,
4,and5.
12.19 Foraperfectlybalancedk-dtree,derivetheworst-caserunningtimeofarange
querythatisquotedinthetext(seep.600).
12.20 The2-dheapisadatastructurethatallowseachitemtohavetwoindividual
keys.
deleteMin
canbeperformedwithrespecttoeitherofthesekeys.The2-d
heapisacompletebinarytreewiththefollowingorderproperty:ForanynodeX
atevendepth,theitemstoredatXhasthesmallestkey#1initssubtree,while
foranynodeXatodddepth,theitemstoredatXhasthesmallestkey#2inits
subtree.
a. Drawapossible2-dheapfortheitems(1,10),(2,9),(3,8),(4,7),(5,6).
b.Howdowefindtheitemwithminimumkey#1?
c. Howdowefindtheitemwithminimumkey#2?
d.Giveanalgorithmtoinsertanewitemintothe2-dheap.
e. Giveanalgorithmtoperform
deleteMin
withrespecttoeitherkey.
f. Giveanalgorithmtoperform
buildHeap
inlineartime.
12.21 Generalizetheprecedingexercisetoobtainak-dheap,inwhicheachitemcan
havekindividualkeys.Youshouldbeabletoobtainthefollowingbounds:
insert
inO(logN),
deleteMin
inO(2
k
logN),and
buildHeap
inO(kN).
12.22 Showthatthek-dheapcanbeusedtoimplementadouble-endedpriorityqueue.
12.23 Abstractly,generalizethek-dheapsothatonlylevelsthatbranchonkey#1have
twochildren(allothershaveone).
a. Doweneedpointers?
b.Clearly,thebasicalgorithmsstillwork;whatarethenewtimebounds?
12.24 Usea k-d treeto implement
deleteMin
.What would you expect theaverage
runningtimetobeforarandomtree?
12.25 Useak-dheaptoimplementadouble-endedqueuethatalsosupports
deleteMin
.
12.26 Implementthepairingheapwitha
nullNode
sentinel.

12.27 ShowthattheamortizedcostofeachoperationisO(logN)forthepairingheap
algorithminthetext.
12.28 Analternativemethodfor
combineSiblings
istoplaceallofthesiblingsonaqueue,
andrepeatedly
dequeue
andmergethefirsttwoitemsonthequeue,placingthe
resultattheendofthequeue.Implementthisvariation.
12.29 Showthatusingastackinsteadofaqueueinthepreviousexerciseisbadby
givingasequencethatleadsto(N)costperoperation.Thisistheleft-to-right
single-passmerge.
12.30 Without
decreaseKey
,wecanremoveparentlinks.Howcompetitiveistheresult
withtheskewheap?
12.31 Assumethateachofthefollowingisrepresentedasatreewithchildandparent
pointers.Explainhowtoimplementa
decreaseKey
operation.
a. Binaryheap
b.Splaytree
Exercises
611
p
1
p
p
2
p
2
p
2
p
3
p
3
p
1
p
3
p
1
p
5
p
4
p
4
p
1
p
1
2
Figure12.50 Theplanepartitionedbya2-dtreeaftertheinsertionofp1= (53,14),
p2=(27,28),p3=(30,11),p4=(67,51),p5=(70,3)
12.32 Whenviewedgraphically,eachnodeina2-dtreepartitionstheplaneintoregions.
Forinstance,Figure12.50shows thefirstfiveinsertionsintothe2-dtree in
Figure12.39.Thefirst insertion,ofp1,splitstheplaneintoaleft partand a
rightpart.Thesecondinsertion,ofp2,splitstheleftpartintoatoppartanda
bottompart,andsoon.
a. ForagivensetofNitems,doestheorderofinsertionaffectthefinalpartition?
b.Iftwodifferentinsertionsequencesresultinthesametree,isthesamepartition
produced?
c. GiveaformulaforthenumberofregionsthatresultfromthepartitionafterN
insertions.
d.Showthefinalpartitionforthe2-dtreeinFigure12.39.
12.33 Analternativetothe2-dtreeisthequadtree.Figure12.51showshowaplaneis
partitionedbyaquadtree.Initially,wehavearegion(whichisoftenasquare,but
neednotbe).Eachregionmaystoreonepoint.Ifasecondpointisinsertedintoa
region,thentheregionissplitintofourequal-sizedquadrants(northeast,south-
east,southwest,andnorthwest).Ifthisplacesthepointsindifferentquadrants(as
whenp2isinserted),wearedone;otherwise,wecontinuesplittingrecursively(as
isdonewhenp5isinserted).
a. ForagivensetofNitems,doestheorderofinsertionaffectthefinalpartition?
b.Show thefinalpartition if f thesame elementsthat werein the2-d tree in
Figure12.39areinsertedintothequadtree.
12.34 Atreedatastructurecan storethequad tree.Wemaintain theboundsofthe
originalregion.Thetreerootrepresentstheoriginalregion.Eachnodeiseither
aleafthatstoresaninserteditem,orhasexactlyfourchildren,representingfour
quadrants.Toperformasearch,webeginattherootandrepeatedlybranchtoan
appropriatequadrantuntilaleaf(or
nullptr
)isreached.
p1
p2
p2
p2
p2
p3
pp1
p3
p4
p1
p1
p1
p5
p4
Figure12.51 Theplanepartitionedbyaquadtreeaftertheinsertionofp1= (53,14),
p2=(27,28),p3=(30,11),p4=(67,51),p5=(70,3)
Documents you may be interested
Documents you may be interested