Red - Black Trees 

Introduction

A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black

Properties 

1) Every node has a color either red or black. 

2) Root of tree is always black. 

3) There are no two adjacent red nodes (A red node cannot have a red parent or red child). 

4) Every path from a node (including root) to any of its descendant NULL node has the same  number of black nodes. 

5) Every leaf (NIL) is black. 

Example 

Size and Depth 

1. The height of a  Red-Black tree is always O(Logn) where n is the number of nodes in the tree.
2. The cost of these operations may become O(n) for a skewed Binary  tree.

Operations on RB- Trees

Rotation 

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:

• Left Rotation
• Right Rotation

Left Rotation

LEFT_ROTATE(T, x)
  y = x.right
  x.right = y.left
  if y.left != NULL
      y.left.parent = x
  y.parent = x.parent
  if x.parent == NULL //x is root
      T.root = y
  elseif x == x.parent.left // x is left child
      x.parent.left = y
  else // x is right child
      x.parent.right = y
  y.left = x
  x.parent = y

From the above code, you can easily see that rotation is a constant time taking process ($O\left(1\right)$).

Consider the following tree:

After applying left rotation on the node x, the node y will become the new root of the subtree and its left child will be x. And the previous left child of y will now become the right child of x.

Right Rotation

RIGHT_ROTATE(T, y)
   x = y.left
    y.left = x.right
    if x.right != T.nil
        x.right.p = y
    x.p = y.p
    if y.p == T.nil
        T.root = x
    else if y == y.p.right
        y.p.right = x
    else y.p.left = x
    x.right = y
    y.p = x

Now applying right rotation on the node y of the rotated tree, it will transform back to the original tree.

So right rotation on the node y will make x the root of the tree, y will become x's right child. And the previous right child of x will now become the left child of y.

Insertion 

Red Black Tree Insertion Rules:

1-If tree is empty, create new node as root node with color black 

2-If tree is not empty, create new node as leaf node with color red 

3-If parent of new node is black then exit 

4-If parent of new node is red, then check the color of parents sibling of new node 

a-If color is black or null then do suitable rotation & recolor 

b-If color is red then recolor & also check if parents parent of new node is not root node then recolor it & recheck 

INSERT(T, z)
  y = T.NIL
  x = T.root

  while x != T.NIL
      y = x
      if key[z] < key[x]
          x = key[x]
      else
          x = key[x]
  p[z] = y
  if y==T.NIL
      T.root = z
  else if key[z] < key[y]
      y.left = z
  else
      y.right = z

  z.left = T.NIL
  z.right = T.NIL
  z.color = RED
  INSERT_FIXUP(T, z)

Code for fixing the violation:

INSERT_FIXUP(T, z)
  while z.parent.color == red

      if z.parent == z.parent.parent.left //z.parent is left child
          y = z.parent.parent.right //uncle of z

          if y.color == red //case 1
              z.parent.color = black
              y.color = black
              z.parent.parent.color = red
              z = z.parent.parent

          else //case 2 or 3
              if z == z.parent.right //case 2
                  z = z.parent //marked z.parent as new z
                  LEFT_ROTATE(T, z) //rotated parent of orignal z

              //case 3
              z.parent.color = black // made parent black
              z.parent.parent.color = red // made grandparent red
              RIGHT_ROTATE(T, z.parent.parent) // right rotation on grandparent

      else // z.parent is right child
          code will be symmetric
  T.root.color = black

Insert 2, 1, 4, 5, 9, 3, 6, 7 following values into an initially empty red/black tree...

Insertion Cases:

Case 1:

1. Uncle is Red

Solution for Case 1:

1. Swap colors of Parent, Uncle, and Grandparent

2. Grandparent becomes the new node to check for violations

Case 2:

1. Uncle is Black

2a. Node is a Left Child of a Right Child

2b. Node is a Right Child of a Left Child

Solution for Case 2:

1a. Right rotate around Parent for 2a = Go to Case 3

1b. Left rotate around Parent for 2b = Go to Case 3

Case 3:

1. Uncle is Black

2a. Node is a Right Child of a Right Child

2b. Node is a Left Child of a Left Child

Solution for Case 3:

1a. Left rotate around Grandparent for 2a

1b. Right rotate around Grandparent for 2b

2. Swap colours of Parent and Grandparent

3. Grandparent becomes the new node to check for violations

Figure: Case 1 of the procedure RB-INSERT. Property 3 is violated, since x and its parent p[x] are both red. The same action is taken whether (a) x is a right child or (b) x is a left child. Each of the subtrees α, β,  γ, δ and ε has a black root, and each has the same black-height. The code for case 1 changes the colors of some nodes, preserving property 4: all downward paths from a node to a leaf have the same number of blacks. The while loop continues with node x's grandparent p[p[x]] as the new x. Any violation of property 3 can now occur only between the new x, which is red, and its parent, if it is red as well.

Figure: Cases 2 and 3 of the procedure RB-INSERT. As in case 1, property 3 is violated in either case 2 or case 3 because x and its parent p[x] are both red. Each of the subtrees α, β,  γ, and δ has a black root, and each has the same black-height. Case 2 is transformed into case 3 by a left rotation, which preserves property 4: all downward paths from a node to a leaf have the same number of blacks. Case 3 causes some color changes and a right rotation, which also preserve property 4. The while loop then terminates, because property 3 is satisfied: there are no longer two red nodes in a row.

Deletion 

Deletion Rules and Strategies:

