While learning advanced Data Structures, one of the most important steps that you might have come across is the Red-Black Tree. It is basically a self-balancing binary search tree that helps to ensure that the height of the tree stays balanced even when you are performing multiple insertions and deletions. If you don’t know how to perform balancing in binary search trees, operations like searching, insertion, and deletion may become slow. This is where you can use the Red-Black Tree.
In this blog, we will discuss everything about Red-Black Trees, from their properties to operations like insertion, deletion, and searching. So let’s get started.
Table of Contents
What is a Red-Black Tree?
A Red-Black tree is a special type of binary search tree that is balanced, where each node is colored either red or black. These colors are not just for appearance; they help the tree stay balanced automatically. Because of this balance, the tree can perform search, insert, and delete operations in O(log n) time, even while handling large amounts of data.
The Red-Black tree is flexible and changes itself each time there is a change, hence it is very efficient in handling large datasets. It follows a few simple rules about how nodes should be colored and arranged, and these rules ensure that searching, sorting, and managing data are always fast and efficient.
Properties of Red-Black Tree
Other than the normal rules of a binary search tree, a Red-Black tree consists of some extra rules that help to keep it balanced:
1. Internal Property: If a node is red, then its parent must always be black. Two red nodes cannot be next to each other.
2. Depth Property: Every path from the root to any leaf (NULL node) must contain the same number of black nodes.
3. Path Property: Regardless of the route that you choose between the root and the leaf, the number of black nodes will be the same.
4. Root Property: The top node (root) of the tree is always black in color.
5. External Rule: All the leaf nodes of the tree (NULL or NIL nodes) are always black in color.
Example of Red-Black Tree:
In the correct Red-Black tree, every path from the root to any leaf has the same number of black nodes. In this example, each path has one black node (not counting the root).
In the incorrect Red-Black tree, the rules are broken in two ways:
1. Two red nodes are placed next to each other, which is not allowed.
2. The paths from the root to the leaves do not have the same number of black nodes. One path has zero black nodes, while the others have one.
Why Red-Black Trees
In a normal binary search tree (BST), various operations like search, insert, delete, finding the maximum, or the minimum usually take time depending on the height of the tree, denoted as O(h). But if the tree becomes skewed (like a linked list), the height can grow too much, and these operations may take O(n) time, which is very slow.
In order to avoid this, you have to make sure that the height of the tree is close to O(log n) after insertion and deletion of every value. In this way, you can ensure that all the operations are fast, with a maximum time complexity of O(log n). A Red-Black tree always keeps its height as O(log n), no matter how many nodes it has. This makes it more efficient.
| Algorithm |
Time Complexity |
| Search |
O(log n) |
| Insert |
O(log n) |
| Delete |
O(log n) |
Comparison with AVL Tree
The comparison between Red-Black Tree and AVL Tree is given below in a tabular format:
| Feature |
AVL Tree |
Red-Black Tree |
| Balance |
More strictly balanced |
Less strictly balanced |
| Rotations |
Needs more rotations during insert/delete |
Needs fewer rotations |
| Search Performance |
Faster for searches (due to stricter balance) |
Slightly slower than AVL |
| Insertion/Deletion |
Slower (extra rotations make it costly) |
Faster and more efficient |
| Best Use Case |
When data changes rarely, but searching happens a lot |
When data changes frequently (insertions & deletions) |
| Height |
Closer to log(n), very tightly balanced |
Height is at most 2 × log(n), still balanced |
| Complexity |
Search, Insert, Delete = O(log n) |
Search, Insert, Delete = O(log n) |
Operations of Red-Black Trees
A Red-Black tree allows you to do three main operations:
- Insertion: In a Red-black tree, you can add new elements. It will automatically adjust itself with the new elements and stay balanced.
- Deletion: You can also remove elements from the tree, and it will fix itself to keep all the rules intact.
- Rotation: A rotation in a Red-Black tree is a restructuring operation that helps restore balance after insertion or deletion.
Insertion in Red-Black Tree
Given below are the steps to insert a node in the Red-Black tree:
1. Check if the tree is empty: If the tree is empty, you have to make the new element the root and color it black.
2. If the tree is not empty: If the tree is not empty, you have to create a new node and then color it red. If the parent element of the new node is black, the job is done as no rules are broken.
3. If the parent is red: When inserting a new node in a Red-Black tree, you need to check the parent’s sibling, which is also called the “uncle.” If the uncle is black or doesn’t exist, you have to fix the tree by performing a rotation and adjusting the colors. But if the uncle is red, then you simply change the colors: make the parent and the uncle black, and the grandparent red. However, if the grandparent happens to be the root, then you only recolor the parent and the uncle to black. This way, the Red-Black tree remains balanced and its rules are preserved.
This step-by-step process helps to ensure that the Red-Black tree always stays balanced and continues to follow the rules after every insertion.
Example:
Given below is a step-by-step process that shows how insertion works in a Reb-Black Tree.
Step 1: Insert 2
When you insert the first element into an empty Red-Black tree, it becomes the root node, and the root is always colored black by default.
Step 2: Insert 6
If the red-black tree already consists of some nodes, you have to add the new node (with the next value) and then color it red. This way, the rules of both the binary search tree and the Red-Black tree stay valid. You can continue to add more nodes as long as you follow these rules, and the tree will be balanced.
Step 3: Insert 11
Since the Red-Black tree is not empty, you add the new node with the next value and color it red. But if the parent of this new node is also red, it breaks the rules of the Red-Black tree (because two red nodes cannot be next to each other).
If the parent’s sibling (the uncle) is not there, you fix the Red-Black tree by doing a rotation. After that, you change the colors of the parent and the grandparent to bring the tree back into balance. Recoloring simply means swapping colors; if a node is red, you turn it black, and if it is black, you turn it red.
Step 4: Insert 17
Again, the balance rules of the Red-Black tree are broken. This time, when you check the parent’s sibling (the uncle), it is red. To fix this, you don’t need any rotation; you just have to recolor the parent and the uncle to restore balance.
Step 5: Insert 22
When you insert the 5th element into the Red-Black tree, it breaks the balance rules again, causing another violation that needs to be fixed.
Since the sibling node (uncle) is missing, you fix the Red-Black tree by doing a rotation and then changing the colors of the nodes to bring the tree back into balance.
Step 6: Insert 30
When you insert element 30 into the Red-Black tree, it breaks one of the tree’s rules. To fix this, you need to apply one of the special insertion cases (like rotation or recoloring) to bring the tree back into balance.
When the parent’s sibling (the uncle) is red, you fix the Red-Black tree by changing colors. You turn the parent and the uncle black, and the grandparent red. But if the grandparent is the root, then you only recolor the parent and the uncle.
Step 7: Insert 49
ChatGPT said:
This insertion breaks the rules of the Red-Black Tree.
Since the parent’s sibling (the uncle) doesn’t exist, you fix the Red-Black tree by doing a rotation. In this case, it’s a right-right (RR) rotation. After the rotation, you also change the colors of the parent and the grandparent to restore balance.
Step 8: Insert 58
Inserting 58 violates the rule of the Red-Black tree.
When the parent’s sibling (the uncle) is red, you fix the Red-Black tree by changing colors. You recolor the parent, the uncle, and the grandparent to maintain balance.
In the above tree, there’s a problem because two connected nodes (17 and 30) are both red, which breaks the Red-Black tree rule. Since node 30 is causing the issue, we look at the color of the parent’s sibling (node 2). Node 2 is black, so to fix this, we perform a right-right (RR) rotation on the nodes 6, 17, and 30. After the rotation, we recolor nodes 6 and 17 according to the rules. This gives us the correct balanced tree.
Get 100% Hike!
Master Most in Demand Skills Now!
Deletion in Red-Black Tree
To keep the Red-Black tree rules intact while deleting a node, you just need to follow some steps that make sure the tree stays balanced.
1. Initial Deletion
- First, delete the node using the normal binary search tree (BST) rules.
- If the deleted node or its parent is red, just remove it.
- But if the deleted node is a black leaf, this creates an extra problem called double black, which you need to fix.
2. Double Black Handling
Case 1: If the sibling and both of the sibling’s children are black, make the parent black, sibling red, and if needed, handle double black at the parent.
Case 2: If the sibling is red, you have to swap the colors of the parent and sibling, rotate the parent toward the double black, and then continue checking other cases.
Case 3: If the sibling’s closer child is red, you have to swap the colors of the sibling and that child, rotate the sibling away from the double black, and move to the next case.
Case 4: If the sibling’s father child is red, you have to swap the colors of the parent and sibling, rotate the parent toward the double black, remove the double black, and fix colors as needed.
By following these steps, the tree will still follow both the binary search tree rules and the red-black tree rules, which keep the tree balanced and working properly even after deletion.
Example:
Consider the tree given below:
Step 1: Delete 17
At first, you need to perform binary search deletion first.
Once you delete a node using the normal BST rules, if the Red-Black Tree rules are still fine, then you don’t need to do anything else; the tree stays the same.
Step 2: Delete 22
After deleting a node, the Red-Black Tree rules might break because some paths may not have the same number of black nodes. To fix this imbalance, you have to change the colors of certain nodes to restore the balance of the tree.
Step 3: Delete 11
After deleting node 11, which is a leaf, since it was black, its removal leaves behind an extra black called a double black at its position.
In this case, the double black’s sibling and its children are all black. So, we fix the problem by removing the double black and changing the colors of the parent and sibling to keep the tree balanced.
All the nodes that you wanted to be deleted have been removed, and the Red-Black Tree rules were followed at every step, so the tree stays balanced and correct.
Searching in Red-Black Tree
Finding a node in a Red-Black Tree works in the same way as in a normal Binary Search Tree. You have to start from the root node and keep moving down the tree. At each step, you have to compare the value with the value that you are looking for. If the value is smaller than the current node value, you have to go left, and if it is bigger, you have to go right. This goes on until you either find the value or reach the end of the tree.
Search Steps:
1. You have to start from the root node of the tree.
2. If the value of the root is equal to the target value, you have found it.
3. If the target value is smaller than the current node’s value, you have to move to the left child.
4. If the target value is larger than the current node’s value, you have to move to the right child.
5. You have to keep repeating steps 2 to 4 until you get the desired value, or you have reached an empty spot (value not found).
Code Implementation of Red-Black Tree
The code implementation of the Red-Black Tree in Data Structure is given below in C++, Java, and Python.
Code: C++
Output:
Explanation:
This C++ program creates a Red-Black Tree, which is basically a smarter version of a normal binary search tree. Every node has a number and a color (either red or black). When you add a new number, it first goes in like a regular tree, but then the tree automatically fixes itself if something looks wrong, like two red nodes in a row. It does this by rearranging nodes (rotations) or changing colors so the tree stays balanced. Because of this, searching for numbers is always quick. The program also lets you print the tree with colors and check if a number exists. In simple terms, it’s a self-organizing tree that keeps things neat and efficient.
Code: Java
Output:
Explanation:
This Java code creates a Red-Black Tree, which is a self-balancing type of Binary Search Tree. In this case, each node will be red or black. The tree is self-balancing and will automatically adjust itself when you add a new value, through colors and rotations. The code lets you insert numbers, look for specific values, and print the tree in order (showing numbers in sorted sequence along with their colors). In the main part, a few numbers are added, the tree is displayed, and a search is carried out to show how it works.
Code: Python
Output:
Explanation:
The Python code builds a Red-Black Tree, which is a type of balanced Binary Search Tree. Each node is either red or black in color. When you add a new value to the tree, it adjusts itself using coloring and rotations so that it stays balanced. The code supports inserting values, searching for values, and performing an in-order traversal (which shows the values in sorted order along with their colors). The main section adds some numbers to the tree, prints them out, and shows how searching works.
Complexity Analysis of Red-Black Tree
Time Complexity
In a Red-Black Tree, the time it takes to search, insert, or delete a value grows slowly, even if the tree gets very big. All these operations take about O(log n) time, which means the execution time increases only in proportion to the height of the tree, not the total number of nodes. This makes the Red-Black Tree efficient even when a large amount of data is stored.
Space Complexity
A Red-Black Tree needs O(n) space, which means the memory it uses grows in direct proportion to the number of nodes in the tree. So, if there are more nodes, it simply takes more space to store them.
Applications of Red-Black Tree
1. Databases: They are used in databases to keep data sorted so that searching, inserting, and deleting records is always fast.
2. File Systems: Nowadays, many file systems use Red-Black Trees to manage files and directories in an efficient way.
3. Programming libraries: In languages like C++, Red-Black Trees are used in map and set to keep data in sorted order.
4. Networking: They help in routing tables where quick lookup and updates are needed.
5. Memory management: Red-Black trees are used by operating systems to help keep track of free and used memory blocks.
Advantages of Red-Black Tree
Given below are 5 advantages of the Red-Black Tree:
1. Always balanced: Red-Black trees ensure that the trees not very tall. This helps the operations to stay fast.
2. Fast Operations: Searching, inserting, and deleting have the same time complexity in a Red-Black Tree, which is O(log n).
3. Efficient for Large Data: Even if you have a lot of data, it still works smoothly without slowing down.
4. Used in Real Systems: Many libraries and operating systems are dependent on Red-Black trees. This shows that they are reliable.
5. Better than unbalanced trees: Unlike normal binary search trees that can become skewed, Red-Black Trees avoid worst-case slowness.
Disadvantages of Red-Black Tree
Given below are 5 disadvantages of the Red-Black Tree:
1. Harder to Understand: The rules with colors and rotations can be tricky to learn compared to normal binary search trees.
2. Complex to Implement: Writing the code for insertions and deletions is more complicated than other tree types.
3. Extra Memory: Each node needs a colour attribute which increases the memory usage.
4. Slower than Simpler Trees for Small Data: For small sets of data, simpler trees or arrays might be faster because the balancing overhead is unnecessary.
5. Not Always the Best Choice: In some cases, other balanced trees like AVL trees may give faster lookups.
Level Up Your Resume with In-Demand Skills!
Join our Free DSA Course and master problem-solving with hands-on practice.
Conclusion
In data structures, a Red-Black Tree is a smart way to maintain balance in the data ensuring that operations like searching, inserting, and deleting remain fast, even as the tree grows large. At first, it may be complicated because of its coloring and rotations, but the rules are what make it powerful. Although it has a few drawbacks, its ability to keep operations efficient makes it an appropriate choice in many real-world applications. Once you understand the basics, it becomes very clear why the Red-Black trees are used in computer science.
Boost your career by joining the Python Course today and build real hands-on skills. Get ready for job interviews with expert-curated Python Interview Questions.
Red-Black Tree in Data Structure – FAQs
Q1. Why are colors important in a Red-Black Tree?
The colors help keep the tree balanced without needing too many rotations.
Q2. Is a Red-Black Tree always perfectly balanced?
No, it’s not perfectly balanced, but it stays “balanced enough” for fast operations.
Q3. Can a Red-Black Tree have two red nodes in a row?
No, it is not allowed. This is because this rule helps to keep the tree balanced.
Q4. Is a Red-Black Tree faster than a normal Binary Search Tree?
Yes, because it prevents the tree from becoming too tall, so searching is quicker.
Q5. Where do we mostly use Red-Black Trees in real life?
They are commonly applied in databases, compilers, and memory management systems.