Minimum number of tree operations to normalize a labeled tree

Question

Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many applications of commutativity (swapping the two children of a node) and associativity (tree rotations) are needed to bring this tree to a sorted normal form like $a(b(cd))$ or $a(b(c(d(ef))))$? Examples:

$$(bc)(ad)\mapsto((bc)a)d\mapsto(a(bc))d\mapsto a((bc)d)\mapsto a(b(cd))$$

\begin{align} &\phantom{{}\mapsto{}}((af)e)(c(db))\\ &\mapsto (a(fe))(c(db))\\ &\mapsto (a(fe))((cd)b)\\ &\mapsto (a(fe))(b(cd))\\ &\mapsto (a(ef))(b(cd))\\ &\mapsto a((ef)(b(cd)))\\ &\mapsto a((b(cd))(ef))\\ &\mapsto a(b((cd)(ef)))\\ &\mapsto a(b(c(d(ef)))) \end{align}

There are $C_{n-1}\cdot n!$ possible trees on $n$ elements, and about $2n$ possible operations to apply at each stage, so the information theoretic bound gives $\Omega(\log_{2n}(C_{n-1}\cdot n!))=\Omega(n)$. On the other hand, if we first fully right associate, then we can perform adjacent swaps with $O(1)$ operations, leading to an upper bound of $O(n^2)$ operations.

I suspect that $O(n\log n)$ operations suffice, perhaps even $O(n)$, but I have not been able to improve on the above bounds. I know that $O(n)$ operations work if it is possible to perform exchanges in $O(1)$, but every element has its depth change by at most 1 per operation, so exchanges are rather expensive ($O(n)$) in this model. Probably we want to keep the tree balanced during the sorting, but assuming a balanced tree it's not clear how to sort effectively by block swaps.

Answer 1

$O(n \log n)$ operations suffice, as you conjectured. One can implement something akin to quicksort (using the median as the pivot in each stage). I'll describe the details below. For simplicity of exposition, let's assume $n$ is a power of two (though it all works for arbitrary powers of two). We'll bring the tree into a normal form, which is a complete binary tree (i.e., all leaves are at the same depth, $\lg n$).

Let $\alpha$ be the $n/2$th label (in sorted order of the labels). We'll first manipulate the tree so it has the form $xy$, where $x$ is a subtree of size $n/2$ containing all items $\le \alpha$ and $y$ is a subtree of size $n/2$ containing all items $>\alpha$. Call this the partition operation. Then, we'll recursively apply the algorithm to the left subtree and to the right subtree.

I'll argue below that the partition operation can be done with $O(n)$ operations. Then it follows that the total number of operations performed by this algorithm obeys the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

which has the solution $T(n) = O(n \log n)$. It follows that this algorithm takes $O(n \log n)$ operations.

So how do we do the partition operation? Well, suppose the tree is originally of the form $uv$. We'll recursively apply the partition algorithm to $u$, to get a tree of the form $u_0u_1$ where the leaves of $u_0u_1$ are the same as the leaves of $u$, but now $u_0$ has all items of $u$ that are $\le \alpha$ and $u_1$ has the items that are $>\alpha$. Similarly, we'll recursively apply the partition algorithm to $v$, to get $v_0v_1$. So after the recursive calls to the partition algorithm, the tree has the form $(u_0u_1)(v_0v_1)$. Now by a constant number of applications of commutatively and associativity, this can be transformed to $(u_0v_0)(u_1v_1)$. At this point, the tree has the desired form, as $u_0v_0$ is composed of all of the items of $uv$ that are $\le \alpha$ and $u_1v_1$ is composed of all of the items of $uv$ that are $>\alpha$.

The running time of the partition algorithm is given by the recurrence

$$U(n) = 2U(n/2) + O(1),$$

which has the solution $U(n) = O(n)$. Thus, the partition algorithm can be done in $O(n)$ operations.

Answer 2

$\Omega(n \log n)$ operations are needed. More precisely, starting from any given tree $T$ you can only reach $\exp(O(n+m))$ other trees in $m$ operations. The idea is to augment your information-theoretic argument with the observation that most operations commute. Note that we cannot hope to replace $O(n+m)$ with $O(m)$, since for $m = 1$ there can be $O(n) \gg 1$ reachable trees.

Let's represent sequences of operations using strings in the six-letter alphabet $\{a, b, c, (, |, )\}$, where the letters $a$, $b$, $c$ represent the basic operations "swap the children of the root", "apply a rotation at the root" and "apply a rotation at the root, but the other direction". The empty string represents the empty sequence. For well-formed strings $L$, $R$, their juxtaposition $LR$ represents "do $L$, then $R$", and $(L|R)$ represents "do $L$ in the left child of the root, and $R$ in the right child". It can be checked that any sequence of operations can be represented by some string and that every string represents at most one sequence of operations. I claim that in fact for any sequence of $m$ operations there is a string of length $O(n+m)$ which represents an equivalent sequence of operations. (Equivalent in the sense that, starting from $T$, one ends up at the same tree after applying either sequence.) Then we'll be done, since the number of such strings is only $\exp(O(n+m))$.

To begin, note that we can find a representing string where the letters $a$, $b$, $c$ together occur exactly $m$ times. So it suffices to bound the number of occurrences of the $(L|R)$ pattern. Let's not count the occurrences which directly precede or succeed one of the letters $a$, $b$, $c$, since there are at most $O(2m)$ of those. We can also assume that $(L|R)(K|S)$ doesn't occur anywhere since it can be replaced by $(LK|RS)$. It remains to consider patterns like $((L|R)|K)$. In this case, the idea is to try to write $(L|R)$ earlier in the string.

To be more precise, after parsing a prefix of our string, we have a state of the following form: a tree $T'$ (the current transformation of $T$), a node $v \in T'$ (the node at which our operations are currently based), and a subset $V \subseteq T'$ of "visited nodes", such that $v \in V$. Initially $T' = T$, $v$ is the root, and $V = \{v\}$. Let's say that after a rotation operation, the newly created node is unvisited, so that the number $|V|$ of visited nodes may decrease by one. But it never decreases otherwise, so it will increase at most $n+m$ times. Returning to the pattern $((L|R)|K)$, consider the state $(T', v, V)$ right before parsing $(L|R)$. If $v$ was already in $V$ earlier, then we can move $(L|R)$ to the corresponding position of our string; otherwise we are in one of only $n+m$ positions where $|V|$ increases.