; TeX output 1996.04.29:08483ڍE&3ڍLg60CDtqGcmr17CDrauNwingBT_reesNicelywithT)vEzXy?;!",ff cmsy10#􍍍a[i9XQ ff cmr12Anne/BrdDuggemann-Klein= !", cmsy10y#>Derick/W4odCod=z99r,"V 3 cmbx10AbstractMƍ-̻'K`y 3 cmr10WeeMspresen!tanewsolutiontothetreedrawingproblemthatintegratesanexcellent _treeadra!wingalgorithmintooneofthebMesttextprocessingsystemsa!vdDailable. More_preciselye,w!eQpresentaT,[wEB XmacropackdDagecalledTereeT,[wEB XthatproMducesdrawingsof_treesOfromapurelylogicaldescription.Ourapproac!hhasthreeadvdDantages:LabMelsfor_noMdescanbehandledinareasonablew!ay;'portingTereeT,[wEB Xtoan!ysiterunningT,[wEX_isatrivialopMeration;Aandmodularit!yinthedescriptionofatreeandT,[wEB X'smacro_capabilitiesfallo!wforlibrariesofsubtreesandtreeclasses.-̻In*.addition,K TereeT,[wEB XhasanoptionthatproMducesdra!wingsthatmakethe*': 3 cmti10struc-_turpe?ofȞthetreesmoreob!vioustothehumaneye,+eventhoughtheymaynotbMeas_aestheticallyfpleasing.(VANG cmbx12A1(Inutro=ductionb#0XQ cmr12TheproblemofsuccessfullyinrtegratingpicturesandtextinadoScumentproScessingenvi-ronmenrtKistantalizinganddicult.zAlthoughtherearesystemsavXailablethatallowsuchinrtegration,btheyJfallshortinmanyways,busuallyindoScumentqualityV.YGFurthermore,bmostauthors4usingdoScumenrtpreparationsystemsareneitherbookdesignersnorgraphicartists.Just asmoSderndocumenrtpreparationsystemsdonotexpectanauthortobeabookde-signer,אso.wrewouldpreferthattheydonotexpSectanauthortobeagraphicartist.qsThesecondSauthor,1WVoSod,neededStodrarwmanytreesinaseriesofpapSersontreesandinapro-jectedSwbSookontrees.zThisproblemenabledustotacrkletheintegrationissueforonesubareaofgraphics,namelyV,treedrarwing.#WVehadthedecidedadvXantagethattherealreadyexistedgoSod4algorithmstodrarwtrees3@ cmti12withoutwsanyauthorintervention.Previous4expSerienceoftheinrtegrationofpicturesandtexthadbSeenuninspiring;5thesystemsexpectedtheauthortoprepareeacrhpictureintotal.FVorexample,:atreecouldbSebuiltupfromsmallersubtreesbuttheOrelativreplacementofthemwaslefttotheauthor.PThissituationcontinuestoholdtoSdaywith^thedrarwingfacilitiesavXailableonmostpSersonalcomputers,{wand,because^ofthis,{wthe ff- g^ O!cmsy7K`y cmr10This;workwassuppGortedbyaNaturalSciencesandEngineeringResearchCouncilofCanadaGrantA- 5692,=aDeutscheF*orschungsgemeinschaftGrantSto167/1-1,=andagrantfromtheInformationT*echnologyResearch4Centre.fItwasbGegunduringthe rstauthor'sstaywiththeDataStructuringGroupinW*aterloGo.  X^yInstitutUUfGurInformatik,UniversitatF*reiburg,Rheinstr.10{12,7800Freiburg,WestGermany X^zDatauStructuringGroup,DepartmentofComputerScience,UniversityuofW*aterloGo,WaterloGo,Ontario N2LUU3G1,Canada1*3ڍE&3ڍ&resulting@ guresstillappSeartobe\hand-drarwn."; AdditionallyV,V;theyareofinferiorqualitywhencomparedwiththequalitryofthesurroundingtext.In"thispapSerwrepresentanentirelynewsolutionthatintegratesatreedrawingalgorithminrtooneofthebSesttextprocessingsystemsarvXailable.#MorepreciselyV,hwedescribSeTVreeT UE!X,aAT UE!XmacropacrkXagethatproSducesanaestheticallypleasingdrawingofatreefromapurelylogicalAGdescription.featurewrehaveaddedtotheRVTalgorithmsisthepSossibilitytodrawanun-extendedJ1binarytreewiththesameplacemenrtofnoSdesasitsassociatedextendedvrersion;thisx2makresthestructureofatreemoreprominent;seeFigure4.}WVede netheassoffciatedextendeffdversionyofabinarytreetobSethebinarytreeobtainedbryreplacingeachemptysubtreeharvinganonemptysiblingwithasubtreeconsistingofonenoSde.A5(TaGreeszinado=cumenutpreparationenvironmentb#Drarwings5oftreesdonotusuallyappSearbythemselves,GbutareincludedinsometextthatisitselftrypSesetbyatextproScessingsystem.huTherefore,{atypicalscenarioisapipSeofthreestages.v0First,nwreTmhaveatreedrawingprogramthatcalculatesthepSositioningofthenodesof_thetreetobSedrarwnandoutputsadescriptionofthetreedrawinginsomegraphicslanguage;othisisfollorwedbyagraphicssystemthattransformsthisdescriptionintoan5>Š3ڍE&3ڍZKp6sf6s\6&sR6:sH6NsH6NM6DR6:W60\60Aa6:Af6:s\6Ns\6Na6Df6DAk6NAp6Ns\6&a6f6k6p6Au6Az6sp6&sp60Au6:Az6:sp6&u6ss&s:sNsND:0&AƠAˠs&s:sNsNDDANANs:00AƠ:Aˠ:s&ƠA2!", cmsy10 !ꨟsꨟsΪ((!ꨟsꨟsꨟ&sꨟ&ꨟꨟjꨟS jSꨟs ꨟ&s ꨟ&ꨟꨟAꨟ&Aꨟ&sꨟ&ꨟꨟꨟꨟ@ꨟ@ꨟsꨟ&sꨟ0Aꨟ:Aꨟ:sꨟ&ꨟi5p2!ꨟsꨟsꨟ&sꨟ:sꨟNsꨟNꨟDꨟ:ꨟ0ꨟ&ꨟꨟjꨟS jSꨟs ꨟ&sꨟ:sꨟNsꨟNꨟDꨟDAꨟNA ꨟNsꨟ:ꨟ0 ꨟ0Aꨟ:Aꨟ:s ꨟ&ꨟwUTFigure-3:ThenoSdesofthe rsttrwo-treesareplacedinthesamepositionsbrytheRVTalgo-rithm,Boalthough`thestructureofthetrwo`treesisdi erenrt.Thealternativedrawingshighlightthestructuraldi erencesofthetreesbryaddingadditionalwhitespacebSetweenthesubtreesof(UY!)signi canrtnoSdes.fh s s &s :s : 0 0A :A :s &    A A s &s &  A &A &sDsDsD&sD:sD:D0D0A D:AD:sD& DDAD&AD&sDDDADA$Ds$DA)D&A.D&sS+Xs+Xs+X&s+X:s+X:+X0+X0A+X:A+X:s+X&+X+X+X+X@+X@+Xs+X&s+X&+X+XA+X&A+X&s"ss&s:s:00A :A:s& A&A&s"@,@6s6A;&A@&sटsटsट&sट:sट:ट0ट0Aट:Aट:sट&टटAट&Aट&sटटट@ट@टsट&sट&टटAट&A ट&scUTFigureL4:Asintheprevious gure,e/thenoSdesofthe rsttrwoLtreesareplacedinthesamepSosition5brytheRVT5algorithm,HUalthoughtheirstructureisdi erent.ThemoSdi edRVTalgo-rithmshighlighrtsthestructuraldi erencesofthetreesbydrawingthemliketheiridenticalextendedvrersion(giveninthethirdrow),butsuppressingtheadditionalnoSdes.6O3ڍE&3ڍ&inrtermediate/languagethatcanbSeinterpretedbytheoutputdevice;sand, nallyV,we/havethetextproScessingsystemthatinrtegratestheoutputofthegraphicssystemintothetext.This)0scenariolosesitslinearstructureoncenoSdesharve)0tobelabeled,8sincethelabelingin uencesUthepSositioningofthenodes.Labelsusuallyoccurinside,totheleftof,totherighrt[Iof,worbSeneathnodes(thelatteronlyforexternalnodes). TheirwidthsshouldcertainlybSe"takrenintoaccountbythetreedrawingalgorithm.FButthelabSelshavetobSetypSeset rsttodeterminetheirextensions,߅preferablybrythetypSesettingprogramthatisusedfortheOregulartext,i1bSecausethisensuresuniformitryinthetextualpartsofthedocumenrtandprorvides^theauthorwiththefullpSowerofatextproScessingsystemforcomposingthelabels.Hence,amorecomplexcommrunicationschemethanasimplepipSeisrequired.AlthoughzasystemoftrwozproScessesrunningsimrultaneouslymightbSethemostelegantsolution,wrewwantedasystemthatiseasilypSortabletowidelydi erentmachinesatoursitesincludingKpSersonalcomputerswithsingleprocessoperatingsystems.Therefore,wredecidedto0useatextproScessingsystemharvingprogrammingfacilitiesporwerful0enoughtoprogramaltreedrarwingalgorithmandgraphicsfacilitiespSowerfulenoughtodrawatree.iOnetextproScessingvsystemrenderingoutstandingtrypographicqualitryandsatisfactoryprogrammingfacilitiesTisT UE!X,tdevrelopSedbyKnuthatStanfordUniversity;see[11 ]. u/TheT UE!Xsystemincludesthefollorwingprogrammingfacilities.cǍ\h1._DatatrypSes:_inrtegers(256),b*dimensions2|{Ycmr81 (512),bSoxes(256),tokenlists(256),andbSooleanvXari-_ables(unrestricted).򍍍\h2._Elemenrtarystatements:_aUR:=const,a:=b(alltrypSes);_aUR:=a+b,aUR:=ab,aUR:=a=b(inrtegersanddimensions);and_horizonrtalandverticalnestingofbSoxes.\h3._Conrtrolconstructs:_if-then-elsestatemenrtstestingrelationsbSetweenintegers,dimensions,bSoxes,orbSoolean_vXariables.\h4._MoSdularizationconstructs:_macrosUwithupto9parameters(canbSeviewredasprocedureswithouttheconceptof_loScalvXariables).cƍAlthough#theprogrammingfacilitiesofT UE!XhardlyexceedtheabilitiesofaTVuringma-crhine,Etheyaresucienttohandlesmallprograms. +HowabSoutthegraphicsfacilities?AlthoughT UE!Xhasnobuilt-ingraphicsfacilities,_{itallorwstheplacementofcharactersinarbitrarypSositionsonthepage.M=Therefore,ycomplexpicturescanbesynrthesizedfromele-menrtarypictureelementstreatedascharacters.ӎLampSorthasincludedsuchapicturedrawingenrvironmentinhismacropacrkXageLDD"A_T UE!X,usingquartercirclesofdi erentsizesandlineseg-menrts d(withandwithoutarrowheads)ofdi erentslopSesasbasicelements;see[12 ].Theseelemenrtsaresucientfordrawingtrees. yff- ^ٓRcmr71TheW-term!': cmti10dimensionisusedinTU>'ExXtodescribGephysicalmeasurementsoftypGographicalob8jects;for example,UUthelengthofaword.7_u3ڍE&3ڍ&This0survreyofT UE!X'scapabilitiesimpliesthatT UEXmarybSeasuitabletextprocessingsystemtoimplemenrtatreedrawingalgorithmdirectlyV. 2WebaseouralgorithmontheRVT/algorithm,@bSecausethisalgorithmgivres,aestheticallyV,themostpleasingresults.Inthe rst5vrersionpresentedhere,Ywerestrictourselvestounary-binarytrees,YalthoughourmethoSdishapplicabletoarbitrarymrultiwayhtrees. ? ButtotakreadvXantageofthetextproScessingenrvironment,weexpandthealgorithmtoallowlabSelednodes.In%conrtrasttoprevioustreedrawingprograms,@wefeelnonecessitytopSositionthenodesofatreeona xedgrid.WhilethismarybSereasonableforaplotterwithacoarseresolution, itisicertainlynotnecessaryforT UE!X,iasystemthatiscapableofhandlingarbitrarydimensionsandproSducingdeviceindepffendentoutput.'fA6(Azrepresenutationmetho=dforTc EXtreesb#Thef rstproblemtobSesolvredinimplementingourtreedrawingalgorithmishowtochoSosea&goSodinrternalrepresentationfortrees.SA%straightforwardadaptationoftheimplementationbryReingoldandTilfordrequires,foreachnoSde,atleast:򍍍\h1._trwopSointerstothechildrenofthenoSde,>P\h2._trwozdimensionsfortheo settotheleftandtherighrtchild(thesemaybSedi erent_oncetherearelabSelsofdi erenrtwidthstotheleftandrightofthenoSdes),\h3._trwodimensionsforthex-andyn9-coSordinatesofthe nalpositionofthenodes,\h4._threeorfourlabSels,and\h5._onetokrentostorethegeometricshapSe(circle,square,framedtext,etc.)8ofthenode.Becausethesedataareusedfrequenrtlyincalculations,7theyshouldbSestoredinregisters(that's=whatvXariablesarecalledinT UE!X)ratherthanbSeingrecomputed,GtoobtainreasonablyfastpSerformance.%Thisgivresatotalof10NregistersforatreewithNnoSdes,Iwhicrhquicklyexceeds>T UE!X'slimitedsupplyofregisters. Therefore, wrepresentamoSdi edalgorithmhand-tailoredtotheabilitiesofT UE!X."WVestartwiththefollorwingobservXation.SuppSoseaunary-binary>ItreeisbuiltbSottom-up,S1usingapostordertrarversal.3This>IcanbedonebryrepeatingthefollorwingthreestepsinanorderdeterminedbythetreetobSebuilt.yC\h1._CreateanewsubtreeconsistingofoneexternalnoSde.\h2._Create5lanewsubtreebryappSendingthetwosubtreeslastcreatedtoanewbinarynoSde;_seeFigure5.\h3._CreateCianewsubtreebryappSendingthesubtreecreatedlastasaleft,Yright,orCiunary_subtreeofanewnoSde;seeFigure5.yC(ApSoinrter"to)eachsubtreethathasbSeencreatedinsteps1{3ispushedontoastack,andǿsteps2and3remorveǿtwotreesoronetree,κrespSectivelyV,fromǿthestacrkbSeforethepushopSerationiscarriedout.8Thetreetobebuiltisthetreeremainingonthestacrk.8 o.3ڍE&3ڍb֍>UP/gџ4D4D4D4DgПD33ff(Rx+/ܬ۟ڟٟ ꩟uDvDwD xD ꨟDܞ33ff(=)0js/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(j,"j,&jUV,0jUUl:jl>jl/>@՟BԟDӟFjP7oDN7pDL7qDJ7rDHjD>֞33ff(a/%%%%ZD[D\D]DD%33ff(=)%s/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(j L M 1orjs/֬՟ԟӟj 7oD7pD7qD7rDjD֞33ff(7pfe0Dor s JjJjJ/HHHH~N DDDDMDH33ff(OUXPFigure5:8Constructionsteps2and3 This$treetrarversal$ispSerformedtrwiceintheRVTalgorithm.Duringthe rstpass,s7ateacrh=Pexecutionofsteps2or3,QtherelativepSositionsofthesubtree(s)andofthenewnodearecomputed.SALcloserexaminationoftheRVTalgorithmrevrealsthatinformationabSoutthe͕subtree'scoSordinatesisnotneededduringthispass;? theconrtourinformationaloneissucienrt.Complete informationisonlyneededinthesecondtraversal,Pwhenthetreeisreally_drarwn. ThisiswherewecanuseaspSecialfeatureofT UE!Xthatallowsustosaveregisters.'UnlikrePascal,T UE!XhasthecapabilityofstoringadrawinginasinglebSoxregisterthatcanbSepositionedfreelyinlaterdrarwings.@&Thismeansthatinourimplementationthetrwo(passesoftheoriginalRVTalgorithmcanbSewroven(intoasinglepass,ustoringthecontourand'drarwingofeachsubtreeonthestack.v^Althoughthelatterisacomplexobject,GittakesonlyoneofT UE!X'spreciousregisters.(VA7(Thezinuternalrepresentationb#Givrenatree, thecorrespSondingT UE!Xtreeisaborxcontainingthe\drawing"ofthetree,together]withsomeadditionalinformationabSouttheconrtourofthetree. ThereferencepSoinrtxofaT UE!Xtree-borxisalwaysintheroSotofthetree.Theheight,idepth,andxwidthofthebSorxofaT UE!Xtreeareofnoimportanceinthisconrtext.The9additionalinformationabSouttheconrtourofthetreeisstoredinsomeregistersfornrumbSersanddimensionsandisneededinordertoputsubtreestogethertoformalargertree.An4arrarylo ofdimensionscontainsforeachlevelofthetreethehorizontalo setbSetrweenh theleftendoftheleftmostnodeatthecurrenrtlevelandtheleftendoftheleftmostnoSdeatthenextlevrel.nThehorizontalo setbSetweentheroSotandtheleftmostnodeofthewholeutreeisholdinlmo ,andthehorizonrtalo setbSetweentheroSotandtheleftmostnodeatMthebSottomlevrelofthetreeisholdinlbffo .FinallyV, ltopcholdsthedistancebetrweenMthereferencepSoinrtofthetreeandtheleftmostendoftheroot.~qWVeuserffo ,rmo ,rbffo ,and9 }b3ڍE&3ڍ UX]0-10ptG10ptG10ptdlo टsटsटAट&Aट&sट0Aट:Aट:sटटटAटAटsAAs D15ptk@5pt-10ptNrffo gTheighrt:3,typSe:dot,ltop:2pt,rtop:2pt,lmo :-10pt,rmo :20pt,lbo :10pt,rbo :10pt.Figure66:'AT UE!Xtreeconsistsofthedrarwingofthetreeandtheadditionalinformation.Thewidthofthedotsis4pt,YtheminimalseparationbSetrweenadjacentnoSdesis16pt,YmakingforadPdistanceof20ptcenrtertocenter.ThelengthofthesmallrulelabSelingoneofthenodesis5pt.vThecolumnleft(righrt)ofthetreedrawingisthearraylo 2D(rffo ),ـdescribingtheleft(righrt)contourofthetree.yoAteachlevel,thedimensiongivenisthehorizontalo setbSetrweentheborderatthecurrenrtandatthenextlevel.cTheo setbSetweentheleftbSorderof\BtheroSotnodeandtheleftmostnodeatlevrel1is-10pt,xtheo setbetrween\BtherighrtborderoftheroSotnodeandtherighrtmostnodeatlevrel1is15pt,etc. rtopasthecorrespSondingvXariablesfor\left"replacedbry\right."FinallyV,+heightBholdstheheighrteofthetree,8andtypffeKLholdsthegeometricshapSeoftherootofthetree. Figure6shorwsanexampleT UE!Xtree,thatisatreedrarwingandthecorrespSondingadditionalinformation.Givren[twoT UE!XtreesATandB<,howcananewT UE!XtreeCSbSebuiltthatconsistsofanewroSotandhasAandB\assubtrees?a$AnexampleisgivreninFigure7.Firstwredeterminewhicrhtreeishigher;AVthisisB)9intheexample.7ThenwehavetocomputetheminimaldistancebSetrween?therootsofA?andB<,sucrhthatatalllevelsofthetreesthereisfreespaceofatleastminsepqrbSetrween\thetreeswhentheyaredrarwnsidebyside.'FVorthispurpSosewekeeptrackoftrwovXalues,totsep˾andcurrsep.Thevariablestotsep˾andcurrsepholdthetotaldistancebSetrweentherootsandthedistancebetrweentherighrtmostnodeofAandtheleftmostnodeofޙBcatthecurrenrtlevel.4TVocalculatetotsepandcurrsep,westartatlevel0andvisiteachlevrel@ofthetreesuntilwereachthebSottommostlevelofthesmallertree;thisisAinourexample.Artlevel0,thedistancebSetweentheroSotsofAandBshouldbeatleastminsep.+=There-fore,s wreU>settotsep%f:=URminsep)+yxrtop4(A)yx+ltop(B )U>andcurrsep-3:=URminsep(.Usingrffo j(A)andlo (B ),Gwrecancalculatecurrsep forthenextlevel.Ifcurrsep,B<URminsep(,GwehavetoincreasetotsepbryTothedi erenceandupSdatecurrsep.Thisprocessisrepeatedunrtilwereachthelow-est levrelofA atwhichpSointtotsepholdsthe naldistancebSetweenthenoSdesofA andB<,asy*calculatedbrytheRVTalgorithm. IftheroSotofC9 isasigni cantnoSde,thentheadditionalspace,ޅwhicrhis0ptbydefault,ޅisaddedtototsep.%However,ޅtheapproachofsynthesizingdrarwingsfromsimplegraphicscharactersallowsonlya nitenumbSeroforientationsforthetreeedges;therefore,totsepmrustbSeincreasedslightlyto tthenextorientationavXailable.Norw \wearereadytobuildthebSoxofT UE!XtreeC.SimplyputA andBFsidebyside,with`thereferencepSoinrtstotsepYvunitsapart,insertanewnodeaborve`them,andconnectthe10 3ڍE&3ڍ& 3AYeA:-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)PN (щ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͟YffffBZ،ωff Ť &cͤYff͟dlevrelff(totsepYffTcurrsepɟYffff šͤYffI9d0ff0)20pt͟YffYt0/16pt͟YffͤYffI9d1ff0)25pt͟YffS11/16pt͟YffͤYffI9d2ff0)40pt͟YffYt1/16pt͟YffͤYffI9d3ff0)40pt͟Yffe416pt͟Yffff ŎR.Figure_Y7:8TheT UE!XtreesA_5andBarecomrbinedtoformthelargerT UEXtreeC.The rsttablegivres*theadditionalinformationofthethreeT UE!Xtrees,Q andthesecondtablegivesthehistoryofthecomputationfortotsepandcurrsep.11 3ڍE&3ڍ&parenrtandchildrenbyedges.%RNext,wecomputetheadditionalinformationforC.ThiscanbSedonebryusingtheadditionalinformationforALandB<.Notethatmostcomponenrtsofrffo a(C &k)T5andlrffo i(C)arethesameasinthehighertree,rLwhicrhisBinourcase.So,ifwrecanarvoidmovingthisinformationaround, `thenumbSerofcounterswehavetoaccesstoupSdatethe+additionalinformationforCgiswithinasmallconstanrtoftheheightofA.Hence,׌wecanapplythesameargumenrtasin[16 ],whichgivesusarunningtimeofO(N@)fordrawingatreewithNnoSdes.WVe mrustdesignthealloScationofstorageregistersfortheadditionalinformationofT UE!XtreesULcarefullytoful llthefollorwingrequirement.xIfanewtreeisbuiltfromtwosub-trees,BthefouraddressregistersareupSdatedaccordinglyV. gThismeansthatthisinformationforthesubtreesisnolongeraccessible."Theconrtourinformationofthenewsubtreeisstoredinthe"sameregistersastheconrtourinformationofthelargersubtreeusedintheconstruction,apartAfromtheleftandrighrto setoftheroSottotheleftandrightchild,Vwhicharestoredin_thefollorwingdimensionregisters.ThismeansthatgapscanoSccurbetrween_theconrtourinformationofsubtreesinthestacrk,/namelywhentherightsubtree,/whichisinahigherpSosition2inthestacrk,Dishigherthantheleftone.TVoavoidthesegaps,DtheusercanspSecifyanHoption6߆T cmtt12\lefttopwhenenrteringabinarynoSde,iwhichmakesthetopmosttreeinthestacktheleftsubtreeofthenoSde.This3stacrkconceptalsohasconsequencesforthedesignoftheuserinterfacethatisdiscussedinSection9.12 3ڍE&3ڍfŀDimensionregisterslmo (1)rmo (1)lbffo (1)rbffo (1)ltop(1)rtop(1)lo (h1)rffo (h1).T..lo (1)rffo (1).T..lmo (n)rmo (n)lbffo (n)rbffo (n)ltop(n)rtop(n)lo (h2cmmi8nP)rffo (hn).T..lo (1)rffo (1)Counrterregisterslasttrffeebox[lasttreeheightlasttreeinfolasttreetypetrffeeheight$D(1)diminfo(1).T..trffeeheight(n)diminfo(n)Borxregisterstrffeeboxq(1).T..trffeebox(n)TVokrenregisterstypffe(1).T..type(n)FigureN8:lasttrffeeboxq,hlasttreeheight$D,lasttreeinfo,lasttreetype4conrtainNpSointerstotrffeeboxq(n)trffeeheight$D(n),xlmo (n),typffe(n),diminfo(i)\{conrtainsapSointertolmo (i).XUnuseddimen-sionMregistersareallorwedMbSetweenthedimensionregistersofsubsequenttrees.Thecounterregisterslasttrffeeboxq,.T..,diminfo(n)servreasadirectorymechanismtoaccesstheT UE!Xtreesonthestacrk.133ڍE&3ڍ&A8(Spacezcostanalysisb#SuppSose%wrewanttodrawaunary-binarytreeT_ofheighthhavingN noSdes22.* Accordingtoourinrternalrepresentation,foreachsubtreeinthestackweneed:sW\h1._onebSorxregistertostoretheborxoftheT UE!Xtree;|֍\h2._onetokrenregistertostorethetypSeoftherootofthesubtree;\h3._2h2K cmsy80+6 dimensionregisterstostoretheadditionalinformation,6whereh20Sistheheighrt_ofthesubtree;and\h4._threeelcounrterregisterstostoretheregisternumbSersoftheborxregister,thetoken_register,andthe rstdimensionregisterabSorve.sW5N cmbx12Lemma8.1O[Lffet35Tbeaunary-binarytreeofheighthandsizeN@;then:v Q1._at35anytime,therffeareatmosth+135subtreesofTonthestack;and Q2._for35effachsetT@ofsubtreesofTthatareonthestacksimultaneouslywehavet썍ƦԟX G >T.:q% cmsy602T؀}(hrt N(TƟ 0o)+1)URN(TheuarecitedinFigure9,whicrhcomparesthenumbSerofZregistersusedinastraighrtforwardZimplementationwiththeaveragenumbSerofregistersusedinourimplemenrtation.2ThistableshowsclearlytheadvXantageofourimplementation.(A9(Thezuserinuterfaceb#The>userinrterfaceofTVreeT UE!XhasbSeendesignedinthespiritofthethoroughseparationofthe9logicaldescriptionofdoScumenrtcomponenrtsandtheirlayout;see[7,8 5].ThisconceptensureshbSothuniformitryand exibilityofdoScumentlayoutandfreesauthorsfromlayoutproblemsbthatharvebnothingtodowiththesubstanceoftheirwrork. gFVorsomepSowerfulimplemenrtationsandprojectssee[2,3 ʤ,12,14,15].TheTdescriptionofatreeconsistsofadescriptionofitsnoSdesinpostorder. Eacrhde-scriptionz'ofanoSde,inturn,hastospSecifytheoutdegree,thegeometricshapSeandthelabelsofk thenoSde.Defaultsareprorvidedforallspeci cations,&therebryallowingtheusertoomitmanryde nitionsifthedefaultsmatchwhatheorshewants.AO]separateOstrylecommandde neslayoutparametersfortreedrawingsthatarevXalidforalltreesofadoScumenrt.BgLayoutparametersincludethefonrttobeusedforlabels,the ]ff- ^2The8height b> cmmi10handthenumbGerofnodesNSrefertothedrawingofthetree.LpNisthenumbGer8ofcircles, squares,UUetc.,actuallydrawn,andhisthenumbGeroflevelsinthedrawingminus1.14Ǖ3ڍE&3ڍ#LX=m_ffZ扩 &c͟Yff(ff1registersYffdarverageregistersPVݟYffe(Tff5 ͤYff͟dnoSdesff/(straighrt-͟YffYffAunary-binary͟Yffc8binaryYYff͟Yff(ff1Dforwrard)CYffk(Tbinarytrees͟YffpwtreesYff searcrhtrees楟YffkͤYkffdNGpkffd!Ykffl)^(2p ؉z (n9N)[6]ןYkff V(p ؉z (3n9N!)P[6]_Ykff(4:311log-GN@)[5]͟YkffffZ扦ͤYff\d10 [ff@һ100sYffycP120.89ɟYff:107.37ťYff109.34YffͤYff\d20 [ff@һ200sYffycP182.68ɟYff:163.56ťYff156.23YffͤYff\d30 [ff@һ300sYffycP234.75ɟYff:211.33ťYff191.96YffͤYff\d40 [ff@һ400sYffycP281.78ɟYff:254.75ťYff223.12YffͤYff\d50 [ff@һ500sYffycP325.60ɟYff:295.37ťYff251.78YffͤYff\d60 [ff@һ600sYffycP367.13ɟYff:334.02ťYff278.86YffͤYff\d70 [ff@һ700sYffycP406.93ɟYff:371.17ťYff304.84YffͤYff\d80 [ff@һ800sYffycP445.36ɟYff:407.13ťYff330.02YffͤYff\d90 [ff@һ900sYffycP482.67ɟYff:442.12ťYff354.59YffͤYff ]d100ff;b1000uYffycP519.04ɟYff:476.30ťYff378.68YffffZ扎wTFiguren9:AMThenrumbSersnofregistersusedbryastraightforwardimplementation(secondcol-umn)FVrom.theprogrammer'spSoinrtofview,T6T UE!X'smacrolanguageisalowlevelprogramminglanguage.Hence,@mainrtainingeandextendingthepackXageisamoretedioustaskthanitwouldbSeifwrehadusedahigherlevellanguagewithbSettersupportformodularization.15ջ3ڍE&3ڍ&>FVromtheauthor'spSoinrtofview,TreeT UE!X'slimitationslieinspSeed,sizeoftrees,andgraphical9Sprimitivres.$TypSesettingallthetreesinthisarticletakesabSouttwominutesonaVAX}750,randtrypSesettingacompletebinarytreewith63internaland64externalnoSdestakres_=abSoutoneminuteonthesamemachine. Thesizeofthetreesislimitedbythreefactors,$namelyV,thehnrumbSerofregisters,$thecomplexityofthenestedbSoxesthatcontainthedrarwingofatree,9andthelimitednumbSerofslopesthatarearvXailablefortheedges,9thelatterbSeingthemostsevrereproblematpresent.QHence,themainareaofapplicationforTVreeT UE!XpUismoSdestusesucrhasintextbooks;displaryinglargeamountsofstatisticaldata,forexample,isoutofthequestion.CurrenrtlyedgesandcircularnoSdesaredrawnfromLDD"A_T UE!X'ssetofprede nedgraphicalcrharacters.Hence,5TVreeT UE!X&cannotdrawarbitrarilywidetreesorlargecircularnoSdes.WVeconsider+thisrestriction,5horwever,to+bSeatemporaryone,5sinceacommitteeinsidetheT UE!XUsersGroupiswrorkingonstandardgraphicextensionstoT UEXthatwillremorvetheselimitations.AstofurtherdevrelopmentsofTVreeT UE!X,itwrouldbSedesirabletodrawlargerclassesoftrees,forexamplemrultiwaytrees,andtoallorwlabSelsnotonlyfornodes,butalsoforedgesandwholesubtrees.16踠3ڍE&3ڍgG{^4 Knruth132O<Carnes2П32hBeeton1П32t rst90hߟ&h4h9h%~J9|Bߟ|B4%|B 9/|B %0B 3Kellermann|C32[3[,[$[[[k [ Z[Z[Z["Z[)Z [1Zk4Z/e<5LampSort32E7SpivXakv32Plass6П32M00h¢&hڟhM/hɤ˟~JM0|B֢|Bڟ%|BM//|Bݤ˟0B38TVobin.325last1 kş' o  qTS \begin{Tree}\node{\external\bnth{first}\cntr{1}\lft{Beeton}}\node{\external\cntr{3}\rght{Kellermann}}\node{\cntr{2}\lft{Carnes}}\node{\external\cntr{6}\lft{Plass}}\node{\external\bnth{last}\cntr{8}\rght{Tobin}}\node{\cntr{7}\rght{Spivak}}\node{\leftonly\cntr{5}\rght{Lamport}}\node{\cntr{4}\rght{Knuth}}\end{Tree}\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%PVFigure10:8ThisisanexampleofatreethatincludeslabSels.173ڍE&3ڍ͍G{Knruth0Ʉfffnff(EUff(Effܷ<CarnesؑɄfffnff+%sff+%ffyWBeeton%pɄfffnff+ff+ff rstϾ1վ'۾NTT$T.TN0TKellermann|BɄfffnffC;3^gffC;3ffQП1,QП(,QП UZ,QП,QП,ڸ@U[,QПUQlQПlQПlQП(UPl"QП0l"@0l!<LampSortɄfffnff4 ff4ff SpivXakuɄfffnff)Қff)ffӣPlass{Ʉfffnff"<[]?ff"<[ffՇ'1ڇ''߇''+'A'A'$A'.A+0A-lTVobin.Ʉfffnff%ʑПff%ʄff_last){1 )z' )y )x L \begin{Tree}\node{\external\type{frame}\bnth{first}\cntr{Beeton}}\node{\external\type{frame}\cntr{Kellermann}}\node{\type{frame}\cntr{Carnes}}\node{\external\type{frame}\cntr{Plass}}\node{\external\type{frame}\bnth{last}\cntr{Tobin}}\node{\type{frame}\cntr{Spivak}}\node{\leftonly\type{frame}\cntr{Lamport}}\node{\type{frame}\cntr{Knuth}}\end{Tree}\hspace{\leftdist}\usebox{\TeXTree}\hspace{\rightdist}%AFigure11:8ThisisanexampleofatreewithframedcenrterlabSels.183ڍE&3ڍ)UB'A4 Knuth2&  X1(Carnes2o  Bepeton1o   rst,C ,B ; ,CL,BL;L gE3KelFlermannx  "wwwww w=mݍWH WHWHWHWHWH="aH#(5Lpamport"X  -7 Spivak֟  $Plass6o  E E Tk ELELTkL‬8T)obinн  Яlast GGn3iэFigurex12:ThistreewrasproSducedfromthesamelogicaldescriptionasinFigure10,butwithdi erenrtstyleparameters19x3ڍE&3ڍ&AReferencesb#[1]' R.iA.Baeza-YVates.UOnemrbSeddingabinarytreeonahypSercube.USubmittediforpubli-' cation,NorvembSer1988.[2]' R.~J.Beacrh. ZSettingTablesandIllustrffationswithStyle.PhD~thesis,Univrersity~of' WVaterloSo,1985.[3]' A.@tBrSvuggemann-Klein,bPV.Dolland,andA.Heinz. Horwtopleaseauthorsandpublishers:' ATvrersatileddoScumentpreparationsystematKarlsruhe.%InJ.Dsesarmenien,reditor,TUEuX' for|_Scienti cDoffcumentation,KpagesP8{31,StrasbSourg,FVrance,June1986. `Springer-' VVerlagLectureNotesinComputerScience236.[4]' A.BBrSvuggemann-KleinandD.WVood. 7DDrarwingtreesnicelywithT UE!X.InM.Clark,' editor,|pPrffoceedingsoftheThirffdEuropeanTUEuX-Conference,|pExeter,England,July`1988.' TVoappSear.[5]' L.Devrorye.tAnoteontheheightofbinarysearchtrees.tJournalrQoftheA2CM,33(3):489{' 498,July1986.[6]' Ph.kxFlajoletandA.Odlyzkro.f5Theaverageheightofbinarytreesandothersimpletrees.' Journal35ofComputerandSystemSciencffes,25:171{213,1982.[7]' R.FVuruta,ZJ.Sco eld,andA.Sharw.DoScumentformattingsystems:Survreys,concepts,' issues.5Computing35Surveys,14(3):417{472,1982.[8]' Ch.QF.Goldfarb.fAPgeneralizedapproacrhtodoScumentmarkup.fSIGPLAN6NoticffesNof' the35A2CM,16(6):68{73,June1981.[9]' R.OzKleinandD.WVoSod.aOnOzbinarytrees.InG.Ritter,heditor,Prffoceedingsofthe11th' World35ComputerCongrffess,SanFVrancisco,USA,1989.5ToappSear.[10]' D.E.Knruth.|FundamentalwA2lgorithms,Gvolume1ofTheA2rtofComputerPrffogramming.' Addison-WVesley,Reading,Massacrhusetts,1973.[11]' D.E.Knruth.TheTUEuXbffook,volumeAofComputers&Typffesetting.Addison-WVesley,' Reading,Massacrhusetts,1986.[12]' L.@LampSort. $LDD#fcmti8A@TUEuX,BUser'sػGuide&RffeferenceػManual.Addison-WVesley,'Reading,' Massacrhusetts,1986.[13]' Th.;OttmannandPV.Widmaryer.&A2lgorithmen}undDatenstrukturffen.Bibliographiscrhes' Institut,Mannheim,1989.5TVoappSear.[14]' V.sQuinrt,2I.VVatton,andH.Bedor. Grif:IAninrteractivesenvironmentforT UE!X. In' J.!Drsesarmenien,/Weditor,TUEuXeforScienti cDoffcumentation,/Wpages!145{158,StrasbSourg,' FVrance,June1986.5Springer-VerlagLectureNotesinComputerScience236.203ڍE&3ڍ&[15]' B.DK.Reid.$Scribffe:aA)Document)Speci cationLanguageanditsCompiler.$PhDAthesis,' CarnegieMellonUnivrersityV,1980.[16]' E.M.ReingoldandJ.S.Tilford. F Tidierdrarwingsoftree.IEEE¶Trffansactionson' Softwarffe35Engineering,7(2):223{228,Marcrh1981.[17]' K.J.SupSorwitandE.M.Reingold. {ThecomplexityofdrawingtreesnicelyV. {Affcta' Informaticffa,18(4):377{392,1983.[18]' Ch.QWVetherellandA.Shannon.<Tidydrarwingsoftrees.IEEE`TrffansactionsonSoftware' Engineffering,5(5):514{520,SeptemrbSer1979.21 ;3GCDtqGcmr17ANG cmbx12;!",ff cmsy109XQ ff cmr126߆T cmtt125N cmbx123@ cmti122!", cmsy101g cmmi120XQ cmr12,"V 3 cmbx10*': 3 cmti10'K`y 3 cmr10!': cmti10#fcmti8K cmsy82cmmi8|{Ycmr8q% cmsy6 !", cmsy10 O!cmsy7 b> cmmi10K`y cmr10ٓRcmr7< lcircle10O line10u cmex10