Last Updated on May 5, 2023 by Prepbytes
Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. Let us first define a Binary Search Tree before diving into the red black tree. A BST (Binary Search Tree) is a nonlinear data structure in which the nodes in the left subtree have values less than the root node and the nodes in the right subtree have values greater than the root node. In this article, we will go through the Red Black Tree in depth.
What is Red Black Tree in Data Structure
The redblack tree is a binary search tree in which each node is either red or black. It’s a selfbalancing binary search tree. It has a low worstcase running time complexity.
Properties of a Red Black Tree in Data Structure
The RedBlack tree satisfies all of the properties of a binary search tree, as well as the following extra properties –
 The root is black in color.
 External property: In the RedBlack tree, every leaf (Leaf is a NULL offspring of a node) is black.
 Internal property: A red node’s children are black. As a result, the red node’s probable parent is a black node.
 Depth property: The dark depth of all the leaves is the same.
 Path property: There is the same number of black nodes on every simple path from the root to a descendant leaf node.
The red black tree must obey some rules in addition to the given set of characteristics. Let’s talk about these rule sets.
Set of Rules for Red Black Tree in Data Structure
Every Red Black Tree must abide by the following rules:
 Every node has one of two colors: RED or BLACK.
 The tree’s root is always BLACK.
 There are no adjacent RED nodes, which means that a RED node cannot have a RED parent or a RED child.
 Every path that connects a node (including the root) to any of its descendants The number of NULL nodes is the same as the number of BLACK nodes.
 Every leaf, that is, every NULL node, must be coloured BLACK.
Why do we need the Red Black Tree?
Most BST operations (for example, search, max, min, insert, delete, etc.) take O(h) time, where h is the height of the BST. For a skewed Binary tree, the cost of these operations may become O(n). We can guarantee an upper bound of O(log n) for all of these operations if we ensure that the height of the tree remains O(log n) after every insertion and deletion. We can guarantee that all operations require O(log n) operations since the height of a RedBlack tree is always O(log n), where n is the number of nodes in the tree.
The time complexity of each operation is shown below in tabular form:
S.No  Operation  Time Complexity 

1  Search  O(log n) 
2  Insert  O(log n) 
3  Delete  O(log n) 
AVL Tree vs Red Black Tree in Data Structure
Let’s discuss the difference between AVL tree and Red black tree in Data Structure:
What is AVL Tree in Data Structure?
The AVL Tree is a heightbalanced binary search tree in which each node has a balancing factor that is derived by subtracting the height of its right subtree from the height of its left subtree.
If the balance factor of each node is between 1 and 1, the tree is said to be balanced; otherwise, the tree is imbalanced and must be balanced.
Now, let us discuss some differences between AVL Tree and Red Black Tree.
Parameter  Red Black Tree  AVL Tree 

Searching  Searching is not efficient as they are not perfectly balanced.  Searching is efficient as they are perfectly balanced. 
Insertion and deletion  Insertion and deletion are easier in the Red Black tree as it requires fewer rotations to balance the tree.  Insertion and deletion are complex in AVL tree as it requires multiple rotations to balance the tree. 
Color of the Node  Red or Black  No color 
Balance factor  No balance factor  Each node has a balance factor in the AVL tree whose value can be 1, 0, or 1. 
Strictly balanced  Not strictly balanced  Strictly balanced 
Operations on a Red Black Tree in Data Structure
In a Red Black Tree, we can do certain operations, including :
 Rotating a subtree
 Insertion
 Deletion
Rotating a subtree in a Red Black Tree in Data Structure
The positions of a subtree’s nodes are swapped during the rotation operation. When other processes, such as insertion and deletion, violate the attributes of a redblack tree, the rotation operation is employed to restore them. Rotations are classified into two types:

Left Rotation
In leftrotation, the arrangement of the nodes on the right is replaced by the arrangement of the nodes on the left.
Let the first tree be:

If y has a left subtree, make x the parent of y’s left subtree.

