I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{3n}{4}$?
2
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
Here is a natural approach to explore the extreme case.
Let node $r$ be the root of a red-black tree.
Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height.
Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of the nodes among red-black tree of the same black height.
Now let $h=1,2,3,\cdots$ be larger and larger. Can you see the trend?
Here is a related exercise.
Exercise (red-black trees may not be weight-balanced). Given $\alpha\lt 1$, show that there is a red-black tree which has a proper subtree that has more than $\alpha$ of all nodes.
