Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma has been made that red-black trees with $n$ internal nodes have height at most $2\log(n+1)$, would this proof still hold for such a black tree?
$\begingroup$
$\endgroup$
1
asked Oct 27, 2012 at 23:52
-
$\begingroup$ Have a close look at the definition. $\endgroup$– Raphael ♦Oct 28, 2012 at 10:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.
answered Oct 28, 2012 at 0:32