Can we do better than $O(n\log n)$ building a balanced binary tree?

I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?

Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. If these properties hold then it seems to me that it must be possible to build a balanced binary tree in better than $O(n\log n)$ time.

I don't believe this so I'm wondering where the flaw is in my thinking.

The data-structure is the conc-tree list. In it's standard form it looks like a normal binary tree and comes with a concat operation that ensures the invariant that the left and right subtrees of any node never differ in height by more than one. As expected concat has complexity $O(\log n)$.

But there's a builder variant of the conc-tree list called the Append list. This variant allows for temporary height differences in subtrees of more than one. Amortized $O(1)$ time appends are claimed for this variant.

So it seems appending $n$ elements must have a complexity of $O(n)$.

However it's a characteristic of this variant that whenever $n$ is a power of two one ends up with a complete balanced binary tree (containing all elements inserted so far). So while temporary imbalances are allowed the tree becomes balanced every power of 2 insertions.

In this variant a new class of nodes, called Append nodes, are introduced and it's these nodes whose subtrees are allowed differ in height by more than one. However every $2^k$ insertions all such temporary nodes are eliminated.

The Wikipedia page page describes the algorithm fairly succinctly (see the description of the basic data-structure and the append method in particular).

So when $n$ is a power of two our cost for inserting elements is $O(n)$ and we've built a balanced binary tree. Or so it seems.

In a separate question I effectively asked "if I can state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, is this enough to allow me to state the complexity for all values of $n$?"

I can see from Yuval Filmus's answer that the answer is no, but that "in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold."

So it seems to me that in this case if inserting $n$ elements has complexity $O(n)$ and every $2^k$ elements I have a balanced binary tree then the cost of building balanced binary trees with this conc-tree variant approach must be $O(n)$.

So what's wrong here? To be honest I can't see the amortized $O(1)$ append time claimed for this variant. I can see that often insertions do have cost $O(1)$ but that when one looks at what's happening with the temporary Append nodes the overall insertion cost looks to me to be amortized $O(\log n)$.

If this is the case then building our balanced binary tree has an unsurprising $O(n\log n)$ cost.

Sorry for such a long question and sorry for not going into detail about the algorithm in question - instead leaving you to look around on Wikipedia.

• Please stop appending new questions to your question. If your original question is answered, start another question with any inquiries or confusions you have that are not directly related to the original question. The question in its current state has diverged completely from the title. – aelguindy Nov 6 '16 at 18:01
• Apologies for appending here in the style of an ongoing discussion rather than sticking to the Q&A style. I'll mark this question as answered and try to formulate, as a separate question, my failure to get amortized $O(1)$ in my current analysis of the append operation. – George Hawkins Nov 6 '16 at 19:53
• The much expanded version of this question has been consigned to the edit history. While I much appreciate the answer from @gnasher729 I'm a little surprised it has so many votes since the question is definitely about binary trees and not binary search trees. My confusing the complexity of one with the other doesn't change that. Similarly the question has been retagged from binary-trees to search-trees which doesn't seem correct. – George Hawkins Nov 7 '16 at 9:15

If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:

L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
k = 1
while !q.isEmpty:
n = q.pop
if k < L.size:
n.left = node{value=L[k]}
k++
if k < L.size:
n.right = node{value=L[k]}
k++


It is not hard to see that this code does run in linear time and builds a balanced binary tree.

What you cannot do, is build a balanced binary search (ordered) tree in $O(n)$ time (using only comparisons on the values). The algorithm above does not guarantee that the value on the root is greater than or equal to every value in the left sub-tree and is less than or equal to every value in the right sub-tree, for every sub-tree.

The algorithm above does not guarantee it and neither does the conc-tree (using appends and prepends). From the wikipedia page, it only guarantees $O(1)$ amortized time for appends and prepends. For inserts, it can only guarantee $O(\log n)$ time.

• For the second time in as many days I feel rather stupid for confidently asserting something here that turns out to be false, on the basis of half remembered lectures from 20 years ago. In your example you build a somewhat different kind of tree to the conc-tree, where only leaves have values, but still that just increases the number of nodes (leaves and inner nodes) to $2n - 1$ so the complexity remains as in your case $O(n)$. Now I'm left wondering what if anything is clever about the conc-tree append operation. I've added another section to the end of my already long question. – George Hawkins Nov 6 '16 at 15:58
• @GeorgeHawkins no worries, it is a common confusion :). My example does not place the nodes on the leaves, it places the values at all nodes of the tree. There are several very clever things about conc-trees, trying to come up with a data structure that achieves the same bounds should show you why it's clever. For example, if you want fast appends, you may be tempted to use linked lists, but then how do you access internal elements quickly? – aelguindy Nov 6 '16 at 16:15
• I finally added my update to my question. At this stage though I think I'm most interested in what you refer to as the cleverness of the conc-tree data structure. I can see trees have pluses over lists (where certain characteristics are required) but I'm not so clear on conc-trees pluses over other tree implementations. Right at the end of my question I've added some thoughts along these lines. But just as importantly I still can't see the amortized $O(1)$ append time :( My analysis of what's happening in the case of $2^k$ appends still leads me to an incorrect amortized $O(\log n)$. – George Hawkins Nov 6 '16 at 17:44
• Your question is becoming really big and is diverging from the title of your question. I think you may want to ask a few separate questions. – aelguindy Nov 6 '16 at 17:58
• Re the cleverness of the conc-tree, try implementing a tree that keeps itself balanced with appends and prepends in $O(1)$ amortized time and you'll see why conc-trees are clever. Also, try thinking of how to implement concat for two binary trees. – aelguindy Nov 6 '16 at 18:00

Adding to aelguindy's answer: You just can't put n unsorted items into any kind of data structure, and then enumerate them in sorted order, in better than O (n log n) total time - because if you could, then you could sort an array in better than O (n log n) time.

If we define a "sorted" data structure as any data structure that can be enumerated in sorted order in O (n) time, then we can't create any sorted data structure faster than in O (n log n). That would include sorted trees, both balanced and unbalanced.