Red-Black Trees

Red-Black trees are self balancing binary search trees

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

1. Use the BST insertion algorithm to insert new node as a red node
2. If there's a property violation, fix the tree using one of the cases depicted below

3. Validate the tree is valid if required by fix