Red-Black Trees

Valid Red-Black Trees have the following properties

• Each node is either red or black
• The root node is black
• No red nodes have red children
• All paths from the root to a null child have the same number of black nodes

Insertion Algorithm

Deletion Algorithm