Red Black Tree
Red Balck tree variant of tree data structure which comes under the category of the self-balanced binary search tree. A binary search tree is the most popular variant of the tree, and it has at most two child nodes connected with one parent node. A red-black tree is a self-balancing binary search tree with an extra bit to denote the color. In this article, we will briefly discuss red black Tree Algorithm.
The tree is a data structure that stores data in a hierarchical form and is a set of vertices and edges connected with each other but makes sure that they do not form a cycle. The tree has various variants and each variant has different property and classification. In this article, we are going to study about Red Balck Tree variant of tree data structure which comes under the category of the self-balanced binary search tree.
A binary search tree is the most popular variant of the tree, and it has at most two child nodes connected with one parent node. A red-black tree is a self-balancing binary search tree with an extra bit to denote the color. The red-black tree uses two colors red and black to ensure that the tree remains balanced after the insertion and deletion operation. It is similar to an AVL tree in terms of its self-balancing nature, but it uses different properties to be balanced.
Now, you might be thinking, why a balanced tree? Balanced binary search trees like AVL tree, m-tree, and Red-Black Tree are way more efficient than unbalanced binary trees, and hence these efficient trees result in more efficient time complexities and can be used for data organization in the memory.
The red-black tree got this name because the nodes in the tree are labeled with either red or black color. It is slightly larger in size than the AVL tree. In this article, we will discuss the properties of the red-black tree, the height of the red-black tree, insertion, and deletion operations on a red-black tree, and at last, analyze the complexity of the red-black tree.
Properties of Red-Black Tree
A red-black tree is a binary search tree that has the property of self-balancing and for this, it makes use of two colors red and black in order to ensure that the tree is balanced even after multiple insertions and deletion operations. Being a variant of a binary search tree Red Black tree also has at most two children, at most means that a node either can have zero, one, or two children but not more than two.
Here are some properties of the Red Balck Tree which must be considered whenever designing a Red-Black tree, so the properties are as follows:
- Red-black tree is a self-balancing binary search tree.
- The root node should be of Black color.
- Every node would have either red/black color.
- Every leaf node which is NIL would be in Black color.
- If the node is in Red color then its children must be in Black color.
- Every path from a node to any of its descendent NIL nodes has the same number of black trees.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Structure of Red Black Tree
struct t_red_black_node { enum { red, black } color; void *item; struct t_red_black_node *left, *right, *parent; }
Example of Red Black Tree
The above image is a basic Red-Black tree without Nil Node, and it is violating the property number 4, which says every leaf node should be of black color, so to resolve this issue, we will insert black nil node as child node to each node. Then the tree will be like
The above-shown tree is following all the Red-black tree property,
It is a balanced binary search tree.
The root node is black.
Nodes are in red/ black color.
Every leaf node is black in color.
No two child and parent node are of red color consecutively.
Every path from the root node has the equal number of red and black trees.
Hence, the red-black tree in the above diagram is the perfect example of a Red-black tree.
Height of Red Black Tree
A Red-black tree with n number of internal nodes has a height of 2log(n+1)
Consider a tree with a height of h. In any red-black tree, half of its nodes are of red color. So, a tree without a red node will be
h1 ≥ h/2 [Also, known as Balck height of red-Black tree]
and the number of leaves in a tree are exactly n+1.
So,
n + 1≥ 2h1
log (n+1) ≥ h1 ≥ h/2
h ≤ 2log (n+1)
Operations on Red Black Tree
When Insertion and deletion operation runs on a red-black tree, it can violate the basic Red-black tree property, to restore the property of the tree, we need to change the color of the nodes, so we have two operations to restore the property of the red-black tree. After insertion and deletion operation color of some node need to be changed along with the pointer structure.
- Rotation
- Insertion
- Deletion
Rotation
Rotation is a local operation in a red-black tree that preserves the order of in-order traversal in the red-black tree.
Left Rotate:
In the left rotation of the above diagram, node A will become the root node, and B is rotated to left, so it will be the child of B, B’s left child will remain its’ left child, y was on the right of B and left of A, hence that condition will also be maintained, z was the right child of A and hence Z is the right child of A even after rotation.
Algorithm:
left_rotate( Tree T, node B ) { node A; A = B → right; /* Turn y's left sub-tree into B's right sub-tree */ B → right = A →left; if ( A → left != NULL ) A → left → parent = B; /* A's new parent was B's parent */ A → parent = B → parent; /* Set the parent to point to A instead of B */ /* First see whether we're at the root */ if ( B → parent == NULL ) T → root = A; else if ( B == (B → parent) → left ) /* B was on the left of its parent */ B → parent → left = A; else /* B must have been on the right */ B → parent → right = A; /* Finally, put B on A's left */ A → left = B; B → parent = B; }
Insertion:
Insertion in the red-black tree follows following property:
- If tree is empty, create new node with as root node with the black color.
- If the tree is not empty, create new node as a leaf node with the red color.
- If a parent of the new node is of black color, then exit
- If a parent of new is red, check the color of the parent’s sibling of new node
- If the sibling’s color is black or null then do suitable recolration and reordering.
- If the color is red then recolor and also check if the parent’s parent of the new node is not the root node, then recolor it and recheck for the basic properties of the red black tree.
Algorithm:
rb_insert( Tree T, node A ) { /* Insert in the tree in the usual way */ tree_insert( T, A ); /* Now restore the red-black property */ A → colour = red; while ( (A != T → root) && (A → parent → colour == red) ) { if ( A → parent == A → parent → parent → left ) { /* If A's parent is a left, B is A's right 'uncle' */ B = A → parent → parent → right; if ( B → colour == red ) { /* case 1 - change the colours */ A → parent → colour = black; B → colour = black; A → parent → parent → colour = red; /* Move x up the tree */ A = A → parent → parent; } else { /* B is a black node */ if ( A == A → parent → right ) { /* and A is to the right */ /* case 2 - move A up and rotate */ A = A → parent; left_rotate( T, A ); } /* case 3 */ A → parent → colour = black; A → parent → parent → colour = red; right_rotate( T, A → parent → parent ); } } else { /* repeat the "if" part with right and left exchanged */ } } /* Colour the root black */ T → root → colour = black; }
Deletion:
Deletion is the most complex operation in red-black tree, as it has certain cases and each case dealing with different condiition in order to delete a node.
CASE 1: If the node to be deleted is red in color, simply delete it.
CASE 2: If root is double black, just remove double black.
CASE 3: If a double black sibling is black & both its children are black.
Remove Double Black.
- Add black to its parent
- If the Parent is red it becomes black.
- If the Parent is black it will become double black.
- Make sibling red
- If double black still exists, then reply to other cases.
CASE 4: If double black’s sibling is red.
- Swap colors of parent and double black’s sibling
- Rotate parent in double black’s direction.
- Reapply cases.
CASE 5: Double black’s sibling is black, sibling’s child who is far from DB is black but near the child to double black is red.
- Swap color of double black’s sibling and sibling’s child who is near to double black.
- Rotate the sibling in opposite direction to double black.
- Apply CASE 6.
CASE 6: Double black’s sibling is black, and the far child is red.
- Swap color of parent and sibling
- Rotate parent in double black’s direction
- Remove double black
- Change color of the red child to black.
The complexity of Red Black Tree
| Operation | Complexity |
| Insertion | O (log n) |
| Deletion | O (log n) |
| Searching | O (log n) |
| Traverse | O (n) |
| Space | O (n) |
Author: Kanika Joshi
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
