Quiz

Red-Black Tree Rules

Each node is either red or black
The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
All Nil leaf nodes are black.
If a node is red, then both its children are black.
All paths from a single node go through the same number of black nodes in order to reach any of its descendant NIL nodes.