A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes

Let us call a red-black tree strict when every black node has at most one red child.

Show that a strict red-black full tree has at most $$(n − 1)/4$$ red nodes; a binary tree is full when every node has zero or two children.

The hint for this problem says to use a charging argument but I can't seem to figure one out.

My idea was to consider the root of the tree (which must be black) and recursively consider the number of red nodes in the left and right subtrees and show by induction that this holds. But I can't seem to figure out some of the details (and there seem to be some inconsistencies).

• The hard part of proving recursively is when a node has a red child. In that case, that red child must have a black sibling and two black children. Consider the subtree rooted at the left-child of that red child, the subtree rooted at the right-child of that red child, and the subtree rooted at the black sibling. Note that each of them is a strict red-black full tree with black root. Commented May 26, 2022 at 17:39

Deposit 3 dollars on each red nodes initially.

For each black node, if it is a sibling or a child of a red node, move one dollar on that red node onto the black node.

Claim 1: there is at most one dollar on each black node. There is no dollar on the root of the tree.

Claim 2: there is no dollar on red nodes.

The total amount of dollars was $$3\times\#\text{red nodes}$$ initially. The total amount of dollars at the end is at most $$\#\text{black nodes} - 1$$. $$3\times\#\text{red nodes} \le \#\text{black nodes} - 1$$ which means $$4\times\#\text{red nodes} \le (\#\text{black nodes} + \#\text{red nodes}) - 1=\#\text{all nodes}-1$$.

I will let you prove the two claims.

• Hey I've been thinking about this and I can't seem to prove claim 2? Wouldn't a red node still have a dollar if it either has less than 2 children or has no siblings? Commented Jun 4, 2022 at 21:27
• Please come to chat with me. Commented Jun 4, 2022 at 22:07