Rules of Red Black Tree

• Every node is either red or black
• The root node is always black
• If a node is red, then both its children are black
• Every simple path from a node to a descendant leaf contains the same number of black nodes

Example Picture of a Valid Red Black Tree

For more information, go to this webpage!