A **Red Black Tree **is a type of self-balancing 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 red-black 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 black-depth (the number of black nodes).

An example of a red-black tree is:

Each node has the following attributes:

- color
- key
- leftChild
- rightChild
- parent (except root node)

How the red-black tree maintains the property of self-balancing?

** **The red-black 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 self-balancing property of the red-black tree.

**Operations on a Red-Black Tree**

** **Various operations that can be performed on a red-black tree are:

##### Rotating the subtrees in a Red-Black Tree

** **In rotation operation, the positions of the nodes of a subtree are interchanged.

Rotation operation is used for maintaining the properties of a red-black tree when they are violated by other operations such as insertion and deletion.

There are two types of rotations:

##### 1. Left Rotate

** **

In left-rotation, 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 right-rotation, 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. Left-Right and Right-Left Rotate

** **In left-right rotation, the arrangements are first shifted to the left and then to the right.

- Do left rotation on x-y.

- Do right rotation on y-z.

In right-left rotation, the arrangements are first shifted to the right and then to the left.

- Do right rotation on x-y.

- Do left rotation on z-y.

#### Inserting an Element into a Red-Black 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 red-black tree then, we do the following operations.

- Recolor
- Rotation

Following steps are followed for inserting a new element into a red-black tree:

- 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.

- Check if the tree is empty (ie. whether x is NIL). If yes, insert newNode as a root node and color it black.
- 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 InsertFix-algorithm to maintain the property of red-black tree if violated.

##### Why newly inserted nodes are always red in a red-black tree?

** **This is because inserting a red node does not violate the depth property of a red-black 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 red-black property after insertion

** **This algorithm is used for maintaining the property of a red-black 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****newNode**, do the following.

Case-I:

- If 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**.

Case-II:

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. Left-Rotate **newNode**.

Case-III:

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. Right-Rotate 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****newNode**and Right- Rotate**newNode**. - Set color of p as BLACK and color of gP as RED.
- Left-Rotate 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 Red-Black Tree

** **This operation removes a node from the tree. After deleting a node, the red-black property is maintained again.

- Let the
**nodeToBeDeleted**

- Save the color of
**nodeToBeDeleted**in**origrinalColor**.

- If the left child of
**nodeToBeDeleted**is NULL- Assign the right child of
**nodeToBeDeleted**to x.

- Assign the right child of

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**.

- Assign the minimum of right subtree of
**originalColor**is BLACK, call**DeleteFix(x).**

###### Algorithm to maintain Red-Black property after deletion

** **This algorithm is implemented when a black node is deleted because it violates the black depth property of the red-black 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 black-and- red. This violates the red-black 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 red-black In this case,*x*is colored black. - Suitable rotations and recolorings are performed.

Following algorithm retains the properties of a red-black tree.

*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,

Case-I:

- 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. Left-Rotate 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,

Case-II:

- 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

Case-III:

- Set the color of the
**leftChild**of*w*as BLACK - Set the color of
*w*as RED

iii. Right-Rotate *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.

Case-IV:

- 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. Left-Rotate 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.