Red Black Tree in Data Structure

Red-Black Trees are balanced binary search trees where nodes are colored red or black. This color scheme ensures O(log n) time complexity for search, insert, and delete operations. They self-balance, adapting to changes, making them efficient for managing large datasets. Simple rules govern their structure, ensuring fast searching, sorting, and data management.

Properties of Red Black Tree

In addition to the standard properties of a binary search tree, Red-Black Trees have specific rules:

1. Internal Property: If a node is red, its parent must be black.
2. Depth Property: All leaves have the same depth of black nodes.
3. Path Property: Equal black node count along root-to-leaf paths.
4. Root Property: The top node is always black.
5. External Property: All leaf nodes are black.

Rules That Every Red-Black Tree Follows

1. Coloring Rule: Each node is either red or black.
2. Root Rule: The root node is black.
3. Red Constraint: No parent-child pair can have both nodes red.
4. Uniform Black Depth: Every path from a node to its descendant leaves has the same count of black nodes.
5. Leaf Color: All leaf nodes are black.

Why Red-Black Trees?

In binary search trees (BSTs), operations like search, insertion, and deletion usually have a time complexity of O(h), height-dependent. Red-Black Trees ensure O(log n) time complexity for all operations, maintaining efficiency regardless of initial shape. Their self-adjusting mechanism prevents skewing, providing stable performance suitable for tasks needing fast search, insertions, and deletions, making them versatile for diverse applications.

The time complexity for Search, Insert and Delete operations in Red-Black Tree is O(logn).

Comparison With AVL Tree

AVL trees prioritize balance but can undergo more rotations during changes, impacting performance. Red-Black Trees are preferred for frequent data changes due to efficient self-balancing, reducing rotation overhead. AVL suits less dynamic data with frequent searches, while Red-Black Trees prioritize efficiency over strict balance, ideal for frequent insertions and deletions.

Operations of Red-Black Trees

Red-Black Trees support below fundamental operations:

1. Insertion: Adding new elements while maintaining balance.
2. Deletion: Removing elements while preserving tree properties.
3. Search: Finding elements efficiently within the tree.

Insertion in Red-Black Tree

Following are the steps to insert a node in the red-black tree:

1. Check if the tree is empty: If it is, make the new element the root and color it black.
2. If the tree isn't empty:
   • Create a new node and color it red.
   • Check if the new node's parent is black; if so, we're done.
   • If the parent is red:
     • Check the color of the parent's sibling.
     • If the sibling is black or doesn't exist, perform a rotation and adjust colors.
     • If the sibling is red, recolor the parent, sibling, and grandparent nodes (unless the grandparent is the root, then just recolor parent and sibling).

This process ensures the Red-Black Tree remains balanced and maintains its properties.

Example:

Constructing an R-B tree for the first 8 integers to understand the whole process:

Insert 2: When you add the very first piece of data to an empty Red-Black Tree, that data becomes the root, and it's automatically marked as black.

Insert 6: As the tree already contains nodes, we add a new node with the next integer, coloring it red. This addition ensures that both the binary search tree and Red-Black Tree properties are maintained. We proceed with adding more nodes without violating these rules.

Insert 11: Since the tree isn't empty, we add a new node with the next integer, coloring it red. However, the parent of the new node isn't black, which violates the rules of both the binary search tree and Red-Black Tree.

As the sibling of the parent is null, we perform a rotation and recolor the initial parent and grandparent of the nodes to restore balance. Recoloring means interchanging the color i.e. if it is red then turn it to black and vice versa.

Insert 17:

Once again, the Red-Black Tree balance property is violated. We examine the color of the parent's sibling node, which is red. To restore balance, we simply recolor the parent and the sibling nodes.

Insert 22: Inserting the element 5 causes another violation of the Red-Black Tree balance property.

As the sibling node is null, we perform a rotation and adjust colors to restore balance.

Insert 30: Inserting element 6 leads to a violation of the Red-Black Tree property, requiring the application of one of the insertion cases.

As the parent's sibling is red, we recolor the parent, its sibling, and the grandparent nodes, unless the grandparent is the root.

Insert 49: This again violates the rule.

Since the parent's sibling is null, we perform the appropriate rotation, which in this case is a right-right (RR) rotation and recolor the parent and grandparent node.

Insert 58:

