Subtree rooted at any node x contains at least 2bh(x)-1 internal nodes Proof (induction on the height of x): ·Base: If the height of x is 0,then x must be a leaf(T.nil),and the subtree rooted at x indeed contains at least 20-1=0 internal nodes 。Induction: Suppose x 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 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 2bh(x)-1-1 internal nodes. Thus,the subtree rooted at x contains at least(2bh(x)-1-1)+(2bh(x)-1-1)+1=2bh(x)-1 internal nodes• Proof (induction on the height of x): • Base: • If the height of x is 0, then x must be a leaf (T.nil), and the subtree rooted at x indeed contains at least 20 -1 = 0 internal nodes • Induction: • Suppose x 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 • 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 2bh(x)-1 -1 internal nodes. • Thus, the subtree rooted at x contains at least (2bh(x)-1 -1)+ (2bh(x)-1 -1)+1=2bh(x) -1 internal nodes Subtree rooted at any node x contains at least 2bh(x) -1 internal nodes