# Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.

Of course, when we talk about red-black trees*(see definition at the end) being balanced, we actually mean that they are height balanced and in that sense, they are balanced.

Suppose we try to formalize the above intuition as follows:

Definition: A Binary Tree is called $$\mu$$-balanced, with $$0 \le \mu \leq \frac{1}{2}$$, if for every node $$N$$, the inequality

$$\mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$$

holds and for every $$\mu' \gt \mu$$, there is some node for which the above statement fails. $$|N_L|$$ is the number of nodes in the left sub-tree of $$N$$ and $$|N|$$ is the number of nodes under the tree with $$N$$ as root (including the root).

I believe, these are called weight-balanced trees in some of the literature on this topic.

One can show that if a binary tree with $$n$$ nodes is $$\mu$$-balanced (for a constant $$\mu \gt 0$$), then the height of the tree is $$\mathcal{O}(\log n)$$, thus maintaining the nice search properties.

So the question is:

Is there some $$\mu \gt 0$$ such that every big enough red-black tree is $$\mu$$-balanced?

The definition of Red-Black trees we use (from Introduction to Algorithms by Cormen et al):

A binary search tree, where each node is coloured either red or black and

• The root is black
• All NULL nodes are black
• If a node is red, then both its children are black.
• For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Note: we don't count the NULL nodes in the definition of $$\mu$$-balanced above. (Though I believe it does not matter if we do).

• @Aryabhata: what's with the uniqueness ($\mu'>\mu$) in your edit? I'm fine with the fact that $\frac13$-balanced implies $\frac14$-balanced. I don't think you should have to find the exact $\mu$ to prove height is $O(\log n)$. Am I missing something? – jmad Mar 14 '12 at 12:34
• Furthermore, you require a negative statement to provide a counterexample chain with one tree for every $n \in \mathbb{N}$. Any infinite chain that is non-decreasing in node size would be sufficient, wouldn't it? – Raphael Mar 14 '12 at 14:03
• @jmad: Without the $\mu'$ edit, every tree is trivially $0$-balanced and so we have a trivial no answer to the question. I wanted to avoid that. – Aryabhata Mar 14 '12 at 14:07
• @Raphael: I don't understand. The node size of the $n^{th}$ tree is $n$. You are saying it does not matter what tree we pick for $RB_n$ and that $\mu_n \to 0$? Does not seem obvious to me, and that is what the question is about! – Aryabhata Mar 14 '12 at 14:13
• An earlier version of this question claimed that the runtime of a recursive algorithm on a red-black tree which does linear amount of work at each step is not necessarily $O(n\log n)$. This claim was incorrect; height-balance implies that the depth of an $n$-node red-black tree is $O(\log n)$. Thus, if you perform $O(n)$ work at each level of the tree, the total work is $O(n \log n)$. – JeffE Mar 14 '12 at 14:48

Claim: Red-black trees can be arbitrarily un-$$\mu$$-balanced.

Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $$k$$ of black nodes on every root-leaf path.

Proof: Define a sequence $$T_k$$ of red-black trees so that $$T_k$$ has $$k$$ black nodes on every path from the root to any (virtual) leaf. Define $$T_k = B(L_k, R_k)$$ with

• $$R_k$$ the complete tree of height $$2k - 1$$ with the first, third, ... level colored red, the others black, and
• $$L_k$$ the complete tree of height $$k-1$$ with all nodes colored black.

Clearly, all $$T_k$$ are red-black trees.

For example, these are $$T_1$$, $$T_2$$ and $$T_3$$, respectively:

[source]

[source]

[source]

Now let us verify the visual impression of the right side being huge compared to the left. I will not count virtual leaves; they do not impact the result.

The left subtree of $$T_k$$ is complete and always has height $$k-1$$ and therefore contains $$2^k - 1$$ nodes. The right subtree, on the other hand, is complete and has height $$2k - 1$$ and thusly contains $$2^{2k}-1$$ nodes. Now the $$\mu$$-balance value for the root is

$$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$$

which proves that there is no $$\mu > 0$$ as requested.

No. Consider a red-black tree with the following special structure.

• The left subtree is a complete binary tree with depth $d$, in which every node is black.
• The right subtree is a complete binary tree with depth $2d$, in which every node at odd depth is red, and every node at even depth is black.

It's straightforward to check that this is a valid red-black tree. But the number of nodes in the right subtree ($2^{2d+1}-1$) is roughly the square of the number of nodes in the left subtree ($2^{d+1}-1$).

• +1: Thanks! But the number of nodes is of the from $2^{2d+1} + 2^{d+1} - 1$. Can we perhaps 'pad' these sufficiently to get a tree a given size $n$? (It looks like that should be do-able). – Aryabhata Mar 14 '12 at 15:03
• You already have a counterexample for infinitely many $n$, so why bother?. But I suppose if you wanted to, you could add more red nodes to the left subtree, or take some red nodes out of the right subtree. – JeffE Mar 14 '12 at 15:05
• @JeffE: Basically the counterexample chain would then be a 'dense' subset, rather than a 'sparse' subset. Perhaps I will change the formulation of the question. – Aryabhata Mar 14 '12 at 15:08