Not all Red-Black trees are balanced?
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 &gt; 0$ as requested.