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:
- Every node is either red or black
- The root is black
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- 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?