Red Black Tree

In this article, we will look at the red black tree data structure and its different properties.Red black tree is an important data structure and provides a lot of benefits and advantages.

1. Red Black Tree

A red black tree is a self-balancing binary search tree where each node has an extra bit containing the information about the color of the node (RED or BLACK). A red black tree is an extension of the binary search tree. This color information is used to ensure that the tree remains balanced during the insertion or deletion process.

A red black tree is not as strictly balanced as an AVL tree but is approximately balanced.

With this extra bit of information, our tree contains the following information:

  • data – Data being stored in the red black tree.
  • left – left child information.
  • right – right child information.
  • color – color information of the node if the node is red or black.

2. Red and Back Tree Properties

Red black tree is a binary search tree with few properties which help in the self balancing the binary tree.Here are the red back tree properties which should be satisfied if we want to call it and red and black tree.

  1. The root node of the tree is always black.
  2. Every node of the tree is red or black.
  3. Every leaf node is black. If a node does not contain any child (no left or right child), we treat the child nodes as black.
  4. if a node is red, both children are black.
  5. every path from root node to the leaf node has the same number of black nodes.

Here is a sample red black tree

red black tree
Red back tree satisfying all the above 5 rules.

3. Benefits of Red Black Tree

A natural question arises as what is the benefit of the red black tree? If you read the article on the binary search tree and its time complexity, we will see the following major points.

  1. Most of the binary search tree operation will take O(h) time, where h is the height of the binary search tree.
  2. In the worst case (skewed binary tree), our tree is a linked list and search time will be O(n). We may have to go through each element of the tree.
  3. Red black tree guarantees all operations on the tree with a time complexity of O(log n) by balancing the tree with each insert and delete operation.
  4. The height of red and black tree will always be O(log n).

After each modification (insert or delete,)red black tree perform a re-arranging and repainting to maintain the properties of the tree and thus ensuring O(log n) time complexity.

OperationOperation Complexity
InsertO(log n)
DeleteO(log n)
SearchO(log n)

4. Red Back Tree Rotation

Before we look in to more details of the red black tree data structure, we need to understand how does a red-black tree ensure a balance? Every insert or delete operation can violate the red and black tree properties. To restore the properties of the tree, it re-balance itself with every insert and delete operation by:

  1. By changing the colors of some nodes.
  2. Balancing the tree by rotating it.

To understand the balancing of the tree, we need to understand the tree rotation. I am going to cover some basic of the tree rotation. There are 4 tree rotation in the self balancing tree.

  1. Left rotation.
  2. Right rotation.
  3. Left Right Rotation.
  4. Right Left Rotation.

To balance a red and black tree, we need a clear understanding of the left and right rotation.

4.1. Binary Search Tree Left Rotation

Before looking in to the pseudo-code, let’s look at the following image to understand how the left rotation work for a binary search tree.

Red Back Tree Balancing
How left rotation modify binary search tree

Here is the pseudo-code for the left rotation :

leftRotation (node)

1. y = right(node); //set as y
2. right(node) = left(y);  // change the y left subtree to node right subtree (check image)

3. if(left(y) not null)
5    than parent(left(y)) = node
6. parent(y) = parent(node) // make node parent as y parent

7 if(parent(node) is null)
   root =y // if node was the root node, now y will be root node

8 elseif(node = left(parent(node)))
    left(parent(node)) = y   // if node was the left child, y will become the new left child

9 else
   right(parent(node)) = y   // if node was the right child, y will become the new right child

10 left(y) = node
11 parent(node) = y

Binary tree right rotation is like the left rotation, change left with right to perform right rotation.When balancing our red and black tree, we will always perform a rotation on the grandparent.

4.1. Binary Search Tree Left Rotation in Java

If you are interested in the rotation for the binary search tree, here is the Java code for the left rotation in BST.

public void leftRotate(Node n) {
    if (n != null) {
        Node temp = n.right;
        n.right = temp.left;
        if (leftOf(temp) != null) {
            temp.left.parent = n;
        }
        temp.parent = n.parent;
        if (parentOf(n) == null) {
            root = temp;
        } else if (leftOf(parentOf(n)) == n) {
            n.parent.left = temp;
        } else {
            n.parent.right = temp;
        }
        temp.left = n;
        n.parent = temp;
    }
}

