Red Black Tree

Red Black Tree Properties

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

Red Black Tree Insertions Steps

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

Restore Steps

• Reparing a Red Root: switch it to black without violating any other property
• Repairing a Red Node with Red Child
• if aunt is black(or null): rotate and color swap
• if aunt is red: recolor