If the parent of x is NULL, make y the tree’s root.

Otherwise, if x is p’s left child, make y p’s left child.

Otherwise, make y the right child of p.

Make y the parent of x.


Right Rotation
The arrangement of the nodes on the left is changed into the arrangement of the nodes on the right in rightrotation.
Let the initial tree be:

If x has a right subtree, assign y as the parent of the right subtree of x.

If the parent of y is NULL, make x as the root of the tree.

Else if y is the right child of its parent p, make x as the right child of p.

Else assign x as the left child of p.

Make x as the parent of y.

Insertion in a Red Black Tree in Data Structure
When a new node is inserted, it is always inserted as a RED node. If the tree violates the properties of the redblack tree after insertion of a new node, we do the following activities.
 Recolor
 Rotation
Algorithm to Insert a Node in a Red Black Tree
 Navigate the tree to determine the best location for the new node.
 Once you’ve found the right spot, insert the new node as a red node.
 If the new node’s parent is black, no additional action is required, and the tree remains a valid redblack tree.
 If the new node’s parent is red, there are three possibilities:
 Case 1: The sibling of the parent is also red. In this scenario, color the parent and its sibling black, and the parent’s parent (grandparent) red in this scenario. Then, repeat the algorithm from the grandparent to ensure that the redblack tree properties are preserved.
 Case 2: The parent’s sibling is black, the new node is its parent’s right child, and the parent is its grandparent’s left child. Perform a left rotation on the parent in this case, so that the new node becomes the parent and the parent becomes the new node’s left child. Then, repeat the algorithm from the parent to ensure that the redblack tree properties are preserved.
 Case 3: The parent’s sibling is black, the new node is the parent’s left kid, and the parent is the grandparent’s left child. In this scenario, recolor the parent black and the grandparent red, and then right rotate the grandparent such that the parent becomes the grandparent’s right child and the grandparent becomes the parent’s right child. Then, repeat the algorithm from the parent to ensure that the redblack tree properties are preserved.
 Case 4: The parent’s sibling is black, the new node is its parent’s left child, and the parent is the right child of its grandparent. In this situation, rightrotate the parent such that the new node becomes the parent and the parent becomes the new node’s right child. Then, repeat the algorithm from the parent to ensure that the redblack tree properties are preserved.
 Case 5: The parent’s sibling is black, and the new node is the parent’s right kid, and the parent is the grandparent’s right child. In this scenario, recolor the parent black and the grandparent red, and then rotate the grandparent so that the parent becomes the grandparent’s left child and the grandparent becomes the parent’s left child. Then, repeat the algorithm from the parent to ensure that the redblack tree properties are preserved.
 Continue the procedure until you reach the tree’s root, and then recolor it black to ensure it is always black.