We will provide the complete source code at the end of this series.You can also download it from our GitHub repository

5. Balancing In Red and Black Tree

A red-Black tree is very similar to the binary search tree, and it performs the same operations as available on the binary search tree. The Red black tree grantees all operation with a constant time of O(log(n)) by self balancing the tree after each operation. The insert operation is same as the binary search tree insert operation, however at the end of each insert operation, we will call a method to fix any violation in the Red-Black tree. We will look at the following 2 steps in the section.

  1. A pseudo-code outlining how to fix the Red Black tree after insert.
  2. Step and step demonstration based on the pseudo-code.

Our pseudo-code will focus on fixing up the red and black tree after every insert operation. As outlined earlier, the insert operation is like the binary search tree insert operation.

insert(n){
    //insert logic same as BST
    rbTreeFix(n)
}

rbTreeFix(n)
//p - parent
color[n] = RED // every new inserted node will be marked red initially
while(n!=null and color[p[n]] RED)
 if(p[n] = left[p[p[n]]]){
   x= right[p[p[n]]]
   if(color[x] =RED)
      color[p[n]]=BLACK
      color[x]=BLACK
      color[p[p[y]]] =RED 
      n= p[p[n]]
    else
      if(n = right[p[n]]){
        n=p[n]
        leftRotate(n);
      }
      color[p[n]] = BLACK
      color[p[p[n]]] = RED
      rightRotate(p[p[n]])
 }
 else{
   //this is same except left is replaced by right  
    x= left[p[p[n]]]
   if(color[x] =RED)
      color[p[n]]=BLACK
      color[x]=BLACK
      color[p[p[y]]] =RED 
      n= p[p[n]]
    else
      if(n = left[p[n]]){
        n=p[n]
        rightRotate(n);
      }
      color[p[n]] = BLACK
      color[p[p[n]]] = RED
      leftRotate(p[p[n]])
 }
 color[root] - BLACK

So this seems to be a lot of conditions and combinations, but if you look closely, it’s not that complicated. Before we look into more details, remember these 2 rules:

  1. If uncle’s color is black, we will perform a rotation.
  2. if uncle’s color is red, we change the colors of parent, uncle and grand parent.

If we look into the above pseudo-code, we are setting the color of the newly inserted node as RED. We need to understand which property of the red and back tree will be violated after this step.

  1. We are setting the root node as BLACK (at the end of the code). Property 1 will also hold true.
  2. Property 2 holds true (every node is red and back), our newly inserted node is RED.
  3. Property 3 also holds true. The child nodes are null and treated as BLACK.
  4. Property 5 also holds true, as we have inserted the new node for some Null child.
  5. Only the property #4 can be violated if the parent of the newly added node is RED (if a node is red, both children should be black).

Let’s try to understand the above pseudo-code. I have added color code which outline 3 different use cases while working on the red and back tree data structure.

  • Case 1: N’s node uncle is red– Work based on the color of node’s uncle. If the color of the uncle’s node is red, we will perform the color flip.Once the color flip is complete, we will move to the grant parent and fix any violation (n= p[p[n]]). Let’s see how this will work out in our case.

Once we follow the case 1, we did a color flip and 8 become the new node. We will continue this process until it satisfy all the properties of a red and black tree.

  • Case 2 N’s uncle is Black and N is the right child– For both the case 2 and case 3, the color of n's uncle will be back.Both cases takes a different approach if n is a right or left child of its parent. For case 2, n is the right child of its parent and we will perform a left rotation and then follow the case 3. Let’s see how this will look like:
red and back tree
  • Case 3 N’s uncle is Black and N is the left child – Finally the case 3 will be executed where we will flip the color and perform a right rotation. Let’s see this in action:
Red Back Tree Rotation

There are total 6 different cases for the red back tree. We have covered the 3 and other are similar depending on whether n is left child or right child of the grandparent of n.

6. Implementing Red Black Tree In Java