Inserting 58 results in violation of the rule.

The parent node's sibling is red so we recolor sibling, parent and grandparent node.

But the problem in above orientation is that two adjacent nodes have red color which violates the property (node 17 and node 30). Since, the node 30 is in trouble, so we check the color of sibling parent's node (i.e. node 2). Node 2 is black, so we apply the RR rotation on (6-17-30) and recolor the node 6 and node 17 as per the rule. Hence, the final tree will become like below:

Deletion in Red Black Tree

To ensure the Red-Black Tree properties are preserved during deletion, follow these steps:

1. Initial Deletion:

   • Delete the node based on binary search tree rules.
   • If the deleted node or its parent is red, simply remove it.
   • If the deleted node is a black leaf, creating a double black situation, proceed to handle it.

2. Double Black Handling:

   • If the double black's sibling and its children are black, recolor parent to black, sibling to red, and handle potential double black at parent.
   • If the sibling is red, swap colors of parent and sibling, rotate parent towards double black, and continue with other cases if needed.
   • If the sibling's closer child is red, swap colors of sibling and that child, rotate sibling away from double black, and proceed to below case.
   • If the farther child is red, swap colors of parent and sibling, rotate parent towards double black, remove double black, and adjust colors.

These steps ensure that after deletion, both the binary search tree and Red-Black Tree properties are maintained, preserving the integrity and balance of the tree.

Example:

Consider the below tree:

1. Delete 17: Perform binary search deletion first.

After completing the binary search tree deletion, the Red-Black Tree properties remain intact, so the tree remains unchanged.

2. Delete 22:

Following the binary search tree deletion, the Red-Black Tree properties are violated as the paths no longer contain the same number of black nodes. To restore balance, we adjust the colors of nodes accordingly.

3. Delete 11: After executing the binary search deletion, we remove node 3 as it's a leaf node. This deletion results in a situation where the node 3 being black, leaves a double black node in its place.

We address case 3 deletion since the double black's sibling node is black, and its children are also black. In this scenario, we remove the double black node and adjust the colors of its parent and sibling accordingly.

All target nodes have been successfully deleted while ensuring that the Red-Black Tree properties are maintained throughout the process.

Searching in a Red Black Tree

Searching in a Red-Black Tree uses a similar algorithm to that of a binary search tree. It involves traversing the tree and comparing each node's value with the key element being searched. If the element is found, a successful search is returned. Otherwise, an unsuccessful search is returned.

Code Implementation

C++:

Java:

Python:

Output:

Complexity Analysis of Red Black Tree

Time Complexity

The time complexity for search, insert, and delete operations in a Red-Black Tree are all O(log n), where n specifies the number of nodes in the tree.

Space Complexity

It has the space complexity of O(n), where n denotes the number of nodes in the tree.

Applications of Red Black Tree

1. Common libraries and data structures like maps and sets in C++, as well as Java's TreeMap and TreeSet, use Red-Black Trees for efficient searching and sorting.
2. Operating systems like Linux employ Red-Black Trees in the CPU scheduling algorithm, such as the Completely Fair Scheduler.
3. In machine learning, Red-Black Trees are utilized in algorithms like K-means clustering to reduce time complexity.
4. MySQL utilizes Red-Black Trees for indexing tables, enhancing search and insertion efficiency.
5. Widely used programming languages such as Java, C++, and Python integrate Red-Black Trees as a built-in data structure for effective data searching and sorting.
6. Graph algorithms like Dijkstra’s shortest path and Prim’s minimum spanning tree rely on Red-Black Trees for efficient implementation.

Advantages of Red Black Tree

1. Red Black Trees ensure fast operations like insertion, deletion, and searching with a guaranteed time complexity of O(log n).
2. They automatically balance themselves, ensuring efficient performance without manual intervention.
3. Red Black Trees find use in various applications due to their reliable performance and adaptability.
4. The method for balancing Red Black Trees is straightforward and easy to grasp, enhancing their practicality.

Disadvantages of Red Black Tree

1. Each node in a Red Black Tree requires an additional bit of storage to store its color (red or black).
2. Implementing Red Black Trees may involve some complexity due to the need for managing node colors and ensuring balanced tree structure.
3. While Red Black Trees offer efficient performance for common operations, they might not always be the optimal choice for every type of data or specific scenarios.