0
$\begingroup$

To prove this, Introduction to Algorithms by Cormen et al., makes the assumption that the node has two children.

For the inductive step, consider a node $x$ that has positive height and is an internal node with two children. Each child has a black-height of either $bh(x)$ or $bh(x) - 1$, depending on whether its color is red or black, respectively. Since the height of a child of $x$ is less than the height of $x$ itself, we can apply the inductive hypothesis to conclude that each child has at least $2^{bh(x) - 1} - 1$ internal nodes. Thus, the subtree rooted at x contains at least $(2^{bh(x) - 1} - 1) + (2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$ internal nodes, which proves the claim.

How does this extend to red black trees in general? The author defined red black trees using these five properties, none of which stops a black node from having only one child.

A red-black tree is a binary tree that satisfies the following red-black properties:

  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.
$\endgroup$

1 Answer 1

1
$\begingroup$

You can check your reference, but every internal node (node with assigned key), with no internal child/children is by default has leaf node (NIL) as child/children.

$\endgroup$
1
  • $\begingroup$ Correct, in that case the black height would be 1 through the path to NIL, and consequently in general. Thus, the number of internal nodes has to be $2^1 - 1 = 1$, which holds true. $\endgroup$
    – ihsingh2
    Apr 9, 2023 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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