What is a red-black tree?

A red-black tree is a self-balancing binary search tree where each node is colored red or black. A set of color rules keeps the longest path from the root to a leaf at most twice the shortest one, so the tree stays roughly balanced.

What are the rules of a red-black tree?

Every node is red or black. The root is black. Every leaf (NIL) is black. A red node cannot have a red child. Every path from a node down to its NIL leaves contains the same number of black nodes (the black height).

Why does a red-black tree guarantee O(log n) height?

Every root-to-leaf path has the same number of black nodes, and red nodes cannot be adjacent, so the longest path (alternating red and black) is at most twice the shortest path (all black). This limits the height to about 2 log 2 (n + 1).

What happens after inserting a node into a red-black tree?

The new node is colored red, so the black height does not change. If its parent is also red, the rules are restored by recoloring (when the uncle is red) or by rotations plus recoloring (when the uncle is black).

Why is a new node colored red instead of black?

Adding a black node would increase the black height on one path only, breaking rule 5 everywhere along that path. Adding a red node can only break the "no two reds in a row" rule, which is easier to fix locally.

Write a Java class for a red-black tree node.

Java example: class RedBlackNode { static final boolean RED = true; static final boolean BLACK = false; int key; boolean color = RED; // new nodes start red RedBlackNode left, right, parent; RedBlackNode(int key) { this.key = key; } boolean isRed() { return color == RED; } }

Write a Java method that checks the no-red-red rule.

Java example: class RBNode { int key; boolean red; RBNode left, right; } class CheckRedRule { static boolean noRedRed(RBNode node) { if (node == null) { return true; } if (node.red && ((node.left != null && node.left.red) || (node.right != null && node.right.red))) { return false; // a red node with a red child } return noRedRed(node.left) && noRedRed(node.right); } }

What is the time complexity of red-black tree operations?

Search, insert and delete are all O(log n). An insert needs at most 2 rotations, and a delete at most 3, plus recoloring that may move up the tree.

Where are red-black trees used in Java?

TreeMap and TreeSet are red-black trees. Since Java 8, HashMap also converts a bucket with many collisions (more than 8 entries, once the table has at least 64 buckets) into a red-black tree, so lookups in that bucket become O(log n) instead of O(n).

Write a Java example that uses a TreeMap as a sorted, balanced map.

Each of these operations runs in O(log n) because the map is a red-black tree.

Red Black Tree | JavaByTechie

What is Red-Black tree in Data Structures?

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.

The Red-Black Tree is introduced by Rudolf Bayer in the year 1972.

Properties of Red Black Tree

Red-Black Tree always be a Binary Search Tree (BST).
Each node in a Red-Black tree will be either RED or BLACK in color.
The ROOT node must be colored BLACK.
All the child nodes of RED colored node must be colored BLACK. (Two consecutive RED nodes not possible in the tree).
There should be the same number of BLACK colored nodes in all the paths of the tree.
Every leaf node (also called NULL or NIL node) must be colored BLACK.

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

In a Red-Black Tree, we can perform the following types of operations.

Insertion
Deletion
Search
Rotation

Implement a Red-Black Tree in Java

RedBlackTree.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();
  }
}

Output

R----45(BLACK)
L----30(BLACK)
|  L----25(RED)
R----60(BLACK)
   L----50(RED)
   R----70(RED)

After deleting an element:
R----45(BLACK)
  L----30(BLACK)
  |  L----25(RED)
  R----60(BLACK)
    L----50(RED)

Advantages of Red-Black Trees

Self-balancing binary search tree.
Efficient insertion and deletion operations with a time complexity of O(log n), which ensures balanced height and optimal search times.
Red-Black Trees support dynamic insertions and deletions while maintaining balance, making them suitable for applications where data changes frequently.
Compared to other balanced trees like AVL trees, Red-Black Trees require less strict balancing, which can reduce the number of rotations and improve performance in practice.
Red-black trees provide strong guarantees on performance, making them suitable for applications where consistent and predictable performance is critical.
Red-Black Trees are used in many real-world applications, such as: maps, sets, priority queues and many more.

Disadvantages of Red-Black Trees

Complex Implementation.
Overhead of Balancing.
Slower than Hash Tables.
Not Ideal for Small Datasets./span>
Memory Overhead - Each node of a red-black tree requires extra memory to store the color (red/black).
Less Strict Balancing than AVL Trees.

When to Use Red-Black Trees

There are the following scenarios where we can use Red-Black Tree:

It can be used if we need a self-balancing BST with guaranteed O(log n) performance for all operations.
Uesful if application requires frequent insertion and deletion operations with ordered data such as:
- Database indexing.
- Language libraries.
- Real-time systems where predictable performance is critical.

When to Avoid Red-Black Trees

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

Avoid Red-Black Trees for small datasets or when lookup speed is the primary concern (use hash tables instead).
If we need faster lookups and can tolerate slower insertions/deletions, consider AVL trees.

Red-Black Vs AVL Tree

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

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.

Help Us Improve

Red Black Tree