A Red Black Tree is a type of selfbalancing binary search tree, in which every node is colored with a red or black. The red black tree satisfies all the properties of the binary search tree but there are some additional properties which were added in a Red Black Tree. The height of a Red Black tree is O (Logn) where (n is the number of nodes in the tree)
A redblack tree satisfies the following properties:
 Red/Black Property: Every node is colored, either red or black.
 Root Property: The root is black.
 Leaf Property: Every leaf (NIL) is black.
 Red Property: If a red node has children then, the children are always black.
 Depth Property: For each node, any simple path from this node to any of its descendant leaf has the same blackdepth (the number of black nodes).
An example of a redblack tree is:
Each node has the following attributes:
 color
 key
 leftChild
 rightChild
 parent (except root node)
How the redblack tree maintains the property of selfbalancing?
The redblack color is meant for balancing the tree.
The limitations put on the node colors ensure that any simple path from the root to a leaf is not more than twice as long as any other such path. It helps in maintaining the selfbalancing property of the redblack tree.
Operations on a RedBlack Tree
Various operations that can be performed on a redblack tree are:
Rotating the subtrees in a RedBlack Tree
In rotation operation, the positions of the nodes of a subtree are interchanged.
Rotation operation is used for maintaining the properties of a redblack tree when they are violated by other operations such as insertion and deletion.
There are two types of rotations:
1. Left Rotate
In leftrotation, the arrangement of the nodes on the right is transformed into the arrangements on the left node.
Algorithm
 Let the initial tree be:
 If y has a left subtree, assign x as the parent of the left subtree of y.
 If the parent of x p is NULL, make y as the root of the tree.
 Else if x is the left child of p, make y as the left child of p.
 Else assign y as the right child of p.
 Make y as the parent of x.
2. Right Rotate
In rightrotation, the arrangement of the nodes on the left is transformed into the arrangements on the right node.
 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.
3. LeftRight and RightLeft Rotate
In leftright rotation, the arrangements are first shifted to the left and then to the right.
 Do left rotation on xy.
 Do right rotation on yz.
In rightleft rotation, the arrangements are first shifted to the right and then to the left.
 Do right rotation on xy.
 Do left rotation on zy.
Inserting an Element into a RedBlack Tree
While inserting a new node, the new node is always inserted as a RED node. After insertion of a new node, if the tree is violating the properties of the redblack tree then, we do the following operations.
 Recolor
 Rotation
Following steps are followed for inserting a new element into a redblack tree:
1. The newNode be:
2. Let y be the leaf (ie. NIL) and x be the root of the The new node is inserted in the following tree.
3. Check if the tree is empty (ie. whether x is NIL). If yes, insert newNode as a root node and color it black.
4. Else, repeat steps following steps until leaf (NIL) is reached.

 Compare newKey with rootKey.
 If newKey is greater than rootKey, traverse through the right subtree.
 Else traverse through the left subtree.
 Assign the parent of the leaf as parent of newNode.
 If leafKey is greater than newKey, make newNode as rightChild.
 Else, make newNode as leftChild.
 Assign NULL to the left and rightChild of newNode.
 Assign RED color to newNode.
 Call InsertFixalgorithm to maintain the property of redblack tree if violated.
Why newly inserted nodes are always red in a redblack tree?
This is because inserting a red node does not violate the depth property of a redblack tree.
If you attach a red node to a red node, then the rule is violated but it is easier to fix this problem than the problem introduced by violating the depth property.
Algorithm to maintain redblack property after insertion
This algorithm is used for maintaining the property of a redblack tree if insertion of a newNode
violates this property.
 Do the following until the parent of newNode p is RED.
 If p is the left child of grandParent gP of newNode, do the following.
CaseI:
 the color of the right child of gP of newNode is RED, set the color of both the children of gP as BLACK and the color of gP as RED.
b. Assign gP to newNode.
CaseII:
c. (Before moving on to this step, while loop is checked. If conditions are not satisfied, it the loop is broken.)
Else if newNode is the right child of p then, assign p to newNode.
d. LeftRotate newNode.
CaseIII:
e. (Before moving on to this step, while loop is checked. If conditions are not satisfied, it the loop is broken.)
Set color of p as BLACK and color of gP as RED.
f. RightRotate gP.
 Else, do the
 If the color of the left child of gP of z is RED, set the color of both the children of gP as BLACK and the color of gP as RED.
 Assign gP to newNode.
 Else if newNode is the left child of p then, assign p to newNode and Right Rotate newNode.
 Set color of p as BLACK and color of gP as RED.
 LeftRotate gP.
 (This step is perfomed after coming out of the while loop.) Set the root of the tree as BLACK.
The final tree look like this:
Deleting an element from a RedBlack Tree
This operation removes a node from the tree. After deleting a node, the redblack property is maintained again.
 Let the nodeToBeDeleted be:
 Save the color of nodeToBeDeleted in origrinalColor.
 If the left child of nodeToBeDeleted is NULL
 Assign the right child of nodeToBeDeleted to x.
b. Transplant nodeToBeDeleted with x.
 Else if the right child of nodeToBeDeleted is NULL
 Assign the left child of nodeToBeDeleted into x.
b. Transplant nodeToBeDeleted with x.
 Else
 Assign the minimum of right subtree of noteToBeDeleted into y.
 Save the color of y in originalColor.
 Assign the rightChild of y into x.
 If y is a child of nodeToBeDeleted, then set the parent of x as y.
 Else, transplant y with rightChild of y.
 Transplant nodeToBeDeleted with y.
 Set the color of y with originalColor.
 If the originalColor is BLACK, call DeleteFix(x).
Algorithm to maintain RedBlack property after deletion
This algorithm is implemented when a black node is deleted because it violates the black depth property of the redblack tree.
This violation is corrected by assuming that node x (which is occupying y's original position) has an extra black. This makes node x neither red nor black. It is either doubly black or blackand red. This violates the redblack properties.
However, the color attribute of x is not changed rather the extra black is represented in x's pointing to the node.
The extra black can be removed if
 It reaches the root node.
 If x points to a redblack In this case, x is colored black.
 Suitable rotations and recolorings are performed.
Following algorithm retains the properties of a redblack tree.
 Do the following until the x is not the root of the tree and the color of x is BLACK
 If x is the left child of its parent then,
 Assign w to the sibling of x.
b. If the sibling of x is RED,
CaseI:
 Set the color of the right child of the parent of x as BLACK.
 Set the color of the parent of x as RED.
iii. LeftRotate the parent of x.
iv. Assign the rightChild of the parent of x to w.
c. If the color of both the right and the leftChild of w is BLACK,
CaseII:
 Set the color of w as RED
 Assign the parent of x to x.
d. Else if the color of the rightChild of w is BLACK
CaseIII:
 Set the color of the leftChild of w as BLACK
 Set the color of w as RED
iii. RightRotate w.
iv. Assign the rightChild of the parent of x to w.
e. If any of the above cases do not occur, then do the following.
CaseIV:
 Set the color of w as the color of the parent of x.
 Set the color of the parent of parent of x as BLACK.
 Set the color of the right child of w as BLACK.
iv. LeftRotate the parent of x.
v. Set x as the root of the tree.
3. Else same as above with right changed to left and vice versa.
4. Set the color of x as BLACK.
The workflow of the above cases can be understood with the help of the flowchart below.