Red-Black Tree

Properties of a Red-Black Tree

• Each node is either red or black.
• The root node is black.
• No red nodes have red children.
• Every path from root to a null child has the same number of black nodes.
• Null children are black.

Inserting into a Red-Black Tree

1. Insert the new key using the BST insertion algorithm.
2. Color the new node red.
3. Check and restore Red-Black tree properties if necessary.

Example of Red-Black Tree

For more information, refer to Introduction to Red-Black Tree.