Minimum number of tree operations to normalize a labeled tree

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.

$$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.

• Very nice. There are a few missing bits, but the main idea is all here. The partition algorithm also needs to handle the case $u(v_0v_1)$ where all items of $u$ are $\le \alpha$ or all $>\alpha$, and variations on this with $v$. All of these can be put in the appropriate form in $O(1)$ operations. Also the input might not be balanced, or the partitioning might throw off the balance; we can fix this by perfectly rebalancing the tree before each partitioning step, which is $O(n)$ so within the budget of $T(n)$. Do you see a way to get a $\Omega(n\log n)$ matching lower bound? Mar 7 '19 at 4:34
• @MarioCarneiro, good question! I don't see how to get a better lower bound than what you show in the question... but maybe someone else will spot something.
– D.W.
Mar 7 '19 at 5:11

$$\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.

• Very nice construction. In the last part, you say that a rotation operation creates one unvisited node, but doesn't it create two? (Also commutations create one, although they can be handled specially.) At least, the defining property of nodes that have to be un-visited is that the tree configuration under them has not appeared earlier in the sequence, and this would seem to be the case with both nodes created in a tree rotation. Sep 24 '21 at 0:54
• To answer my own question: After a rotation or commutation, we are at the new root, and so later $(L|R)$ steps applied to the new root node can be moved to immediately after this position. Thus the new root can be considered visited after any rotation/commutation, and only the new non-root node in a rotation has to be marked as unvisited. Sep 24 '21 at 2:05