Discuss the insertion operation in Red Black tree. Write the algorithm of Selection sort and find its time complexity.

Q.) Discuss the insertion operation in Red Black tree. Write the algorithm of Selection sort and find its time complexity.

 Subject: Data Structures

Insertion in a Red-Black Tree

Red-Black Trees are a type of 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. Red/Black Property: Every node is colored, either red or black.
  2. Root Property: The root is black.
  3. Leaf Property: Every leaf (NIL node) is black.
  4. Red Property: If a red node has children then, the children are always black.
  5. Depth Property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

The insertion operation in a Red-Black Tree is performed in two steps:

  1. Binary Search Tree (BST) Insert: The new node is inserted as in a regular BST, and the new node is colored red.
  2. Red-Black Fixup: The tree is then adjusted to maintain the Red-Black properties.

Step-by-Step Insertion Algorithm:

  1. Perform Standard BST Insert: Insert the new node as you would in a regular binary search tree. Color the new node red.
  2. Maintain Red-Black Tree Properties: If the new node's parent is black, the properties are maintained. If the parent is red, we have to do the following adjustments:
    • Case 1: If the uncle of the new node is also red, recolor the parent and uncle to black and the grandparent to red. Then, move the current node pointer to the grandparent and repeat the process.
    • Case 2: If the new node's parent is red but the uncle is black and the new node is a right child, perform a left rotation on the parent. This transforms it into Case 3.
    • Case 3: If the new node's parent is red, the uncle is black, and the new node is a left child, perform a right rotation on the grandparent, then swap the colors of the parent and grandparent.

Example of Insertion:

Let's say we are inserting the value 8 into the following Red-Black Tree:

     10(B)
     /   \
   5(R)  15(B)
  1. BST Insert: Insert 8 as a red node.
     10(B)
     /   \
   5(R)  15(B)
     \
     8(R)

  1. Red-Black Fixup: Since the new node's parent 5 is red, we have a violation of the Red-Black properties. The uncle of 8 is black (NIL node), so we are in Case 3.

  2. Case 3 Fix: Rotate the grandparent 10 to the right and swap the colors of the parent 5 and grandparent 10.

     5(B)
     /   \
   2(R)  10(R)
         /   \
        8(B) 15(B)

Now the tree satisfies all Red-Black properties.

Selection Sort Algorithm

Selection sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part and moving it to the beginning.

Algorithm:

1. Start with the first element in the array as the minimum.
2. For each unsorted element in the array:
   a. If the element is less than the current minimum, update the minimum to be this element.
3. Swap the first unsorted element with the minimum found in step 2.
4. Move the boundary of the unsorted array by one element to the right.
5. Repeat steps 2-4 until the entire array is sorted.

Example:

Consider the array [64, 25, 12, 22, 11]. Here's how Selection Sort would sort the array:

Initial Array: [64, 25, 12, 22, 11]

  • First pass (find min, swap with first element):
    • Min = 11, Swap 64 with 11
    • [11, 25, 12, 22, 64]
  • Second pass (find min from second element onwards, swap with second element):
    • Min = 12, Swap 25 with 12
    • [11, 12, 25, 22, 64]
  • Third pass (find min from third element onwards, swap with third element):
    • Min = 22, Swap 25 with 22
    • [11, 12, 22, 25, 64]
  • Fourth pass (find min from fourth element onwards, swap with fourth element):
    • Min = 25, Swap 25 with 25 (no change as it is already in correct position)
    • [11, 12, 22, 25, 64]

Sorted Array: [11, 12, 22, 25, 64]

Time Complexity of Selection Sort

The time complexity of Selection Sort is determined by the number of comparisons and swaps it makes.

  • Best Case: (O(n^2)) - Even if the array is already sorted, it still goes through the entire array to find the minimum element for each position.
  • Average Case: (O(n^2)) - On average, it performs the same number of comparisons as the worst case.
  • Worst Case: (O(n^2)) - When the array is sorted in reverse order, it still performs the same number of comparisons.

Selection Sort does not adapt to the initial order of the elements, and hence its time complexity remains quadratic in all cases. It is not suitable for large datasets due to its (O(n^2)) time complexity.