Code Implementation
/*package whatever //do not write package name here */ import java.io.*; // considering that you know what are redblack trees here is the implementation in java for insertion and traversal. // RedBlackTree class. This class contains subclass for node // as well as all the functionalities of RedBlackTree such as  rotations, insertion and // inoredr traversal public class RedBlackTree { public Node root;//root node public RedBlackTree() { super(); root = null; } // node creating subclass class Node { int data; Node left; Node right; char colour; Node parent; Node(int data) { super(); this.data = data; // only including data. not key this.left = null; // left subtree this.right = null; // right subtree this.colour = 'R'; // colour . either 'R' or 'B' this.parent = null; // required at time of rechecking. } } // this function performs left rotation Node rotateLeft(Node node) { Node x = node.right; Node y = x.left; x.left = node; node.right = y; node.parent = x; // parent resetting is also important. if(y!=null) y.parent = node; return(x); } //this function performs right rotation Node rotateRight(Node node) { Node x = node.left; Node y = x.right; x.right = node; node.left = y; node.parent = x; if(y!=null) y.parent = node; return(x); } // these are some flags. // Respective rotations are performed during traceback. // rotations are done if flags are true. boolean ll = false; boolean rr = false; boolean lr = false; boolean rl = false; // helper function for insertion. Actually this function performs all tasks in single pass only. Node insertHelp(Node root, int data) { // f is true when RED RED conflict is there. boolean f=false; //recursive calls to insert at proper position according to BST properties. if(root==null) return(new Node(data)); else if(data<root.data) { root.left = insertHelp(root.left, data); root.left.parent = root; if(root!=this.root) { if(root.colour=='R' && root.left.colour=='R') f = true; } } else { root.right = insertHelp(root.right,data); root.right.parent = root; if(root!=this.root) { if(root.colour=='R' && root.right.colour=='R') f = true; } // at the same time of insertion, we are also assigning parent nodes // also we are checking for RED RED conflicts } // now lets rotate. if(this.ll) // for left rotate. { root = rotateLeft(root); root.colour = 'B'; root.left.colour = 'R'; this.ll = false; } else if(this.rr) // for right rotate { root = rotateRight(root); root.colour = 'B'; root.right.colour = 'R'; this.rr = false; } else if(this.rl) // for right and then left { root.right = rotateRight(root.right); root.right.parent = root; root = rotateLeft(root); root.colour = 'B'; root.left.colour = 'R'; this.rl = false; } else if(this.lr) // for left and then right. { root.left = rotateLeft(root.left); root.left.parent = root; root = rotateRight(root); root.colour = 'B'; root.right.colour = 'R'; this.lr = false; } // when rotation and recolouring is done flags are reset. // Now lets take care of RED RED conflict if(f) { if(root.parent.right == root) // to check which child is the current node of its parent { if(root.parent.left==null  root.parent.left.colour=='B') // case when parent's sibling is black {// perform certaing rotation and recolouring. This will be done while backtracking. Hence setting up respective flags. if(root.left!=null && root.left.colour=='R') this.rl = true; else if(root.right!=null && root.right.colour=='R') this.ll = true; } else // case when parent's sibling is red { root.parent.left.colour = 'B'; root.colour = 'B'; if(root.parent!=this.root) root.parent.colour = 'R'; } } else { if(root.parent.right==null  root.parent.right.colour=='B') { if(root.left!=null && root.left.colour=='R') this.rr = true; else if(root.right!=null && root.right.colour=='R') this.lr = true; } else { root.parent.right.colour = 'B'; root.colour = 'B'; if(root.parent!=this.root) root.parent.colour = 'R'; } } f = false; } return(root); } // function to insert data into tree. public void insert(int data) { if(this.root==null) { this.root = new Node(data); this.root.colour = 'B'; } else this.root = insertHelp(this.root,data); } // helper function to print inorder traversal void inorderTraversalHelper(Node node) { if(node!=null) { inorderTraversalHelper(node.left); System.out.printf("%d ", node.data); inorderTraversalHelper(node.right); } } //function to print inorder traversal public void inorderTraversal() { inorderTraversalHelper(this.root); } // helper function to print the tree. void printTreeHelper(Node root, int space) { int i; if(root != null) { space = space + 10; printTreeHelper(root.right, space); System.out.printf("\n"); for ( i = 10; i < space; i++) { System.out.printf(" "); } System.out.printf("%d", root.data); System.out.printf("\n"); printTreeHelper(root.left, space); } } // function to print the tree. public void printTree() { printTreeHelper(this.root, 0); } public static void main(String[] args) { RedBlackTree t = new RedBlackTree(); int[] arr = {1,4,6,3,5,7,8,2,9}; for(int i=0;i<9;i++) { t.insert(arr[i]); System.out.println(); t.inorderTraversal(); } t.printTree(); } }
Output
1
1 4
1 4 6
1 3 4 6
1 3 4 5 6
1 3 4 5 6 7
1 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9
Deletion in a Red Black Tree in Data Structure
 Locate the node that needs to be deleted.
 Remove the node from the tree if it has no children.
 Replace the node with that child and recolor the replacement node black if the original node was black. Remove the initial node from the tree if it is red.
 If the node has two children, replace it with its inorder successor (the node with the smallest key in the right subtree of the node), then delete the inorder successor from its original location. Because the inorder successor can only have one child, we can handle this deletion case using case 2 or 3 from the insertion algorithm.
 Find the inorder successor of the node to be deleted.
 Replace the node to be deleted with its inorder successor.
 Delete the inorder successor from its original location using cases 1, 2, or 3 from the insertion algorithm.
 Check whether any of the redblack tree attributes have been violated after deleting the node, and repair any violations using the following cases:
 If the node replaced during deletion is red, recolor it black.
 If the node replaced during deletion is black and its replacement is red, recolor the replacement black.
 If the node replaced during deletion is black and its replacement is black, then adjust the tree to restore the redblack tree properties by following one of the cases below:
 If the deleted node’s sibling is red, recolor the sibling and its parent black and red, respectively, and then rotate the parent left or right (depending on whether the sibling is a left or right child).
 If the deleted node’s sibling is black and both of its children are black, recolor the sibling red and proceed with the algorithm from the sibling’s parent.
 If the deleted node’s sibling is black, its inner child is red, and its outer child is black, rotate the sibling and its inner child, and then continue the algorithm from the original sibling.
 If the deleted node’s sibling is black and its outer child is red, recolor the sibling to match its parent, recolor the parent black, recolor the outer child black, and rotate the parent.
 Finally, recolor the root black to maintain the redblack tree properties.
