stabo@majestix.ida.liu.se (Staffan Bonnier) (05/25/90)
In article <6331@crabcake> callahan@crabcake.cs.jhu.edu (Paul Callahan) writes: > >What is known about the problem of determining the minimum number >of rotations required to transform one (rooted, oriented) binary tree >into another? I attended a talk by Tarjan a couple years ago when >I was at Penn State, and I seem to remember him saying that the >existence of a polynomial time algorithm for this problem was an open >question. > The following simple observation may be of some help to you: A binary tree is full (a full binary tree is a tree in which every node either has two children or is a leaf) iff it is (isomorphic to) the parse tree of a term built from a number of constants and a binary operator. For instance, the tree: * / \ * c / \ d e is the parse tree of ((d*e)*c). Moreover, a (left or right) rotation in such a tree corresponds to one application of the associative law to the term: (A) x*(y*z) = (x*y)*z A right-rotation of the tree in the example yields: * / \ d * / \ e c which corresponds to applying (A) from right to left, and thus obtaining the term (d*(e*c)). Thus, the minimum number of rotations required to transform one tree into another is the same as the minimum length of an equational proof, proving that the corresponding terms are equal in the theory (A). Staffan Bonnier
stabo@ida.liu.SE (Staffan Bonnier) (06/01/90)
In article <6331@crabcake> callahan@crabcake.cs.jhu.edu (Paul Callahan) writes: > >What is known about the problem of determining the minimum number >of rotations required to transform one (rooted, oriented) binary tree >into another? I attended a talk by Tarjan a couple years ago when >I was at Penn State, and I seem to remember him saying that the >existence of a polynomial time algorithm for this problem was an open >question. > The following simple observation may be of some help to you: A binary tree is full (a full binary tree is a tree in which every node either has two children or is a leaf) iff it is (isomorphic to) the parse tree of a term built from a number of constants and a binary operator. For instance, the tree: * / \ * c / \ d e is the parse tree of ((d*e)*c). Moreover, a (left or right) rotation in such a tree corresponds to one application of the associative law to the term: (A) x*(y*z) = (x*y)*z A right-rotation of the tree in the example yields: * / \ d * / \ e c which corresponds to applying (A) from right to left, and thus obtaining the term (d*(e*c)). Thus, the minimum number of rotations required to transform one tree into another is the same as the minimum length of an equational proof, proving that the corresponding terms are equal in the theory (A). Staffan Bonnier