Red Black Trees

The Following Are Notes on Understanding Red Black Trees, a special category of Binary Search Trees that ensure the tree stays Balanced. In other words, Red Black Trees ensure that the height of the tree is always O(log n) where n is the number of nodes in the tree. This is important because it ensures that the time complexity of operations like search, insert, and delete are O(log n) which is the best time complexity we can achieve for these operations in a Binary Search Tree.

For this, we assume you have a solid understanding of Binary Search Trees, check the reference for a refresher:

For more information on Binary Search Trees

Time Complexities of BST Operations

Where N is the number of Nodes

• Search: O(logN)
• Insert: O(logN)
• Deletion: O(logN)

Red Black Trees Properties

• Every Node is either Red or Black
• The Root Node is Black
• Red Nodes can't have Red Children
• Null Children are Black
• Every path from a Root to a Null Child has the Same Number of Black Nodes (Black Height of the Tree)

Insertion Into a Red Black Tree

Steps for Insertion:

1. Insert Using BST Insertion Algorithm
2. The New Node is Colored Red
3. Check for RBT Properties (see next step)

Fixing RBT Properties:

1. If the Parent of the New Node is Black, then the Tree is still a valid RBT
2. If the Root Red, then we can make it Black and still maintain all Red Black Tree Properties
3. If the Parent of the New Node is Red, then we have a violation of the RBT Properties
4. There are 2 cases to consider for fixing the RBT Properties

1. Aunt of the New Node is Red



2. Aunt of the New Node is Black (or null)

Deletion from a Red Black Tree

Steps for Deletion:

1. Delete Using BST Deletion Algorithm
2. Check for RBT Properties (see next step)

Fixing RBT Properties:

1. IF Deleted Node is BLACK, and replacement is RED, turn Replacement BLACK
2. For Black Nodes without Red Replacements are 3 cases to consider for fixing the RBT Properties