2
$\begingroup$

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}$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.