In this article, we will study what is a red-black tree is and why it is useful. We will understand various operations of the red-black tree along with their algorithm, example, and python code. Later we will also go through various advantages, disadvantages, and applications of the red-black tree.
What is a Red-Black Tree?
A red-black tree is the variation of the binary search tree with the property of self-balancing. A red-black tree is also called symmetric binary B-Tree. Every node of the red-black tree contains an extra attribute denoting the color of the node, specifically, either red or black. The importance of these colors in the nodes of the tree ensures that the tree is balanced while insertion and deletion operations of the node. Therefore, the red-black tree follows the below properties:
- Tree Property: Red-Black tree should be a binary search tree.
- Red/Black Property: Every node of the tree is colored either red or black.
- Root Property: The color attribute of the root node is always black.
- Leaf Property: Every leaf of the tree is black.
- Red Property: The child node is always black if the parent node is red in color. Therefore, there should not be two consecutive red nodes.
- Depth Property: Every path from the root node to any leaf node should have the same number of black-colored nodes.
Remember that every node of the red-black tree consumes only 1 bit of memory storage to store the color information, hence the tree is identical to the classic binary search tree.
Why Use Red-Black Tree?
As you know that binary search tree maintains the natural order of the data inserted, but it does not restrict the size, length, or height of the tree. Consider the below image where the nodes inserted in the binary search tree are 10,20,30,40,50. Here, the height of the tree is 5 as the tree grows linearly when the new node is inserted. Hence, as the height of the tree grows linearly, the search operation in the tree becomes the worst-case scenario and takes O(n) time where n is the total number of nodes inserted.
This problem can be solved by using a red-black tree. As the red-black tree maintains its height of the tree after every insertion and deletion operation, the tree can be avoided from skewing. Therefore, the time complexity for search operation is reduced to O(log n) where n is the number of nodes in the tree.
Instead of a red-black tree, you can also use an AVL tree to balance the height of the tree. But it is noted, that the red-black tree makes fewer structural changes to balance the height of the tree in comparison to AVL trees. Hence, the red-black tree is potentially faster during insertion and deletion operations in comparison to AVL trees.
Rotations in Red Black Tree
The rotation is the process of adjusting or interchange the nodes of the subtrees inside the tree in such a way that the height of the tree is restored. It helps to maintain the red-black tree properties which are sometimes violated while insertion and deletion operations. Basically, there are two types of rotation in Red-Black Tree:
1) Left Rotation
The nodes on the right of the tree are transformed on the left node is called the left rotation. Look at the below algorithm for understanding.
- Consider the below red-black tree
- Assign ‘a’ as a parent node of the left subtree of ‘b’, if ‘b’ has a left subtree.
- Assign ‘b’ as the root of the tree if the parent node of ‘a’ is NULL
- Assign ‘b’ as the left child of ‘n’, if ‘a’ is the left child of ‘n’
- Assign ‘b’ as the right child of ‘n’, if ‘a’ is right child of ‘n’
- Make ‘b’ as the parent node of ‘a’
2) Right Rotation
The nodes on the left of the tree are transformed on the right node is called the left rotation. Look at the below algorithm for understanding.
- Consider the below given red-black tree
- Assign ‘b’ as the parent node of the right subtree of ‘a’, if ‘a’ has a right subtree
- Assign ‘a’ as the root of the tree if the parent of ‘b’ is NULL
- Assign ‘a’ as the right child of ‘n’, if ‘b’ is the right child of ‘n’.
- Assign ‘a’ as the left child of ‘n’, if ‘b’ is the right child of ‘n’
- Make ‘a’ as the parent node of ‘b’
3) Right-Left and Left-Right Rotations
In right-left rotation, first, you perform right rotation followed by a left rotation.
In left-right rotation, first, you perform left rotation followed by right rotation
Operations in Red-Black Tree
There are two operations performed in Red-Black Tree:
- Insertion Operation
- Deletion Operation
1) Insertion Operation
When you insert a new node in the tree, it will always be inserted as Red Node. This is because the insertion of a new node does not violate the depth property of the red-black tree. But what if the red node gets attached to the red node? Well, this problem is easier to fix using rotation rather than violating the depth property of the tree. Later, if the tree properties are violated then the red-black tree undergoes the following operations:
Algorithm For Insertion of the Node
InsertionFix Algorithm to Maintain the Red-Black Tree Property
Insert node ‘4’ inside an empty tree. As discussed, the first inserted element is always the root node and black in color
Now, insert node ‘20’ inside the tree. As 20 > 4, it will be inserted as the right subtree of the root node and red in color
Now, insert node ‘31’ inside the tree. As 31> 20, it will be the right child of parent node ‘20’. Node ’31’ is red in color and according to the property of the red-black tree, no two red color nodes can be together and therefore we undergo the RR rotation to regain the balance of the tree.
Now, insert node ‘14’ inside the tree. As 14> 4 but 14<20, node ‘14’ will be the right child of node ‘4’. Again, the red-black tree property is violated because you have two consecutive red color nodes. Hence, we perform the recoloring in the tree which results in a red-colored parent node. So we simple color it black colored as shown below
Therefore the final tree structure will be as given below:
When you delete a node from the tree, there are possibilities that you violate the red-black tree property. Therefore, after removing the node from the tree, make sure you balance the tree by following the properties of the tree.
Algorithm for Deleting a Node
When the DeletingNode is black in color, it violates the red-black tree property. This scenario can be corrected by assuming that the node ‘a’ is had extra black. Therefore, node ‘a’ is neither Red nor Black rather it is either double black or black and red at the same time. Hence, the red-black tree property is violated.
Therefore, the extra black can be removed if
- It reached the RootNode
- If ‘a’ points to the red-black node. In this case, ‘a’ is colored, Black
- Required rotations and recoloring is performed
DeletionFix Algorithm to Maintain the Red-Black Tree Property
Consider the below given red-black tree
Now we want to delete 21 from the above tree. When node ‘21’ is deleted, it will be replaced by Null, so eventually Null will become double black as shown below
Now according to the algorithm of deletion, sibling of DeletingNode i.e Node ‘41’ is black colored with at least one red-colored child i.e. Node ‘36’ and Node ‘51’. Therefore, it will undergo RR rotation to retain the balance of the tree as shown below
Hence, the final tree structure will be as given below
Python Code for Red-Black Tree
| L---- 4(BLACK)
| | L---- 2(RED)
| R---- 10(BLACK)
After deleting an element
| L---- 4(BLACK)
| R---- 10(BLACK)
For insertion, deletion, and search operation, the time complexity for the red-black tree is logarithmic function i.e. O(log n) where n is the total number of nodes in the red-black tree. Whereas, the space complexity of the red-black tree is O(n).
Difference between Red-Black Tree and AVL Tree
It does not provide efficient searching as red-black tree are roughly balanced
It provides efficient searching as AVL trees are strictly balanced
Insertion and deletion operation is easier as require less number of rotation to balance the tree
Insertion and deletion operation is difficult as require more number of rotation to balance the tree
The nodes are either red or black in color
The nodes have no colors
It does not contain any balance factor to balance the height of the tree
It contains the balance factor to maintain the difference in the height of the tree.
Mostly used for insertion and deletion operations
Mostly used for searching operations
Advantages of Red-Black Tree
- Red-black tree balance the height of the binary tree
- Red-black tree takes less time to structure the tree by restoring the height of the binary tree
- The time complexity for search operation is O(log n)
- It has comparatively low constants in a wide range of scenarios
Disadvantages of Red-Black Tree
- Relatively complicated to implement
- The red-black tree is not rigidly balanced in comparison to the AVL tree
Applications of Red-Black Tree
- A red-black tree is used to implement the finite maps
- It is most important to implement the Java Libraries Packages like java.util.TreeSet and java.util.TreeMap
- A red-black tree is used while building the Linux kernel
- A red-black tree is used to implement the standard template library in C++
- It is used to implement the CPU scheduling algorithm like “completely fair scheduler” in Linux.
- A red-black tree is used in reducing the time complexity in the K-mean clustering algorithm
- It is used in MySQL for table indexing
- A red-black tree is used in Computation Geometry Data structure
- It is useful to keep track of the virtual memory segments for the process
- Hashmap data structure makes use of the red-black tree to store the key-value pair instead of linked-list for the faster search operation
The red-black tree is one of the members of the binary search tree which helps to maintain the height of the binary tree just like the AVL tree. Every node in the binary search tree is colored either red or black which further helps to maintain the properties of the tree and provides an effective and efficient method for insertion and deletion operations of the node in the binary tree by undergoing a fewer rotation. Therefore it is important to understand and make use of the red-black tree to enhance the searching time complexity of the binary search tree by preventing the tree from skewing. For more details, please refer to our extensive tutor program designed by experts at Favtutor.