1. Every node is red or black
2. Root is always black
3. Red nodes have black children
4. All paths have equal black nodes