1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Have a close look at the definition. $\endgroup$
    – Raphael
    Oct 28, 2012 at 10:56

1 Answer 1

6
$\begingroup$

In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.

$\endgroup$

Your Answer

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

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