Data Structures

Question 1

What conditions must a red-black tree satisfy?

Answer 1

1) Nodes are either red or black
2) The root is black (optional)
3) All leaves (NIL) are black, i.e. the same color as the root
4) Every red node must have two black child nodes, and therefore must have a black parent
5) Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.