Not all Red-Black trees are balanced?

Problem Detail: 

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

Asked By : Aryabhata

Answered By : Raphael

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/342