Discuss the insertion operation in Red Black tree.

Q.) Discuss the insertion operation in Red Black tree.

 Subject: Data Structures

Insertion in a Red-Black Tree is a process that maintains the Red-Black properties after adding a new node to the tree. The Red-Black Tree is a self-balancing binary search tree, where every node has an extra bit for denoting the color of the node, either red or black. A Red-Black Tree satisfies the following properties:

  1. Node Color: Every node is either red or black.
  2. Root Property: The root is always black.
  3. Leaf Property: Every leaf (NIL node) is black.
  4. Red Node Property: If a red node has children then, the children are always black (no two red nodes can be adjacent).
  5. Black Height Property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Step-by-Step Insertion Operation

Step 1: Regular Binary Search Tree (BST) Insertion

The new node is inserted as in a regular BST, but we color the new node red. This is because inserting a red node causes fewer violations of the Red-Black properties than inserting a black node.

Step 2: Check for Violations

After insertion, we need to check if the Red-Black properties are violated. The only properties that can be violated are the root property, the red node property, and the black height property.

Step 3: Fix Violations

If there are violations, we fix them through a series of rotations and recoloring. The fixing process is iterative and continues until all properties are satisfied. The possible cases that can occur after insertion are:

  1. Case 1: New Node is at Root

    • If the new node is the root node, simply recolor it to black.

  2. Case 2: Parent of New Node is Black

    • If the parent of the new node is black, then the tree is still valid, and no further action is required.

  3. Case 3: Parent and Uncle are Red

    • Recolor the parent and uncle to black.
    • Recolor the grandparent to red.
    • Set the grandparent as the new node and repeat the process from Step 2.

  4. Case 4: Parent is Red but Uncle is Black

    • This case is further divided into subcases based on the position of the new node (left or right child) and the position of the parent (left or right child of the grandparent).
    • Perform rotations to balance the tree. There are two types of rotations: left rotation and right rotation.

Step 4: Perform Rotations and Recoloring

Depending on the case encountered in Step 3, we may need to perform rotations:

  • Left Rotation: This is a rotation on node x where x becomes the left child of its right child. The left child of the new parent (formerly the right child of x) becomes the right child of x.
  • Right Rotation: This is a rotation on node x where x becomes the right child of its left child. The right child of the new parent (formerly the left child of x) becomes the left child of x.

Rotations are used to move the nodes around so that we can recolor them and restore the Red-Black properties.

Step 5: Update the Root and Recolor

After the rotations and recoloring, the root of the tree might have changed. We need to update the root if necessary and ensure that it is colored black.

Example

Let's consider an example where we insert a node into a Red-Black Tree:

  1. Insert the new node as a red node in the correct position using BST rules.
  2. If the new node's parent is black, we are done. If not, check the color of the uncle.
  3. If the uncle is red, recolor the parent and uncle to black and the grandparent to red. Then, move to the grandparent and repeat the process.
  4. If the uncle is black, perform the appropriate rotation:
    • If the new node is a right child and the parent is a left child, perform a left rotation on the parent.
    • If the new node is a left child and the parent is a right child, perform a right rotation on the parent.
  5. After the rotation, the new node and its parent will have switched roles. Now perform a rotation on the grandparent (right if the new node is on the left, left if on the right) and recolor the new parent to black and the grandparent to red.

By following these steps, the Red-Black Tree properties are preserved after each insertion.