二元树之间的旋转距离

RotationDistancesbetweenBinaryTrees

二元樹之間的旋轉距離研究生：陳嬿如指導教授：王有禮教授國立臺灣科技大學資訊管理系碩士學位論文1.Introduction1.1RotationdistanceTherotationdistance

d(T,T’)betweentwobinarytreesTandT’withthesamenumberofleavesistheminimumnumberofrotationsneededtotransformTintoT’.RotationLeftrotationRightrotation34LeftRotation5Rightrotation61.2SurveyItremainsanopenproblemwhetherrotationdistancebetweenbinarytreescanbecomputedinpolynomialtime[29].Pallo[22],

Rogers[27]gaveapproximationalgorithmsCulikandWood[7]upperboundto2n–2[17,30]2n–6forn≥11Pallo[20,21,23]rotationdistanceinthelattice7“Restricted”rotationdistanceBonninandPallo[4]onlyatnodeswithaleaf

Sundar[31]onlyasingledirectionofrotationcalledrightrotationCleary[5]therootortherightchildoftheroot

Pallo[24]atnodesalongtherightarmofthetree8RootorRightchildoftheroot9Rightarm102.Preliminaries2.1LW-sequenceTheweightwT

(i)iscalledtheleftweightofviinTandtheintegersequencewT=(wT

(1),wT

(2),...,wT

(n))iscalledtheleftweightsequence(LW-sequenceforshort)ofT[19]

.

vi

123456wT(i)12121612GiventheLW-sequenceofabinarytreeT,weshowthatthepreorderofTcanbedeterminedbyusingtheintervalrepresentation.Thestartpoint

ST

(i)=i

wT

(i).TheendingpointDT

(i)=i.viwT

(i)ST(i)DT(i)v1101v2202v3123v4224v5145v66060123456v1v2v3v4v5v6132.2AVL-rotationsLL(Rightrotation)RR(Leftrotation)LRRL14LRRL152.3Weightdifferencesδ(i)=wT’

(i)

wT

(i),1≤i≤n,astheweightdifferenceforeachnodeviinthetrees.vi123456wT’(i)123451wT(i)121216δ(i)00+2+2+45163.AlgorithmAlgorithm1Tree-TransformationInput:TheLW-sequenceswTandwT’ofthesourcetreeTandthedestinationtreeT’,respectively.Output:

dist(T,T’),anestimationoftherotationdistancebetweenTandT’.Step1.Letdist(T,T’)=0,andcompute,,and.Step2.while

δ(i)≠0forsomei

{1,...,n}do

Substep2.1ifthereexistvi,vp,vqinthecurrenttreesuchthatviistherightchildofvpandvpistheleftchildofvqforsomei

{1,...,n}andδ(i)>0>δ(q)

then

doLR-rotation(i);18

Substep2.2

elseifthereexistvi,vp,vq

inthecurrenttreesuchthatviistheleftchildofvpandvpistherightchildofvqforsomei

{1,...,n}andδ(i)>0>δ(p)

thendoRL-rotation(i);

Substep2.3

elseifthereexistvi,vp

inthecurrenttreesuchthatviistherightchildofvpforsomei

{1,...,n}andδ(i)>0thendoRR-rotation(i);

Substep2.4

elseifthereexistvi,vl

inthecurrenttreesuchthatvlistheleftchildofviforsomei

{1,...,n}andδ(i)<0then

doLL-rotation(i);endif

Substep2.5

dist(T,T’)=dist(T,T’)+1,and

recompute,and.endwhileStep3.Outputdist(T,T’).193.1Anexample20213.2AnalysisTheorem8GiventheLW-sequencesoftwobinarytreesTandT’withthesamenumberofinternalnodes,sayn,thealgorithmTree-TransformationproducesasequenceofrotationstoconvertTintoT’inO(Δn)time,where.O(n2)224.ConclusionUsinganamortizedanalysisComputingtheaveragerotationdistanceIn[20],Pallopresentedtherotationdistanceinthelatticeofbinarytrees.(3)=1.5(3)=1.424References[1]G.M.Adelson-VelskyandE,M.Landis,“Analgorithmfororganizationofinformation,”SovietMathematicsDoklady3(1962)1259–1263.[2]A.Andersson,“Generalbalancedtrees,”JournalofAlgorithms30(1999)1-18.[3]R.Bayer,“SymmetricbinaryB-trees:datastructureandmaintenancealgorithms,”Acta

