Inserting or deleting nodes in a Red-Black tree involves specific procedures to maintain the tree's balanced properties. Here’s a detailed explanation of how these operations affect a Red-Black tree:
Insertion
Steps for Insertion:
Standard BST Insertion: Insert the new node as you would in a standard Binary Search Tree (BST). The new node is always colored red[1][4][8].
Fixing Violations: After insertion, the tree might violate the Red-Black properties. The main property that might be violated is having two consecutive red nodes (parent and child both red). To fix this, the following steps are taken:
Recoloring: If the parent and the uncle of the newly inserted node are both red, recolor the parent and the uncle to black, and the grandparent to red. This might propagate the violation upwards, requiring further fixes[1][4][8].
Rotations: If recoloring is not sufficient, rotations are used. There are four cases to handle:
Left Rotation: Applied when the new node is the right child of its parent, and the parent is the left child of its grandparent.
Right Rotation: Applied when the new node is the left child of its parent, and the parent is the right child of its grandparent.
Left-Right Rotation: Applied when the new node is the left child of its parent, and the parent is the left child of its grandparent.
Right-Left Rotation: Applied when the new node is the right child of its parent, and the parent is the right child of its grandparent[1][4][8].
Example:
Insert a node with value 15 into a Red-Black tree. Initially, it is colored red. If its parent is black, no further action is needed. If its parent is red, check the color of the uncle and apply recoloring or rotations as necessary[1][4][8].
Deletion
Steps for Deletion:
Standard BST Deletion: Remove the node as you would in a standard BST. If the node to be deleted has two children, replace it with its in-order successor or predecessor[2][5][11].
Fixing Violations: Deleting a node might violate the Red-Black properties, particularly the black height property. The following steps are taken to fix these violations:
Double Black: If a black node is deleted, it might cause a "double black" situation, where the path from the root to some leaves has one fewer black node. This is fixed by:
Recoloring and Rotations: Depending on the color of the sibling and its children, different cases ...
