Question on the properties of red black trees

Question

Problem statement

Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the right subtree of $u$, before the properties of the red black tree are broken?

Attempt at a solution

I was given the answer $O(n^2)$ (past exam sheet question with the answer marked). However, I don't think it's correct, unless I have misunderstood the problem.

According to CLRS the properties of a red black tree are the following:

1. Every node is either red or black
2. The root is black
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Since we are in some internal node $u$, from the properties we infer that all simple paths starting from $u$ and ending in some leaf, should contain the same number of black nodes.

We are given that in the left subtree of $u$ we have $n$ nodes, and our goal is to maximize the number of nodes that we have in the right subtree. It seems natural to assume that the left subtree is a chain containing $n$ black nodes, because in this way, we can make the right subtree of $u$ be a complete binary tree, where every simple path starting from the root of the subtree and ending in some leaf contains exactly $n$ black nodes. And not only that, we can also in the end add red levels of nodes in between black levels, thus increasing the size of the right subtree by 2.

Reducing the black height of the left subtree, will only imply fewer nodes in the right subtree.

So lets find the number of nodes in the right subtree. Essentially we have a complete binary tree of height $n$, so the number of nodes will be:

$S = \sum_{i=0}^{n-1}2^n$

$-2S = \sum_{i=1}^{n}2^n$

$S(1-2) = 1 - 2^n$

$S = 2^n - 1$

so the answer is $O(2^n)$. Am I wrong or was there a typo in the exam sheet?

Answer 1

The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties.

In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, while the right subtree is a full maximal binary tree of height $2\log n$.

The black height of the right subtree must be $\log n$ as well, therefore its maximal total height (including red nodes) is $2\log n$. Since it is a maximal binary tree, it has $ 2^{2\log n} = 2^{\log n^2} = n^2 $ nodes.