We have covered the basic of the red and black tree basic and how to build it. Let’s see how to implement red and black tree in Java.

public class RedBlackTree {

    private Node root;
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public boolean insert(int data) {
        Node n = add(data);
        if (root == null) {
            root = n;
        }
        fixTree(n);
        return true;
    }

    private Node add(int data) {
        Node x = root;
        Node y = null;
        Node n = new Node(data);
        while (x != null) {
            y = x;
            if (x.data > data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        if (y == null) {
            y = n;
        } else if (y.data > data) {
            n.parent = y;
            y.left = n;
        } else {
            n.parent = y;
            y.right = n;
        }
        return n;
    }


    private void fixTree(Node n) {
        n.color = RED;

        while (n != null && n != root && n.parent.color == RED) {
            if (parentOf(n) == leftOf(parentOf(parentOf(n)))) {
                Node y = rightOf(parentOf(parentOf(n)));
                if (colorOf(y) == RED) {
                    // we do color flip.
                    setColor(parentOf(n), BLACK);
                    setColor(parentOf(parentOf(n)), RED);
                    setColor(y, BLACK);
                    n = parentOf(parentOf(n));
                } else {
                    // we do rotate
                    if (rightOf(parentOf(n)) == n) {
                        //right child
                        n = parentOf(n);
                        leftRotate(parentOf(n));

                    }
                    setColor(parentOf(n), BLACK);
                    setColor(parentOf(parentOf(n)), RED);
                    rightRotate(parentOf(parentOf((n))));
                }
            } else {

                Node y = leftOf(parentOf(parentOf(n)));
                if (colorOf(y) == RED) {
                    // we do color flip.
                    setColor(parentOf(n), BLACK);
                    setColor(parentOf(parentOf(n)), RED);
                    setColor(y, BLACK);
                    n = parentOf(parentOf(n));
                } else {
                    // we do rotate
                    if (leftOf(parentOf(n)) == n) {
                        //right child
                        n = parentOf(n);
                        rightRotate(parentOf(n));

                    }
                    setColor(parentOf(n), BLACK);
                    setColor(parentOf(parentOf(n)), RED);
                    leftRotate(parentOf(parentOf((n))));
                }
            }
        }

        root.color = BLACK;
    }

    private boolean colorOf(Node n) {
        return n != null ? n.color : BLACK;
    }

    private Node leftOf(Node n) {
        return n != null ? n.left : null;
    }

    private Node rightOf(Node n) {
        return n != null ? n.right : null;
    }

    private Node parentOf(Node n) {
        return n != null ? n.parent : null;
    }

    private void setColor(Node n, boolean color) {
        if (n != null) {
            n.color = color;
        }
    }

    private void leftRotate(Node n) {
        if (n != null) {
            Node temp = n.right;
            n.right = temp.left;
            if (leftOf(temp) != null) {
                temp.left.parent = n;
            }
            temp.parent = n.parent;
            if (parentOf(n) == null) {
                root = temp;
            } else if (leftOf(parentOf(n)) == n) {
                n.parent.left = temp;
            } else {
                n.parent.right = temp;
            }
            temp.left = n;
            n.parent = temp;
        }
    }

    private void rightRotate(Node n) {
        if (n != null) {
            Node temp = n.left;
            n.left = temp.right;

            if (rightOf(temp) != null) {
                temp.right.parent = n;
            }
            temp.parent = n.parent;
            if (parentOf(n) == null) {
                root = temp;
            } else if (rightOf(parentOf(n)) == n) {
                n.parent.right = temp;
            } else {
                n.parent.left = temp;
            }
            temp.right = n;
            n.parent = temp;

        }
    }


    public class Node {
        Node left, right, parent;
        int data;
        boolean color;

        public Node(int data) {
            this.data = data;
        }
    }

}

Summary

In this article, we saw the red and black tree data structure. We covered the following aspects of the red black tree.

  1. What is red and black tree?
  2. What are the properties of the red and black tree?
  3. What are the benefits of the tree?
  4. How to implement the tree in Java.

As Always the source code for this article is available on our GitHub repository.