Informatica1(1972)290-306.[4]A.BonninandJ.Pallo,“Ashortestpathmetriconunlabeledbinarytrees,”PatternRecognitionLetters13(1992)411-415.[5]S.Cleary,“Restrictedrotationdistancebetweenbinarytrees,”InformationProcessingLetters84(2002)333-338.[6]S.ClearyandJ.Taback,“Boundingrestrictedrotationdistance,”InformationProcessingLetters88(2003)251-256.[7]K.CulikandD.Wood,“Anoteonsometreesimilaritymeasures,”InformationProcessingLetters15(1982)39-42.[8]C.GermainandJ.Pallo,“ThenumberofcoveringsinfourCatalanlattices,”InternationalJournalofComputerMathematics61(1996)19-28.25[9]S.Hanke,T.OttmannandS.Schuierer,“Theedge-flippingdistanceoftriangulations,”JournalofUniversalComputerScience2(1996)570-579.[10]F.HurtadoandM.Noy,“Graphoftriangulationsofaconvexpolygonandtreeoftriangulations,”ComputationalGeometry13(1999)179-188.[11]F.Hurtado,M.NoyandJ.Urrutia,“Flippingedgesintriangulations,”DiscreteComputationalGeometry22(1999)333–346.[12]D.E.Knuth,SortingandSearching,in:TheArtofComputerProgramming,Vol.3,Addison-Wesley,Reading,MA,1973.[13]J.M.Lucas,“Therotationgraphofbinarytreesishamiltonian,”JournalofAlgorithms8(1987)503-535.[14]J.M.Lucas,D.RoelantsvanBaronaigien,andF.Ruskey,“Onrotationsandthegenerationofbinarytrees,”JournalofAlgorithms15(1993)343-366.[15]J.M.Lucas,“Adirectalgorithmforrestrictedrotationdistance,”InformationProcessingLetters90(2004)129-134.[16]J.M.Lucas,“Untanglingbinarytreesviarotations,”TheComputerJournal47(2004)259-269.26[17]F.LuccioandL.Pagli,“Ontheupperboundontherotationdistanceofbinarytrees,”InformationProcessingLetters31(1989)57-60.[18]E.M¨akinen,“Ontherotationdistanceofbinarytrees,”InformationProcessingLetters26(1987/88)271-272.[19]J.Pallo,“Enumerating,rankingandunrankingbinarytrees,”TheComputerJournal29(1986)171-175.[20]J.Pallo,“Ontherotationdistanceinthelatticeofbinarytrees,”InformationProcessingLetters25(1987)369-373.[21]J.Pallo,“Somepropertiesoftherotationlatticeofbinarytrees,”TheComputerJournal31(1988)564-565.[22]J.Pallo,“Anefficientupperboundoftherotationdistanceofbinarytrees,”InformationProcessingLetters73(2000)87-92.[23]J.Pallo,“GeneratingbinarytreesbyGlivenkoclassesonTamarilattices,”InformationProcessingLetters85(2003)235-238.[24]J.Pallo,“Right-armrotationdistancebetweenbinarytrees,”InformationProcessingLetters87(2003)173-177.[25]R.O.RogersandR.D.Dutton,“Propertiesoftherotationgraphofbinarytrees,”Congressus

Numerantium109(1995)51-63.27[26]R.O.RogersandR.D.Dutton,“Ondistanceintherotationgraphofbinarytrees,”Congressus

Numerantium120(1996)103-113.[27]R.O.Rogers,“Onfindingshortestpat