; TeX output 1996.04.29:0853w1\XCDtqGcmr17CDrauNwingBT_reesNicelywithT)vEzXy?;!",ff cmsy10#􍍍U*9XQ ff cmr12Anne/BrdDuggemann-Klein= !", cmsy10y3.Derick/W4odCod=z&a`April/29,199699U","V 3 cmbx10AbstractMƍ<@'K`y 3 cmr10Vearious!algorithmsha!ve!bMeenproposedforthedicultproblemofpro- +ducingRaestheticallypleasingdra!wingsoftrees,"see[15 4,17]butimplemen-+tationsonlyexistas\spMecialpurposesoft!ware",fdesignedforspecialen!vi-+ronmen!ts.OoTherefore,ոmanyAusersresorttothedra!wingfacilitiesavdDailable+on:mostpMersonalcomputers,P0butthe guresobtainedinthisw!ay:stilllook+\hand-dra!wn";their~qualityisinferiortothequalityofthesurrounding+textfthatcanbMerealizedb!ytoda!y'shighqualitytextproMcessingsystems.<@In^,thispapMerw!epresentanentirelynewsolutionthatintegratesatree+dra!wing algorithmintooneofthebMesttextprocessingsystemsa!vdDailable.+MoreVpreciselye,fw!epresentaT,[wEB XmacropackdDageTereeT,[wEB XthatproMducesa+dra!wingofatreefromapurelylogicaldescription.aOurapproachhasthree+advdDan!tages.DFirst,labMelsfornodescanbehandledinareasonablew!aye.DOn+the[onehand,*thetreedra!wingalgorithmcancomputethewidthsofthe+labMelsandtak!ethemintoaccountforthepMositioningofthenodes;onthe+otherchand,allthetextualpartsofthedoMcumen!tcanbetreateduniformlye.+Second,uTereeT,[wEB XizcanbMetriviallyportedtoan!ysiterunningT,[wEB X.ɎFinallye,+moMdularit!y}"inthedescriptionofatreeandT,[wEB X'smacrocapabilitiesallow+forflibrariesofsubtreesandtreeclasses.<@Inaddition,w!ehaveimplementedanoptionthatproMducesdrawings+whic!hrmakethe*': 3 cmti10structurpeofthetreesmoreobvioustothehumaneye,+ev!enfthoughtheymaynotbMeasaestheticallypleasing.t* TDff g^ O!cmsy7K`y cmr10ThisworkwassuppGortedbyaNaturalSciencesandEngineeringResearchCouncilof Canada:VGrantA-5692andaDeutscheF*orschungsgemeinschaftGrantSto167/1-1.sItwasstartedduringUUthe rstauthor'sstaywiththeDataStructuringGroupinW*aterloGo.  X^yInstitut ]fGurInformatik, f]UniversitatF*reiburg,Rheinstr.10{12,7800F*reiburg,W*estUUGermany X^zDataStructuringGroup,DepartmentofComputerScience,UniversityofW*aterloGo,Wa-terloGo,UUOntario,N2L3G1,Canada|V0XQ cmr121*w1\t*ANG cmbx12A1+Aestheticalzcriteriafordrauwingtreesb#t*Oneofthemostcommonlyuseddatastructuresincomputerscienceisthetree.t*Asv+manrypSeopleareusingtreesintheirresearchorjustasillustrationtoSols,t*theyfareusuallystrugglingwiththeproblemof3@ cmti12drffawingtrees.WVeareconcernedt*primarilyѶwithorderedtreesinthesenseof[9], espSeciallybinaryandunary-binaryt*trees.)A:binary:treeisa nitesetofnoSdeswhicrheitherisemptyV,Oorconsistsoft*a roSotandtrwo disjointbinarytreescalledtheleftandrightsubtreesoftheroSot.t*Aunary-binarytreeisa nitesetofnoSdeswhicrheitherisemptyV,orconsistsofat*roSot/andtrwo/disjointunary-binarytrees,orconsistsofaroSotandonenonemptyt*unary-binary'tree.AnextendedbinarytreeisabinarytreeinwhicrheachnoSdet*haseithertrwononemptysubtreesortwoemptysubtrees. FVor&,thesetreestherearesomebasicagreemenrtsonhowtheyshouldbSedrawn,t*re ectingthetop-dorwnandleft-rightorderingofnoSdesinatree;Zsee[15 ]and[17].츍В1.+TVrees*impSoseadistanceonthenodes;ũnonodeshouldbeclosertotheroot+thananryofitsancestors.[.В2.+NoSdesҞofatreeatthesameheighrtshouldlieonastraightline, andthe+straighrtlinesde ningthelevelsshouldbSeparallel.В3.+TheurelativreorderofnoSdesonanylevelshouldbSethesameasinthelevel+ordertrarversalofthetree.츍 Theseaxiomsguaranrteethattreesaredrawnasplanargraphs:8edgesdonott*inrtersect exceptatnoSdes.]TwofurtheraxiomsimprovetheaestheticalappSearancet*oftrees:В4.+Infaunary-binarytree,eacrhleftchildshouldbSepositionedtotheleftof+its)parenrt,"Jeachrightchildtotherightofitsparent,"Jandeachunarychild+shouldbSepositionedbelorwitsparent.[.В5.+AparenrtshouldbSecenteredoveritschildren. AnadditionalaxiomdealswiththeproblemoftreedrarwingsbSecomingtoot*wideandthereforeexceedingthephrysicallimitoftheoutputmedium:В6.+TVreedrarwingsshouldoSccupyaslittlewidthaspSossiblewithoutviolating+theotheraxioms. In[17 ],uWVetherellandShannoninrtroSducetwoalgorithmsfortreedrawings,t*the)k rstofwhicrhful llsaxioms1{5,9andthesecond1{6.(However,9asReingoldt*andȫTilfordin[15 ]pSoinrtout,@,thereisalackofsymmetryinthealgorithmst*ofWVetherellandShannonwhicrhmayleadtounpleasantresults. eTherefore,t*ReingoldandTilfordinrtroSduceanewstructuredaxiom:|V2 ڠw1\В7.+AJ.subtreeJWofagivrentreeshouldbSedrawnthesamewayregardlessofwhere+itoSccursinthegivrentree. Axiom.7allorwsthesametreetobSedrawndi erentlywhenitoSccursasat*subtreeindi erenrttrees.6ReingoldandTilfordgiveanalgorithmwhichful llst*axioms* 1{5and7.AlthoughthisalgorithmdoSesn'tful llaxiom6,Ptheaestheticalt*improrvementsParewrellworththeadditionalspace.Figure1illustratesthebSene tst*of9axiom7,andFigure2shorwsthatthealgorithmofReingoldandTilfordviolatest*axiom6.(Vt*A2+ThezalgorithmofReingoldandTilfordb#t*The6algorithmofReingoldandTilford(hereaftercalled\theRVTalgorithm")t*takres8amoSdularapproachtothepSositioningofnodes:ԷTherelativrepositionsoft*theknoSdesinasubtreearecalculatedindependenrtlyfromtherestofthetree.vAftert*the!relativrepSositionsoftwosubtreeshavebSeencalculated,theycanbejoinedast*siblings_inalargertreebryplacingthemasclosetogetheraspSossibleandcenteringt*theAparenrtnoSdeaborveAthem.*hIncidentallyV,themoSdularityprincipleisthereasont*thatthealgorithmfailstoful llaxiom6;Lsee[16 ].Twrosiblingsubtreesareplacedt*asclosetogetheraspSossible, 2duringapostordertrarversal, 2asfollows.,Ateacht*noSde5Tq,imaginethatitstrwo5subtreesharve5beendrarwnandcutoutofpapert*alongvtheirconrtours./Then,startingwiththetwosubtreessupSerimposedvattheirt*roSots,9morve themapartunrtilaminimalagreedupondistancebetrween thetreest*isobtainedateacrhlevel..ThiscanbSedonegradually:wInitiallyV,theirrootsaret*separated+ubrysomeagreedupSonminimumdistance.$Then,Qatthenextlowerlevel,t*theykarepushedapartunrtiltheminimumseparationisestablishedthere.)Thist*proScessrisconrtinuedratsuccessivrelylowerlevelsuntilthebSottomoftheshortert*subtreeisreacrhed.`pAtsomelevrelsnomovementmaybSenecessary;~pbutatnot*levrel6arethetwosubtreesmovedclosertogether.[WhentheproScessiscomplete,t*the4pSositionofthesubtreesis xedrelativretotheirparent,NXwhichiscenteredt*orverthem.XAssuredthatthesubtreeswillnevrerbSeplacedclosertogether,thet*pSostordertrarversaliscontinued. AnonrtrivialimplementationofthisalgorithmhasbSeenobtainedbyReingoldt*and4TilfordthatrunsintimeO(1g cmmi12N@),KwhereNisthenrumbSer4ofnodesofthetreet*to8bSedrarwn. eTheircrucialideaistokeeptrackofthecontourofthesubtreesbyt*spSecialpoinrters,calledthreads,sucrhthatwhenevertwosubtreesarejoined,onlyt*the- toppartofthetreesdorwntothelowestlevelofthesmallertreeneedtobSet*takrenintoaccount. TheCRVTCalgorithmisgivrenin[15 ].CThenoSdesarepositionedona xedgridt*and"areconsideredtoharve"zerowidth.NolabSellingisprorvided.Thealgorithmt*onlydrarwsbinarytrees,butiseasilyextendabletomultiwaytrees.|V3w1\t\< lcircle10sV\sL\&sL\&O line10Q\V\A[\&A`\&sL\:sB\NsB\NG\DL\DAQ\NAV\NsL\:V\0`\0@j\:@t\:sj\Nsj\No\Dt\DAy\NA~\NsV\`\ UVj\t\Q~\ UTQ\Q\st\&st\&~\UV\\Q\UTQ\%Q\&s\:s\Ns\N\D\DA\NA\Ns\:\0\0@\:@Ĭ\:s\Ns\N\DĬ\DAɬ\NAά\Ns*ss&s&A&A &s:sNsNDDANANs:0 0@:@ :sNsND DA%NA*Ns   *H4H> HHHRsH&sH&MRAW&A\&sH:s>Ns>NCDHDAMNARNsH:R0\0@f:@p:sfNsfNkDpDAuNAzNswUTt*Figure41: &ThelefttreeisdrarwnbythealgorithmofWVetherellandShannon,~andt*thetidierrighrtoneisdrawnbythealgorithmofReingoldandTilford.,\s\s\\\A\A\s\&s\&\\A\&A\&s\:s\Ns\N\D\DA\NA\Ns\bs\b\X\XA\bA\bs\vs\s\\\A\A\s\s\\\A\AĬ\s\s\s\\\A\AĬ\s\s\\Ĭ\Aɬ\Aά\sĬ\sĬ\ɬ\ά\AӬ\Aج\s\\Ĭ\Aɬ\Aά\s\v\l\lA\vAĬ\vs\:\0\0A\:A\:sssAA s&s& A&A&s:sNsNDDANA NsbsbX XAbAbsvssAA ss AAsssAA ss AAss @ @*s @ @*sv ll@ v@*vs: 00@ :@*:sUTt*Figure#2:ThelefttreeisdrarwnbythealgorithmofReingoldandTildford,!butt*theX2righrttreeshowsthatnarrowerdrawingsful llingallaestheticaxiomsaret*pSossible.|V4(:w1\Z<^KağsWğsMğ&sCğ:s9ğNs9ğN>ğDCğ:Hğ0Mğ0ARğ:AWğ:sMğNsMğNRğDWğDA\ğNAağNsMğ&RğWğ\ğağAfğAkğsağ&sağ0Afğ:Akğ:sağ&fğ,\s,\s,\&s,\:s,\Ns,\N,\D,\:,\0,\&,\,\,\,\A,\A,\s,\&s,\:s,\Ns,\N,\D,\DA,\NA,\Ns,\:,\0,\0A,\:A,\:s,\&,\V2!", cmsy10J!ꨟsꨟsΪ((!ꨟsꨟsꨟ&sꨟ&ꨟꨟjꨟS jSꨟs ꨟ&s ꨟ&ꨟꨟAꨟ&Aꨟ&sꨟ&ꨟꨟꨟꨟ@ꨟ@ꨟsꨟ&sꨟ0Aꨟ:Aꨟ:sꨟ&ꨟZb!ꨟsꨟsꨟ&sꨟ:sꨟNsꨟNꨟDꨟ:ꨟ0ꨟ&ꨟꨟjꨟS jSꨟs ꨟ&sꨟ:sꨟNsꨟNꨟDꨟDAꨟNA ꨟNsꨟ:ꨟ0 ꨟ0Aꨟ:Aꨟ:s ꨟ&ꨟwUTt*Figurep|3:The rsttrwop|treesgetthesameplacemenrtoftheirnoSdesbytheRVTal-t*gorithm,oalthoughPthestructureofthetrwoPtreesisvrerydi erent.Thealternativet*drarwings_highlightthestructureofthetreesbyaddingadditionalwhitespacet*bSetrweenthesubtreesof(UY!)signi canrtnodes. t*A3+Improuvingzhumanp=erceptionoftreesb#t*ItTiscommonunderstandinginbSookTdesignthataestheticsandreadabilitrydon'tt*necessarily9coincide,"Oand|asLampSort([11 ])putsit|booksaremeanrttoberead,t*notltobSehrungonwalls.!Therefore,&xreadabilityismoreimpSortantthanaesthetics. Whenitcomestotreedrarwings,EMreadabilitymeansthatthestructureofatreet*mrust˜bSeeasilyrecognizable.1ThiscriterionisnotalwaysmetbytheRVTalgorithm.t*Asanexample,Ftherearetreeswhosestructureisvrerydi erent,Ftheonlycommont*thingbSeingthefactthattheyharvethesamenrumberofnodesateacrhlevel.!Thet*RVT[malgorithmmighrtassignidenticalpSositionstothesenodesmakingitvreryhardt*toWcpSerceivrethedi erentstructures.Hence,rwehavemoSdi edtheRVTalgorithmt*sucrhthatadditionalwhitespaceisinsertedbSetweensubtreesofsigni cffant;noSdes.t*HereabinarynoSdeiscalledsigni canrtiftheminimumdistancebSetweenitstwot*subtreesI3istakrenbffelowtheirroSotlevel.TSettingtheamountofadditionalwhitet*spacetozeroretainstheoriginalRVTplacemenrt.Thee ectofhavingnonzerot*additionalwhitespacebSetrweenthesubtreesofsigni canrtnodesisillustratedint*Figure3. AnotherfeaturewrehaveaddedtotheRVTalgorithmsisthepSossibilitytodrawt*anunextendedbinarytreewiththesameplacemenrtofnoSdesasitsassociatedt*extendedvrersion.WVede netheassoffciated^&extendedversionofabinarytreetobSet*theAbinarytreeobtainedbryreplacingeachemptysubtreehavinganonemptysib-t*lingwithasubtreeconsistingofonenoSde.&/Thisfeaturealsomakresthestructuret*ofatreemoreprominenrt;seeFigure4.|V58w1\* UXeAğs[AğsQAğ&sGAğ:sGAğ:LAğ0QAğ0AVAğ:A[Ağ:sQAğ&VAğ[Ağ`AğeAğAjAğAoAğseAğ&seAğ&jAğoAğAtAğ&AyAğ&s\s\s\&s\:s\:\0\0A\:A\:s\&\\A\&A\&s\\\A\A\s\AŬ\&Aʬ\&sss&s:s:00A:A:s&@@&s&s&!&A+&A0&swscsY&sO:sO:T0Y0A^:Ac:sY&^cAh&Am&scmw@@sA&A&sSlTslTslT&slT:slT:lT0lT0AlT:AlT:slT&lTlTAlT&AlT&slTlTlT@lT@lTslT&slT&lTlTAlT&AlT&scUTt*Figure@{4:Inthe rsttrwo@{drawings,btheRVTalgorithmassignsthesameplacementt*toSthenoSdesoftrwoStreesalthoughtheirstructureisvrerydi erent. ThemoSdi edt*RVTbalgorithmshighlighrtsthestructureofthetreesbyoptionallydrawingthemt*likretheirextendedcounterpart,whichisgiveninthesecondrow. t*A4+TaGreesfinado=cumenutpreparationenvironmentb#t*Drarwingsoftreesusuallydon'tcomealone,Ϩbutareincludedinsometextwhicht*is{EitselftrypSesetbyatextproScessingsystem. Therefore,latypicalscenarioist*aMpipSeofthreestages.Firstcomesthetreedrarwingprogramwhichcalculatest*thepSositioningofthenodesofthetreetobedrarwnandoutputsadescriptiont*of1thetreedrarwinginsomegraphicslanguage;1nextcomesagraphicssystemt*whicrh"transformsthisdescriptionintoanintermediatelanguagewhichcanbSet*inrterpreted1bytheoutputdevice;vand nallycomesthetextproScessingsystemt*whicrhintegratestheoutputofthegraphicssystemintothetext. ThisvscenariolosesitslinearstructureoncenoSdesharvevtobelabelled,sincet*the\labSellingin uencesthepositioningofthenodes.!Labelsusuallyoccurinside,t*totheleftof,,totherighrtof,orbSeneathnodes(thelatteronlyforexternalnodes),t*and theirextensionscertainlyshouldbSetakrenintoaccountbythetreedrawingt*algorithm.WBut zthelabSelsharve ztobetrypeset rstinordertodeterminetheirt*extensions,qpreferably#brythetypSesettingprogramthatisusedfortheregulart*text,ٮbSecausethismethodmakresfortheuniformityinthetextualpartsofthet*doScumenrtfLandprovidestheauthorwiththefullpSowerofthetextproScessingt*systemforcompSosingthelabels.#Hence,lamorecomplexcommrunicationschemet*thanasimplepipSeisrequired. AlthoughxasystemoftrwoxproScessesrunningsimrultaneouslymightbSethemostt*eleganrtfsolution,zwewantedasystemthatiseasilypSortabletoalargerangeoft*hardwrare{atoursitesincludingpSersonalcomputerswithsingleprocessoperating|V6Iqw1\t*systems.7Therefore,*wre2thoughtofusingatextproScessingsystemhavingpro-t*grammingdfacilitiespSorwerfuldenoughtoprogramatreedrarwingalgorithmandt*graphics!facilitiespSorwerful!enoughtodrarwatree.SJOnetextprocessingsystemt*renderingoutstandingtrypSographicqualityandgoSodenoughprogrammingfacili-t*tiesisT UE!X,)devrelopSedbyKnuthatStanfordUniversity;Jsee[10 ].TheT UE!Xsystemt*includesthefollorwingprogrammingfacilities:ӍВ1.+datatrypSes:+inrtegerst(256),Zdimensions2|{Ycmr81 4(512),bSoxest(256),tokenlistst(256),bSoolean+vXariables(unrestricted)I􍍍В2.+elemenrtarystatements:+aUR:=const,a:=b(alltrypSes);+aUR:=a+b,aUR:=ab,aUR:=a=b(inrtegersanddimensions);+horizonrtalandverticalnestingofbSoxesВ3.+conrtrolconstructs:+if-then-elsepstatemenrtstestingrelationsbSetweenintegers,Hdimensions,bSoxes,+orbSooleanvXariablesВ4.+moSdularizationconstructs:+macroswithupto9parameters(canbSeviewredasprocedureswithoutthe+conceptofloScalvXariables).Ӎ AlthoughRtheprogrammingfacilitiesofT UE!Xhardlyexceedtheabilitiesofat*TVuring5macrhine,ztheyaresucienttohandlerelativelysmallprograms.  Howt*abSout¸thegraphicsfacilities?+AlthoughT UE!Xhasnobuilt-ingraphicsfacilities,ʵitt*allorwstheplacementofcharactersinarbitrarypSositionsonthepage.$/Therefore,t*complexpicturescanbSesynrthesizedfromelementarypictureelementstreatedt*as5gcrharacters.LampSorthasincludedsuchapicturedrawingenvironmentinhist*macropacrkXageLDD"A_T UE!X,usingquartercirclesofdi erentsizesandlinesegmentst*(with'ExXtodescribGephysicalmeasurementsoftypGographical ob8jects,UUlikethelengthofaword.|V7Yw1\t*a`coarseresolution,|IitiscertainlynotnecessaryforT UE!X,asystemthatiscapablet*ofhandlingarbitrarydimensionsandproSducesdeviceindepffendentoutput.(Vt*A5+Azrepresenutationmetho=dforTc EXtreesb#t*The& rstproblemtobSesolvredinimplementingourtreedrawingalgorithmishowt*tocrhoSoseagoodinrternalrepresentationfortrees.?Astraightforwardadaptationt*ofW$theimplemenrtationbyReingoldandTilfordrequires,rCforeachnoSde,rCatleastt*thefollorwing elds:В1.+trwopSointerstothechildrenofthenoSdeВ2.+trwo.=dimensionsfortheo settotheleftandtherighrtchild(thesemaybSe+di erenrtkoncetherearelabSelsofdi erentwidthstotheleftandrightofthe+noSdes)В3.+trwoidimensionsforthex-andyn9-coSordinatesofthe nalpositionofthe+noSdesВ4.+threeorfourlabSelsВ5.+onetokrentostorethegeometricshapSe(circle,gsquare,framedtextetc.)0of+thenoSde. Becausethesedataareusedvreryfrequentlyincalculations,QtheyshouldbSet*storedCinregisters(that'swhatvXariablesarecalledinT UE!X),ratherthanbSeingt*recomputed,inqordertoobtainreasonablyfastpSerformance.FThisgivresatotalt*of410NregistersforatreewithNnoSdes,whicrhwouldexceedT UE!X'slimitedt*supplyJ"ofregisters. WMTherefore,wrepresentamoSdi edalgorithmhand-tailoredt*totheabilitiesofT UE!X. WVestartwiththefollorwingobservXation.SuppSoseat*unary-binaryZutreeisconstructedbSottom-up,hinapostordertrarversal. FThisZuist*done2bryiteratingthefollowingthreestepsinanorderdeterminedbythetreetot*bSeconstructed.В1.+CreateanewsubtreeconsistingofoneexternalnoSde.В2.+CreateanewsubtreebryappSendingthetwosubtreescreatedlasttoanew+binarynoSde;seeFigure5.В3.+CreateaanewsubtreebryappSendingthesubtreecreatedlastasaleft,UP/&&&&MDNDODPDD&33ff((+/ܬ۟ڟٟ ꩟uDvDwD xD ꨟDܞ33ff(=)0js/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(j,"j,&jUV,0jUUl:jl>jl/>@՟BԟDӟFjP7oDN7pDL7qDJ7rDHjD>֞33ff(a/tqvpxozn|~>K DK DK DK D~~=Dtq33ff(>5=)%s/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(j L M 1orjs/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(7pfe0Dor s JjJjJ/HHHH~N DDDDMDH33ff(OUX}nFigure5:8Constructionsteps2and3 t*bSeforethepushoperationiscarriedout.{FinallyV,Athetreetobeconstructedwillt*bSetheremainingtreeonthestacrk. ThisL'treetrarversalL'ispSerformedtrwiceintheRVTalgorithm.]^Duringthe rstt*pass,atuxeacrhexecutionofstep2orstep3,therelativrepSositionsofthesubtree(s)t*andofthenewnoSdearecomputed.A`closerexaminationoftheRVTalgorithmt*revrealsdthatinformationabSoutthesubtree'scoordinatesisnotneededduringthist*pass;theconrtourinformationalonewouldbSesucient.Completeinformationt*is]onlyneededinthesecondtrarversal,z8when]thetreeisactuallydrarwn.lHereat*spSecialpfeatureofT UE!Xcomesinthatallorwsustosaveregisters.UnlikePascal,t*T UE!X@prorvidesthecapabilityofstoringadrawinginasinglebSoxregisterthatcant*bSe positionedfreelyinlaterdrarwings.nIThismeansthatinourimplementationt*theutrwopassesoftheoriginalRVTalgorithmcanbSeintertwinedintoasinglepass,t*storing9fforeacrhsubtreeonthestackitscontouranditsdrawing.%Althoughthet*latterisacomplexobject,ittakresonlyoneofT UE!X'spreciousregisters.(Vt*A6+Thezinuternalrepresentationb#t*GivrenWatree,u$thecorrespSondingT UE!Xtreeisaborxcontainingthe\drawing"ofthet*tree,togetherwithsomeadditionalinformationabSouttheconrtourofthetree.t*The referencepSoinrtofaT UE!Xtree-borxisalwaysintheroSotofthetree.Theheight,t*depth,andwidthofthebSorxofaT UE!Xtreeareofnoimportanceinthisconrtext. TheadditionalinformationabSouttheconrtourofthetreeisstoredinsomet*registersfornrumbSersanddimensionsandisneededinordertoputsubtreest*together#toformalargertree.lo @isanarraryofdimensionswhichcontainsfort*eacrhlevelofthetreethehorizontalo setbSetweentheleftendoftheleftmost|V9 rw1\cUX-10ptӈ10ptӈ10ptlo lTslTslTAlT&AlT&slT0AlT:AlT:slTlTlTAlTAlTsAAs15pt5pt,L-10ptgrffo gTt*heighrt:3,typSe:dot,ltop:2pt,rtop:2pt,lmo :-10pt,rmo :20pt,lbo :10pt,t*rbSo :10pt.t*Figure6: PA}T UE!Xtreeconsistsofthedrarwingofthetreeandtheadditionalinfor-t*mation.The.9widthofthedotsis4pt,?theminimalseparationbSetrween.9adjacentt*noSdesis16pt,*_makingforadistanceof20ptcenrtertocenter.Thelengthofthet*smallhrulelabSellingoneofthenodesis5pt.7Thecolumnleft(righrt)ofthetreet*drarwingvisthearraylo q(rffo ),describingtheleft(right)contourofthetree.KAtt*eacrhlevel,+thedimensiongivenisthehorizontalo setbSetweenthebSorderatthet*currenrt{sandatthenextlevel.Theo setbSetweentheleftbSorderoftherootnodet*andP%theleftmostnoSdeatlevrel1is-10pt,itheo setbetrweenP%therighrtborderoft*theroSotnodeandtherighrtmostnodeatlevrel1is15pt,etc. t*noSdeatthecurrenrtlevelandtheleftendoftheleftmostnoSdeatthenextlevel.t*lmo /holdsOthehorizonrtalo setbSetweentheroSotandtheleftmostnodeofthet*whole%tree.}Wlbffo 4holdsthehorizonrtalo setbSetweentheroSotandtheleftmostt*noSdeQatthebottomlevrelofthetree.FinallyV,ltopAgholdsthedistancebetrweenQthet*referencepSoinrtofthetreeandtheleftmostendoftheroot.%Thesameistruefort*rffo ,rmo ,rbffo ,and rtop;#justreplace\left"bry\right".FinallyV,height1>holdst*theheighrtofthetree,andtypffe~9holdsthegeometricshapSeoftherootofthetree.t*Figureq6shorwsanexampleT UE!Xtree,i.e.VatreedrawingandthecorrespSondingt*additionalinformation. GivrentwoT UE!XtreesAandB<,howcananewT UE!XtreeCbSebuiltthatconsistst*ofanewroSotandhasAandB'uassubtrees?8AnexampleisgivreninFigure7. Firstrwredeterminewhichtreeishigher;thisisBintheexample.Thenwet*harvetocomputetheminimaldistancebSetrweentherootsofAandB<,sucrhthatatt*allOlevrelsofthetreesthereisfreespaceofatleastminsep bSetweenthetreeswhent*theyaredrarwnsidebyside."FVorthispurpSosewekeeptrackoftwovXalues,Ftotsept*and4currsep.ThevXariablestotsep=JandcurrsepholdthetotaldistancebSetrweent*the0roSotsandthedistancebetrween0therighrtmostnodeofAandtheleftmostt*noSde,ofBatthecurrenrtlevel.$aInordertocalculatetotsepiBandcurrsep,xwestartt*atrlevrel0andvisiteachlevelofthetreesuntilwereachthebSottomlevelofthet*smallertree;thisisAinourexample.֌X10 w1\AJiA:-10ptP10ptP10ptlo (A)6ns,ns,nA1n&A6n&s6n0A;n:A@n:s,n1n6nA;nABnsAAs\15pta5ptX.-10ptX.rffo (A)\(B:P10pt-10pt-10pt-10pt-10ptlo (B<)JnsJnAOnATnsJn&s@n:s6nNs,nbs,nb1nX6nN;nD@nDAEnNAJnNs@n:En0Jn&Onf10ptb.-10ptb.-10ptf10ptb.-30ptb.rffo (B<)33C:-20-10pt;lo (A)u cmex108 >< >:P10ptP10ptM!P10pt{ lo (B<)f^-P10ptlo (C)Jns6ns,n&s,n0A1n:A6n:s6nDA;nNA@nNs,n&1n6nA;n&ABn(sAAs6n@nJn@Tn@^ns^nAcn&Ahn&s^n:sTnNsJnbs@nvs@nvEnlJnbOnXTnXAYnbA^nbsTnNYnD^n:cn0z20ptz10ptv.-10ptv.-10ptލꨫ9 >>>>>>>>>>>= >>>>>>>>>>>;j rffo (B<)z10ptv.-30ptv.rffo (C)P@щffB &c͟Yff+Bhff:AYffa3BYff~OCUYffffBͤYff͟dheighrtff<3>Yffb 5>Yff6>YffͤYff͟dtrypSeUff6 dot Yff]Qdot Yffdot YffͤYff͟dltop97ff;sr2pt͟Yffb62pt͟Yffj2pt͟YffͤYff͟drtopff;sr2pt͟Yffb62pt͟Yffj2pt͟YffͤYff͟dlmo ɡff1-10pt͟YffXlJ-30pt͟Yff/-30pt͟YffͤYff͟drmo ^ff5v20pt͟Yff\V10pt͟Yffn30pt͟YffͤYff͟dlbSo ǡff5v10pt͟YffXlJ-30pt͟Yff/-10pt͟YffͤYff͟drbSo Nff5v10pt͟YffXlJ-30pt͟Yff/-10pt͟YffffB،ωff &cͤYff͟dlevrelff(totsepYffScurrsepYffffͤYffI9d0ff0)20pt͟YffW.0/16pt͟YffͤYffI9d1ff0)25pt͟Yff\11/16͟YffͤYffI9d2ff0)40pt͟YffW.1/16pt͟YffͤYffI9d3ff0)40pt͟YffcE&16pt͟YffffR.荑t*Figure7:TheT UE!XtreesAZandB'arecomrbinedtoformthelargerT UEXtreeC.t*Thesmalltablegivresthehistoryofcomputationfortotsepandcurrsep.֌X11 w1\ Artglevel0,thedistancebSetweentheroSotsofAg*andBshouldbeatleastt*minsep.JTherefore, wresettotsep& H:=_}minsep*c+rtopDu(A)+ltopQ@(B )andcurrsep-:=t*minsep30W.NUsing"rffo &(A)"andlo (B ),wrecanproSceedtocalculatecurrsep8forthet*nextlevrel.+Ifcurrsep-a<URminsep(,wehavetoincreasetotsep(bythedi erenceandt*upSdate$scurrsep.AThisprocessisiteratedunrtilwereachthelowestlevelofA.t*ThenuCtotsep1Yholdsthe naldistancebSetrweenuCthenodesofAu&andB<,ascalculatedt*bry4theRVTalgorithm.IftheroSotofCisasigni cantnoSde,F[thentheadditionalt*space,12whicrhis0ptbydefault,12isaddedtototsep.HHowever,12theapproachoft*synrthesizing drawingsfromsimplegraphicscharactersallowsonlya nitenumbSert*of%Xorienrtationsforthetreeedges;Btherefore,4totsepnmustbSeincreasedslightlytot* tthenextorienrtationavXailable. NorwwearereadytoconstructthebSoxofT UE!XtreeC.SimplyputAandBt*side87bryside,[withthereferencepSointstotsepMunitsapart,[insertanewnoSdeaborvet*them,andconnecttheparenrtandchildrenbyedges. Next,wreupSdatetheadditionalinformationforC.Thiscanbedonebryusingt*theVadditionalinformationforAIandB<.NotethatmostcompSonenrtsofrffo 2(C &k)t*andzlrffo (C &k)zarethesameasinthehighertree,whicrhisB7inourcase.$&So,ifwret*canarvoidmovingthisinformationaround,weonlyhavetoaccessheight$ (A)#E+t*cffonst.")manrypcountersinordertoupSdatetheadditionalinformationforC.Thist*impliesithatwrecanapplythesameargumentasin[15 ],Vwhichgivesusarunningt*timeofO(N@)fordrarwingatreewithNnoSdes. Therefore,Uwre@pmustcarefullydesignthestoragealloScationfortheadditionalt*informationIofT UE!Xtreesinordertoful llthefollorwingrequirements:Ifanewtreet*iswbuiltfromtrwowsubtrees,/Mtheadditionalinformationofthenewtreeshouldsharet*storage withitslargersubtree.Organizationalorverhead,wthat is,pSoinrterswhicht*kreep[\trackoftheloScationsofdi erentpartsofadditionalinformation,wmustbSet*arvoided.UThis$meansthatalltheadditionalinformationforoneT UE!Xtreeshouldt*bSestoredinarorwofconsecutivedimensionregisterssuchthatonlyonepSointert*granrtingaccesstothe rstelementinthisrowisneeded.4Ontheotherhand, cmmi10handthenumbGerofnodesN qrefertothedrawingofthetree.QNisthenumbGer ofUUcircles,squaresetc.actuallydrawn,andhisthenumbGeroflevelsinthedrawingminus1.֌X14Uw1\+The(secondpartisshorwnbyinductiononh.Thebasishr=0(isclear.+Assumebtheassumptionholdsforalltreesofheighrtlessthanh. IfT+conrtainsonlysubtreesofeithertheleftortherightsubtreeofT,wehave swX G tUT.:02T1(hrt N(TƟ 0o)+1)URōh(h+1)Qmfe+p  24zō(h+1)(h+2)QmfeH̟  !O2N;:#+Otherwise,T=conrtainswptheleftortherightsubtreeTsofT.7Thenallele-+menrtsofTufTsn Therefore,ourƩimplemenrtationusesatmost9hV?+2minF(N;(h+1)(h+2)=2)Ʃreg-t*isters.7Inordertocomparethiswiththe10N*registersusedinthestraighrtforwardt*implemenrtation,anestimationoftheaverageheightofatreewithNnoSdesist*needed.Sevreralresults,depSendingonthetypSeoftreesandoftherandomizationt*moSdel,arehscitedinFigure9,whicrhcomparesthenumbSerofregistersusedinat*straighrtforwardimplementationwiththeaveragenumbSerofregistersusedinourt*implemenrtation.8ThistableshowsclearlytheadvXantageofourimplementation.(Vt*A8+Thezuserinuterface#t*R100sYff~O70.44wǟYff:107.37ťYff)58.80ןYffͤYff{[d11ff>R110sYff~O74.91wǟYff:113.64ťYff)62.41ןYffͤYff{[d12ff>R120sYff~O79.26wǟYff:119.71ťYff)65.87ןYffͤYff{[d20ff>R200sYffycP111.34ɟYff:163.56ťYff)90.48ןYffͤYff{[d30ff>R300sYffycP147.37ɟYff:211.33ťYff117.31ٟYffͤYff{[d40ff>R400sYffycP180.89ɟYff:254.75ťYff132.58ٟYffͤYff{[d50ff>R500sYffycP212.80ɟYff:295.37ťYff143.54ٟYffffW@|oˍt*Figure&9:NThenrumbSers&ofregistersusedbryastraightforwardimplementationt*(second6column)andbryourmoSdi edimplementation(thirdto fthcolumn)oft*the5RVTalgorithmaregivrenfordi erenttypSesoftreesandrandomizationmodels.t*TheformrulainparenthesesindicatestheaverageheightoftherespSectiveclassoft*trees,asdepSendingonthenrumberofnodes. t*macros.InU},\rght{