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$
  • $\begingroup$ Have a close look at the definition. $\endgroup$ – Raphael Oct 28 '12 at 10:56
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, privacy policy and cookie policy

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