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.

  • $\begingroup$ 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? $\endgroup$ – Mario Carneiro Mar 7 '19 at 4:34
  • $\begingroup$ @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. $\endgroup$ – D.W. Mar 7 '19 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.