First, search for an element to be deleted 

1. If the element to be deleted is in a node with only the left child, swap this node with one  containing the largest element in the left subtree. (This node has no right child).
2. If the element to be deleted is in a node with only right child, swap this node with the one  containing the smallest element in the right subtree (This node has no left child)
3. If the element to be deleted is in a node with both a left child and a right child, then swap  in any of the above two ways. While swapping, swap only the keys but not the colors
4. The item to be deleted is now having only a left child or only a right child. Replace this  node with its sole child. This may violate red constraints or black constraints. Violation of  red constraints can be easily fixed. 
5. If the deleted node is black, the black constraint is violated. The elimination of a black  node y causes any path that contains y to have one fewer black node. 
6. Two cases arise: 
1. The replacing node is red, in which case we merely color it black to make up for  the loss of one black node. 
2. The replacing node is black. 

RB-DELETE(T, z)
 1. if left [z] = nil [T] or right [z] = nil [T]
 2.     then y ← z
 3. else y ← TREE-SUCCESSOR (z)
 4. if left [y] ≠ nil [T]
 5.     then x ← left [y]
 6. else x ← right [y]
 7. p [x] ←  p [y]
 8. if p[y] = nil [T]
 9.     then root [T]  ← x
 10. else if y = left [p[y]]
 11.     then left [p[y]] ← x
 12. else right [p[y]] ← x
 13. if y≠ z
 14.     then key [z] ← key [y]
 15. copy y's satellite data into z
 16. if color [y] = BLACK
 17.     then RB-delete-FIXUP (T, x)
 18. return y

RB-DELETE-FIXUP(T, x)
  while x!= T.root and x.color == black
      if x == x.parent.left
          w = x.parent.right
          if w.color == red //case 1
              w.color = black
              x.parent.color = red
              LEFT-ROTATE(T, x.parent)
              w = x.parent.right
          if w.left.color == black and w.right.color == black //case 2
              w.color = red
              x = x.parent
          else //case 3 or 4
              if w.right.color == black //case 3
                  w.left.color = black
                  w.color = red
                  RIGHT-ROTATE(T, w)
                  w = x.parent.right
              //case 4
              w.color = x.parent.color
              x.parent.color = black
              w.right.color = black
              LEFT-ROTATE(T, x.parent)
              x = T.root
      else
          code will be symmetric
  x.color = black

Example: In a previous example, we found that the red-black tree that results from successively inserting the keys 41,38,31,12,19,8 into an initially empty tree. Now show the red-black trees that result from the successful deletion of the keys in the order 8, 12, 19,31,38,41.

Solution:

Delete 38

Delete 41

Deletion Cases:

Case 1: (lines 5-8 of RB-DELETE-FIXUP and Figure 14.7(a)) occurs when node w, the sibling of node x, is red. Since w must have black children, we can switch the colors of w and p[x] and then perform a left-rotation on p[x] without violating any of the red-black properties. The new sibling of x, one of w's children, is now black, and thus we have converted case 1 into case 2, 3, or 4.

Cases 2, 3, and 4 occur when node w is black; they are distinguished by the colors of w's children. In case 2 (lines 10-11 of RB-DELETE-FIXUP and Figure 14.7(b)), both of w's children are black. Since w is also black, we take one black off both x and w, leaving x with only one black and leaving w red, and add an extra black to p[x]. We then repeat the while loop with p[x] as the new node x. Observe that if we enter case 2 through case 1, the color c of the new node x is red, since the original p[x] was red, and thus the loop terminates when it tests the loop condition.

Case 3: (lines 13-16 and Figure 14.7(c)) occurs when w is black, its left child is red, and its right child is black. We can switch the colors of w and its left child left[w] and then perform a right rotation on w without violating any of the red-black properties. The new sibling w of x is now a black node with a red right child, and thus we have transformed case 3 into case 4.

Case 4: (lines 17-21 and Figure 14.7(d)) occurs when node x's sibling w is black and w's right child is red. By making some color changes and performing a left rotation on p[x], we can remove the extra black on x without violating any of the red-black properties. Setting x to be the root causes the while loop to terminate when it tests the loop condition.

In Figure: The cases in the while loop of the procedure RB-DELETE. Darkened nodes are black, heavily shaded nodes are red, and lightly shaded nodes, which may be either red or black, are represented by c and c'. The letters α, β, . . .ζ,  represent arbitrary subtrees. In each case, the configuration on the left is transformed into the configuration on the right by changing some colors and/or performing a rotation. A node pointed to by x has an extra black. The only case that causes the loop to repeat is case 2. 
(a) Case I is transformed to case 2, 3, or 4 by exchanging the colors of nodes B and D and performing a left rotation. 
(b) In case 2, the extra black represented by the pointer x is moved up the tree by coloring node D red and setting x to point to node B. If we enter case 2 through case 1, the while loop terminates, since the color c is red. 
(c) Case 3 is transformed to case 4 by exchanging the colors of nodes C and D and performing a right rotation. (d) In case 4, the extra black represented by x can be removed by changing some colors and performing a left rotation (without violating the red-black properties), and the loop terminates.

Search 

Searching a node in Red Black Tree

1. Perform a binary search on the records in the current node.
2. If a record with the search key is found, then return that record.
3. If the current node is a leaf node and the key is not found, then report an unsuccessful search.
4. Otherwise, follow the proper branch and repeat the process.
5. Searching in Red Black tree takes O(log N) time complexity and O(N) space complexity.