How balanced is a binary tree in the average case?

Question

For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's a generalization, but it's also a reasonable one.

But in real algorithms, we're typically not interested in the rare worst case performance, much less the best case performance. Rather, we're interested in how the algorithm performs in typical use. This begs an interesting (and useful) question: How balanced is a binary tree on average? Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

Answer 1

Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

To be a bit stereotypical: yes. There are reasonable ways to approach the problem, but it's so dependent on use case that you will need to take a look at how your particular algorithm builds binary trees to get information about your algorithm.

More specifically: you ask about the 'average' balance of a binary tree, but you can't have an average without a probability distribution on the set of binary trees. There are (infinitely) many different probability distributions, and different algorithms for generating trees will lead to different distributions on the set of trees generated.

For example, since the number of binary trees on $n$ nodes is finite, we can talk about the uniform distribution where we consider every binary tree equally probable, and ask what the average balance is there. For concreteness, I'm going to use height as a measure of the balance of a tree, because it's easy and well-studied, but note that there are plenty of other metrics you could measure by: maximal ratio between subtree sizes, for instance, would be another reasonable one. Looked at over the uniform distribution of $n$-node binary trees, the average height is proportional to $\sqrt{n}$, (almost) 'right between' the two extremes.

But very few algorithms would lead to a uniform distribution on binary trees. As an example of a more reasonable distribution, we could choose a permutation uniformly at random from the $n!$ permutations on $\{1\ldots n\}$ and then build a binary tree by inserting nodes labeled $1$ through $n$ into a tree in the given order. It can be shown that this process yields a tree with average height proportional to $\log n$, so trees generated in natural fashion from random data are generally 'pretty good'.

Answer 2

Most of the time when binary trees are used, we first create in a way we define; heap, B+ tree, 2-3 tree and etc. So, the probability of being a balanced tree also depends on the tree building algorithm. for example, a list of length 2^n -1 convert into heap definitely give a balanced tree.
Just a thought.

Answer 3

You can't really talk about "average", only about "average for my use case". For example, assume I have a sorted array, and I turn it into a tree by starting with an empty tree, and adding the items in the order they are in the array.

In that case, a trivial algorithm doing no re-balancing ends up with a tree of height n. Or my data might come from some external source which might be sorted, or mostly sorted. I would say that a case where you insert items in random order is actually quite unusual.