Red Black Tree

A Red-Black tree is a type of self-balancing binary search tree in which every node is colored either RED or BLACK. The properties of a Red-Black tree decide the color of a node.

In the Red-black tree, every node contains an extra bit that represents a color to ensure that the tree is balanced during any operations performed on the tree, like insertion, deletion, etc.

Properties of Red Black Tree:

Example of a Red-Black Tree

In the given tree above, all the nodes are satisfying all the properties of a Red-Black Tree.

Why use a Red-Black tree in application development?

A Red-Black Tree data structure provides fast and efficient access to sorted data. It allows us to save any type of data that can be compared, including numbers, strings, dates, and objects. It can also handle dynamic operations like data insertion and deletion without impacting the tree's performance or balanced structure.

A red-black tree can also be used to build abstract data types like sets, maps, and priority queues.

Operations on Red-Black Tree:

Implement a Red-Black Tree in Java

  
  //A Java program to implement a Red-Black Tree
  class Node {
    int data;       // Store actual data
    Node parent;    // Store address of parent node
    Node left;      // Store address of left node
    Node right;     // Store address of right node
    int color;      // Store color of the node
  }
  
  public class RedBlackTree {
    private Node root;
    private Node TNULL;
    
    // Constructor
    public RedBlackTree() {
      TNULL = new Node();
      TNULL.color = 0;
      TNULL.left = null;
      TNULL.right = null;
      root = TNULL;
    }
    
    // Preorder
    private void preOrderHelper(Node node) {
      if (node != TNULL) {
        System.out.print(node.data + " ");
        preOrderHelper(node.left);
        preOrderHelper(node.right);
      }
    }
    
    // Inorder
    private void inOrderHelper(Node node) {
      if (node != TNULL) {
        inOrderHelper(node.left);
        System.out.print(node.data + " ");
        inOrderHelper(node.right);
      }
    }
    
    // Post order
    private void postOrderHelper(Node node) {
      if (node != TNULL) {
        postOrderHelper(node.left);
        postOrderHelper(node.right);
        System.out.print(node.data + " ");
      }
    }
    
    // Search the tree
    private Node searchTreeHelper(Node node, int key) {
      if (node == TNULL || key == node.data) {
        return node;
      }
      
      if (key < node.data) {
        return searchTreeHelper(node.left, key);
      }
      return searchTreeHelper(node.right, key);
    }
    
    // Balance the tree after deletion of a node
    private void fixDelete(Node x) {
      Node s;
      while (x != root && x.color == 0) {
        if (x == x.parent.left) {
          s = x.parent.right;
          if (s.color == 1) {
            s.color = 0;
            x.parent.color = 1;
            leftRotate(x.parent);
            s = x.parent.right;
          }
          
          if (s.left.color == 0 && s.right.color == 0) {
            s.color = 1;
            x = x.parent;
          } else {
            if (s.right.color == 0) {
              s.left.color = 0;
              s.color = 1;
              rightRotate(s);
              s = x.parent.right;
            }
            
            s.color = x.parent.color;
            x.parent.color = 0;
            s.right.color = 0;
            leftRotate(x.parent);
            x = root;
          }
        } else {
          s = x.parent.left;
          if (s.color == 1) {
            s.color = 0;
            x.parent.color = 1;
            rightRotate(x.parent);
            s = x.parent.left;
          }
          
          if (s.right.color == 0 && s.right.color == 0) {
            s.color = 1;
            x = x.parent;
          } else {
            if (s.left.color == 0) {
              s.right.color = 0;
              s.color = 1;
              leftRotate(s);
              s = x.parent.left;
            }
            
            s.color = x.parent.color;
            x.parent.color = 0;
            s.left.color = 0;
            rightRotate(x.parent);
            x = root;
          }
        }
      }
      x.color = 0;
    }
    
    private void rbTransplant(Node u, Node v) {
      if (u.parent == null) {
        root = v;
      } else if (u == u.parent.left) {
        u.parent.left = v;
      } else {
        u.parent.right = v;
      }
      v.parent = u.parent;
    }
    
    private void deleteNodeHelper(Node node, int key) {
      Node z = TNULL;
      Node x, y;
      while (node != TNULL) {
        if (node.data == key) {
          z = node;
        }
        
        if (node.data <= key) {
          node = node.right;
        } else {
          node = node.left;
        }
      }
      
      if (z == TNULL) {
        System.out.println("Couldn't find key in the tree");
        return;
      }
      
      y = z;
      int yOriginalColor = y.color;
      if (z.left == TNULL) {
        x = z.right;
        rbTransplant(z, z.right);
      } else if (z.right == TNULL) {
        x = z.left;
        rbTransplant(z, z.left);
      } else {
        y = minimum(z.right);
        yOriginalColor = y.color;
        x = y.right;
        if (y.parent == z) {
          x.parent = y;
        } else {
          rbTransplant(y, y.right);
          y.right = z.right;
          y.right.parent = y;
        }
        
        rbTransplant(z, y);
        y.left = z.left;
        y.left.parent = y;
        y.color = z.color;
      }
      if (yOriginalColor == 0) {
        fixDelete(x);
      }
    }
    
    // Balance the node after insertion
    private void fixInsert(Node k) {
      Node u;
      while (k.parent.color == 1) {
        if (k.parent == k.parent.parent.right) {
          u = k.parent.parent.left;
          if (u.color == 1) {
            u.color = 0;
            k.parent.color = 0;
            k.parent.parent.color = 1;
            k = k.parent.parent;
          } else {
            if (k == k.parent.left) {
              k = k.parent;
              rightRotate(k);
            }
            k.parent.color = 0;
            k.parent.parent.color = 1;
            leftRotate(k.parent.parent);
          }
        } else {
          u = k.parent.parent.right;
          
          if (u.color == 1) {
            u.color = 0;
            k.parent.color = 0;
            k.parent.parent.color = 1;
            k = k.parent.parent;
          } else {
            if (k == k.parent.right) {
              k = k.parent;
              leftRotate(k);
            }
            k.parent.color = 0;
            k.parent.parent.color = 1;
            rightRotate(k.parent.parent);
          }
        }
        
        if (k == root) {
          break;
        }
      }
      root.color = 0;
    }
    
    private void printHelper(Node root, String indent, boolean last) {
      if (root != TNULL) {
        System.out.print(indent);
        if (last) {
          System.out.print("R----");
          indent += "   ";
        } else {
          System.out.print("L----");
          indent += "|  ";
        }
        
        String nodeColor = root.color == 1 ? "RED" : "BLACK";
        System.out.println(root.data + "(" + nodeColor + ")");
        printHelper(root.left, indent, false);
        printHelper(root.right, indent, true);
      }
    }
    
    public void preorder() {
      preOrderHelper(this.root);
    }
    
    public void inorder() {
      inOrderHelper(this.root);
    }
    
    public void postorder() {
      postOrderHelper(this.root);
    }
    
    public Node searchTree(int k) {
      return searchTreeHelper(this.root, k);
    }
    
    public Node minimum(Node node) {
      while (node.left != TNULL) {
        node = node.left;
      }
      return node;
    }
    
    public Node maximum(Node node) {
      while (node.right != TNULL) {
        node = node.right;
      }
      return node;
    }
    
    public Node successor(Node x) {
      if (x.right != TNULL) {
        return minimum(x.right);
      }
      
      Node y = x.parent;
      while (y != TNULL && x == y.right) {
        x = y;
        y = y.parent;
      }
      return y;
    }
    
    public Node predecessor(Node x) {
      if (x.left != TNULL) {
        return maximum(x.left);
      }
      
      Node y = x.parent;
      while (y != TNULL && x == y.left) {
        x = y;
        y = y.parent;
      }
      
      return y;
    }
    
    public void leftRotate(Node x) {
      Node y = x.right;
      x.right = y.left;
      
      if (y.left != TNULL) {
        y.left.parent = x;
      }
      
      y.parent = x.parent;
      
      if (x.parent == null) {
        this.root = y;
      } else if (x == x.parent.left) {
        x.parent.left = y;
      } else {
        x.parent.right = y;
      }
      
      y.left = x;
      x.parent = y;
    }
    
    public void rightRotate(Node x) {
      Node y = x.left;
      x.left = y.right;
      
      if (y.right != TNULL) {
        y.right.parent = x;
      }
      
      y.parent = x.parent;
      
      if (x.parent == null) {
        this.root = y;
      } else if (x == x.parent.right) {
        x.parent.right = y;
      } else {
        x.parent.left = y;
      }
      
      y.right = x;
      x.parent = y;
    }
    
    public void insert(int key) {
      Node node = new Node();
      node.parent = null;
      node.data = key;
      node.left = TNULL;
      node.right = TNULL;
      node.color = 1;
      
      Node y = null;
      Node x = this.root;
      
      while (x != TNULL) {
        y = x;
        if (node.data < x.data) {
          x = x.left;
        } else {
          x = x.right;
        }
      }
      
      node.parent = y;
      if (y == null) {
        root = node;
      } else if (node.data < y.data) {
        y.left = node;
      } else {
        y.right = node;
      }
      
      if (node.parent == null) {
        node.color = 0;
        return;
      }
      
      if (node.parent.parent == null) {
        return;
      }
      
      fixInsert(node);
    }
    
    public Node getRoot() {
      return this.root;
    }
    
    public void deleteNode(int data) {
      deleteNodeHelper(this.root, data);
    }
    
    public void printTree() {
      printHelper(this.root, "", true);
    }
    
    public static void main(String[] args) {
      // Create a RedBlack Tree
      RedBlackTree tree = new RedBlackTree();
      tree.insert(45);
      tree.insert(60);
      tree.insert(30);
      tree.insert(70);
      tree.insert(25);
      tree.insert(50);
      
      tree.printTree();
      
      System.out.println("\nAfter deleting an element:");
      tree.deleteNode(70);
      tree.printTree();
    }
  }

Advantages of Red-Black Trees

Disadvantages of Red-Black Trees

When to Use Red-Black Trees

When to Avoid Red-Black Trees

There are the following scenarios where we should avoid the uses of Red-Black Tree:

Red-Black Vs AVL Tree

In Summary

Red-Black Trees are a powerful and versatile data structure that provides a good balance between performance and complexity. They are particularly useful in scenarios where data is dynamic and ordered traversal is required. However, their complexity and overhead make them less suitable for small datasets or applications where simpler structures suffice.

Feature	Red-Black Tree	AVL Tree
Balanced	Less balanced	More balanced
Insertion/Deletion	Faster (fewer rotations required)	Slower (more rotations required)
Searching	Less efficient	Efficient search operations
Node color	Either red or black	No color
Balance factor	No balance factor for each node	All the nodes contain a balance factor (-1, 0, 1)
Processing time	Takes less	Takes more