Code Implementation
#include <iostream> #include <queue> using namespace std; enum COLOR { RED, BLACK }; class Node { public: int val; COLOR color; Node *left, *right, *parent; Node(int val) : val(val) { parent = left = right = NULL; // Node is created during insertion // Node is red at insertion color = RED; } // returns pointer to uncle Node *uncle() { // If no parent or grandparent, then no uncle if (parent == NULL or parent>parent == NULL) return NULL; if (parent>isOnLeft()) // uncle on right return parent>parent>right; else // uncle on left return parent>parent>left; } // check if node is left child of parent bool isOnLeft() { return this == parent>left; } // returns pointer to sibling Node *sibling() { // sibling null if no parent if (parent == NULL) return NULL; if (isOnLeft()) return parent>right; return parent>left; } // moves node down and moves given node in its place void moveDown(Node *nParent) { if (parent != NULL) { if (isOnLeft()) { parent>left = nParent; } else { parent>right = nParent; } } nParent>parent = parent; parent = nParent; } bool hasRedChild() { return (left != NULL and left>color == RED) or (right != NULL and right>color == RED); } }; class RBTree { Node *root; // left rotates the given node void leftRotate(Node *x) { // new parent will be node's right child Node *nParent = x>right; // update root if current node is root if (x == root) root = nParent; x>moveDown(nParent); // connect x with new parent's left element x>right = nParent>left; // connect new parent's left element with node // if it is not null if (nParent>left != NULL) nParent>left>parent = x; // connect new parent with x nParent>left = x; } void rightRotate(Node *x) { // new parent will be node's left child Node *nParent = x>left; // update root if current node is root if (x == root) root = nParent; x>moveDown(nParent); // connect x with new parent's right element x>left = nParent>right; // connect new parent's right element with node // if it is not null if (nParent>right != NULL) nParent>right>parent = x; // connect new parent with x nParent>right = x; } void swapColors(Node *x1, Node *x2) { COLOR temp; temp = x1>color; x1>color = x2>color; x2>color = temp; } void swapValues(Node *u, Node *v) { int temp; temp = u>val; u>val = v>val; v>val = temp; } // fix red red at given node void fixRedRed(Node *x) { // if x is root color it black and return if (x == root) { x>color = BLACK; return; } // initialize parent, grandparent, uncle Node *parent = x>parent, *grandparent = parent>parent, *uncle = x>uncle(); if (parent>color != BLACK) { if (uncle != NULL && uncle>color == RED) { // uncle red, perform recoloring and recurse parent>color = BLACK; uncle>color = BLACK; grandparent>color = RED; fixRedRed(grandparent); } else { // Else perform LR, LL, RL, RR if (parent>isOnLeft()) { if (x>isOnLeft()) { // for left right swapColors(parent, grandparent); } else { leftRotate(parent); swapColors(x, grandparent); } // for left left and left right rightRotate(grandparent); } else { if (x>isOnLeft()) { // for right left rightRotate(parent); swapColors(x, grandparent); } else { swapColors(parent, grandparent); } // for right right and right left leftRotate(grandparent); } } } } // find node that do not have a left child // in the subtree of the given node Node *successor(Node *x) { Node *temp = x; while (temp>left != NULL) temp = temp>left; return temp; } // find node that replaces a deleted node in BST Node *BSTreplace(Node *x) { // when node have 2 children if (x>left != NULL and x>right != NULL) return successor(x>right); // when leaf if (x>left == NULL and x>right == NULL) return NULL; // when single child if (x>left != NULL) return x>left; else return x>right; } // deletes the given node void deleteNode(Node *v) { Node *u = BSTreplace(v); // True when u and v are both black bool uvBlack = ((u == NULL or u>color == BLACK) and (v>color == BLACK)); Node *parent = v>parent; if (u == NULL) { // u is NULL therefore v is leaf if (v == root) { // v is root, making root null root = NULL; } else { if (uvBlack) { // u and v both black // v is leaf, fix double black at v fixDoubleBlack(v); } else { // u or v is red if (v>sibling() != NULL) // sibling is not null, make it red" v>sibling()>color = RED; } // delete v from the tree if (v>isOnLeft()) { parent>left = NULL; } else { parent>right = NULL; } } delete v; return; } if (v>left == NULL or v>right == NULL) { // v has 1 child if (v == root) { // v is root, assign the value of u to v, and delete u v>val = u>val; v>left = v>right = NULL; delete u; } else { // Detach v from tree and move u up if (v>isOnLeft()) { parent>left = u; } else { parent>right = u; } delete v; u>parent = parent; if (uvBlack) { // u and v both black, fix double black at u fixDoubleBlack(u); } else { // u or v red, color u black u>color = BLACK; } } return; } // v has 2 children, swap values with successor and recurse swapValues(u, v); deleteNode(u); } void fixDoubleBlack(Node *x) { if (x == root) // Reached root return; Node *sibling = x>sibling(), *parent = x>parent; if (sibling == NULL) { // No sibling, double black pushed up fixDoubleBlack(parent); } else { if (sibling>color == RED) { // Sibling red parent>color = RED; sibling>color = BLACK; if (sibling>isOnLeft()) { // left case rightRotate(parent); } else { // right case leftRotate(parent); } fixDoubleBlack(x); } else { // Sibling black if (sibling>hasRedChild()) { // at least 1 red children if (sibling>left != NULL and sibling>left>color == RED) { if (sibling>isOnLeft()) { // left left sibling>left>color = sibling>color; sibling>color = parent>color; rightRotate(parent); } else { // right left sibling>left>color = parent>color; rightRotate(sibling); leftRotate(parent); } } else { if (sibling>isOnLeft()) { // left right sibling>right>color = parent>color; leftRotate(sibling); rightRotate(parent); } else { // right right sibling>right>color = sibling>color; sibling>color = parent>color; leftRotate(parent); } } parent>color = BLACK; } else { // 2 black children sibling>color = RED; if (parent>color == BLACK) fixDoubleBlack(parent); else parent>color = BLACK; } } } } // prints level order for given node void levelOrder(Node *x) { if (x == NULL) // return if node is null return; // queue for level order queue<Node *> q; Node *curr; // push x q.push(x); while (!q.empty()) { // while q is not empty // dequeue curr = q.front(); q.pop(); // print node value cout << curr>val << " "; // push children to queue if (curr>left != NULL) q.push(curr>left); if (curr>right != NULL) q.push(curr>right); } } // prints inorder recursively void inorder(Node *x) { if (x == NULL) return; inorder(x>left); cout << x>val << " "; inorder(x>right); } public: // constructor // initialize root RBTree() { root = NULL; } Node *getRoot() { return root; } // searches for given value // if found returns the node (used for delete) // else returns the last node while traversing (used in insert) Node *search(int n) { Node *temp = root; while (temp != NULL) { if (n < temp>val) { if (temp>left == NULL) break; else temp = temp>left; } else if (n == temp>val) { break; } else { if (temp>right == NULL) break; else temp = temp>right; } } return temp; } // inserts the given value to tree void insert(int n) { Node *newNode = new Node(n); if (root == NULL) { // when root is null // simply insert value at root newNode>color = BLACK; root = newNode; } else { Node *temp = search(n); if (temp>val == n) { // return if value already exists return; } // if value is not found, search returns the node // where the value is to be inserted // connect new node to correct node newNode>parent = temp; if (n < temp>val) temp>left = newNode; else temp>right = newNode; // fix red red violation if exists fixRedRed(newNode); } } // utility function that deletes the node with given value void deleteByVal(int n) { if (root == NULL) // Tree is empty return; Node *v = search(n), *u; if (v>val != n) { cout << "No node found to delete with value:" << n << endl; return; } deleteNode(v); } // prints inorder of the tree void printInOrder() { cout << "Inorder: " << endl; if (root == NULL) cout << "Tree is empty" << endl; else inorder(root); cout << endl; } // prints level order of the tree void printLevelOrder() { cout << "Level order: " << endl; if (root == NULL) cout << "Tree is empty" << endl; else levelOrder(root); cout << endl; } }; int main() { RBTree tree; tree.insert(7); tree.insert(3); tree.insert(18); tree.insert(10); tree.insert(22); tree.insert(8); tree.insert(11); tree.insert(26); tree.insert(2); tree.insert(6); tree.insert(13); tree.printInOrder(); tree.printLevelOrder(); cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl; tree.deleteByVal(18); tree.deleteByVal(11); tree.deleteByVal(3); tree.deleteByVal(10); tree.deleteByVal(22); tree.printInOrder(); tree.printLevelOrder(); return 0; }
Output
Inorder:
2 3 6 7 8 10 11 13 18 22 26
Level order:
10 7 18 3 8 11 22 2 6 13 26
Deleting 18, 11, 3, 10, 22
Inorder:
2 6 7 8 13 26
Level order:
13 7 26 6 8 2
Conclusion
In this article, we have discussed the Red black tree in data structure. Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. We have also discussed the use cases of Red Black Tree in data structure. How insertion and deletion work, along with how we can rotate a subtree in a Red black data structure.
Frequently Asked Questions (FAQs)
Q1. What is the purpose of the redblack tree?
Ans. RB trees are used to construct associative arrays in functional programming. RB trees are used in conjunction with 24 trees, a selfbalancing data structure in which each node has two, three, or four child nodes.
Q2. In terms of data structure complexity, what is a redblack tree?
Ans. Redblack trees give a logarithmic average and worstcase time complexity for insertion, search, and deletion. Rebalancing has an average time complexity of O(1), with a worstcase complexity of O(log n).
Q3. What exactly is a redblack tree?
Ans. A selfbalancing binary search tree is a Red Black Tree. It was invented in 1972 by Rudolf Bayer and termed "symmetric binary Btrees."
Q4. What exactly is the redblack tree sorting algorithm?
Ans. The redblack tree algorithm is a method for balancing trees. The term is derived from the fact that each node is either red or black, and the color of the node is significant in defining the balance of the tree.
Q5. What is the highest point of the redblack tree algorithm?
Ans. Because red nodes cannot have red children, the path’s nodes must alternate between red and black. As a result, the path can only be twice as long as the black depth of the tree. As a result, the worstcase height of the tree is O(2 log nb). A redblack tree’s height is O(log n).