[Solved]: Can you have three consecutive black nodes in red-black search tree?

Problem Detail: 

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?

Asked By : user1675999

Answered By : Hendrik Jan

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6343

3.2K people like this

 Download Related Notes/Documents