Red-Black Trees in Java

In computer science, a red-black tree is a type of self-balancing binary search tree. It is a data structure used to store and manage data efficiently. It is one of the most popular data structures in the world, used in many applications. Red-black trees are popular because of their efficient search, insert, delete, and update operations. They are also relatively easy to implement and maintain.

In this article, we’ll discuss how red-black trees work, their time complexity for access, search, insertion, and deletion, and their space complexity. We’ll also provide Java code samples throughout to illustrate each topic.

What Is a Red-Black Tree?

A red-black tree is a type of binary search tree, which means it has two children for each node: a left child and a right child. The left child is always less than its parent, and the right child is always greater than its parent.

In a red-black tree, each node also has a color, which can be either red or black. The color of a node is determined by its parent’s color and the colors of its children. A node can have up to two children, so it can have up to three colors: red, black, or a combination of the two.

Red-black trees are self-balancing, which means they maintain a certain level of balance as data is inserted and deleted. This makes them efficient for searching, inserting, deleting, and updating data.

Properties of Red-Black Trees

Red-black trees have certain properties that make them efficient for searching, inserting, deleting, and updating data. These properties are:

• Every node is either red or black.
• The root node is always black.
• All leaf nodes (null nodes) are black.
• All red nodes must have two black children.
• Every path from the root to a leaf must contain the same number of black nodes.

These properties ensure that the tree is balanced and that data can be efficiently inserted, deleted, and updated.

Time Complexity

The time complexity of a red-black tree is dependent on the number of nodes in the tree. The average time complexity for searching, insertion, deletion, and update operations is O(log n), where n is the number of nodes in the tree. The worst-case time complexity for these operations is O(n).

Space Complexity

The space complexity of a red-black tree is O(n), where n is the number of nodes in the tree. This means that the tree uses O(n) space to store data, regardless of the size of the data.

Java Code

Now, let’s look at some Java code to illustrate how a red-black tree works.

// Node class to represent a node in a red-black tree
class Node {
  int data;
  Node left, right;
  Color color;
 
  Node(int data) {
    this.data = data;
    left = right = null;
    color = Color.RED;
  }
}

// Enum to represent the color of a node
enum Color {
  RED, BLACK;
}

// Class to represent a red-black tree
class RedBlackTree {
  Node root;
 
  RedBlackTree() {
    root = null;
  }
 
  // Insert a node into the tree
  void insert(int data) {
    root = insertNode(root, data);
  }
 
  // Recursive function to insert a node into the tree
  private Node insertNode(Node node, int data) {
    // If the tree is empty, create a new node and set it as the root
    if (node == null) {
      node = new Node(data);
    }
 
    // If the data is smaller than the node, go left
    else if (data < node.data) {
      node.left = insertNode(node.left, data);
    }
 
    // If the data is greater than the node, go right
    else if (data > node.data) {
      node.right = insertNode(node.right, data);
    }
 
    // Set the color of the node
    node.color = Color.RED;
 
    // Return the node
    return node;
  }
 
  // Search for a node in the tree
  boolean search(int data) {
    return searchNode(root, data);
  }
 
  // Recursive function to search for a node in the tree
  private boolean searchNode(Node node, int data) {
    // If the tree is empty, return false
    if (node == null) {
      return false;
    }
 
    // If the data is smaller than the node, go left
    if (data < node.data) {
      return searchNode(node.left, data);
    }
 
    // If the data is greater than the node, go right
    else if (data > node.data) {
      return searchNode(node.right, data);
    }
 
    // If the data is equal to the node, return true
    else {
      return true;
    }
  }
 
  // Delete a node from the tree
  void delete(int data) {
    root = deleteNode(root, data);
  }
 
  // Recursive function to delete a node from the tree
  private Node deleteNode(Node node, int data) {
    // If the tree is empty, return null
    if (node == null) {
      return null;
    }
 
    // If the data is smaller than the node, go left
    if (data < node.data) {
      node.left = deleteNode(node.left, data);
    }
 
    // If the data is greater than the node, go right
    else if (data > node.data) {
      node.right = deleteNode(node.right, data);
    }
 
    // If the data is equal to the node, delete the node
    else {
      // If the node is a leaf node, set it to null
      if (node.left == null && node.right == null) {
        node = null;
      }
 
      // If the node has one child, set it to the child
      else if (node.left == null) {
        node = node.right;
      }
      else if (node.right == null) {
        node = node.left;
      }
 
      // If the node has two children, replace it with its in-order successor
      else {
        Node successor = findMin(node.right);
        node.data = successor.data;
        node.right = deleteNode(node.right, successor.data);
      }
    }
 
    // Set the color of the node
    node.color = Color.BLACK;
 
    // Return the node
    return node;
  }
 
  // Find the in-order successor of a node
  private Node findMin(Node node) {
    // If the tree is empty, return null
    if (node == null) {
      return null;
    }
 
    // If the node has no left child, it is the in-order successor
    if (node.left == null) {
      return node;
    }
 
    // Otherwise, go left
    return findMin(node.left);
  }
}

Conclusion

Red-black trees are a type of self-balancing binary search tree. They are popular because they maintain a certain level of balance as data is inserted and deleted, making them efficient for searching, inserting, deleting, and updating data. Their time complexity for access, search, insertion, and deletion is O(log n) on average and O(n) in the worst case. Their space complexity is O(n).

Exercises

public static boolean isValidRedBlackTree(Node root) {
    if (root == null) {
        return true;
    }
 
    // Check if root is black
    if (root.color != Color.BLACK) {
        return false;
    }
 
    // Check if all red nodes have two black children
    if (!checkRedNodeProperties(root)) {
        return false;
    }
 
    // Check if all paths from root to leaves have same number of black nodes
    int blackNodesCount = getBlackNodesCount(root);
    if (!checkBlackNodesCount(root, blackNodesCount)) {
        return false;
    }
 
    return true;
}

private static boolean checkRedNodeProperties(Node node) {
    if (node == null) {
        return true;
    }
 
    if (node.color == Color.RED && 
        (node.left == null || node.left.color != Color.BLACK) &&
        (node.right == null || node.right.color != Color.BLACK)) {
        return false;
    }
 
    return checkRedNodeProperties(node.left) && checkRedNodeProperties(node.right);
}

private static int getBlackNodesCount(Node node) {
    if (node == null) {
        return 0;
    }
 
    if (node.color == Color.BLACK) {
        return 1 + getBlackNodesCount(node.left) + getBlackNodesCount(node.right);
    } else {
        return getBlackNodesCount(node.left) + getBlackNodesCount(node.right);
    }
}

private static boolean checkBlackNodesCount(Node node, int blackNodesCount) {
    if (node == null) {
        return true;
    }
 
    if (node.color == Color.BLACK) {
        blackNodesCount--;
    }
 
    if (blackNodesCount != getBlackNodesCount(node.left) ||
        blackNodesCount != getBlackNodesCount(node.right)) {
        return false;
    }
 
    return checkBlackNodesCount(node.left, blackNodesCount) && 
           checkBlackNodesCount(node.right, blackNodesCount);
}

public static Node insertNode(Node root, int data) {
    if (root == null) {
        // Create a new node and set it as the root
        root = new Node(data);
        root.color = Color.BLACK;
    } else if (data < root.data) {
        // If the data is smaller than the node, go left
        root.left = insertNode(root.left, data);
    } else if (data > root.data) {
        // If the data is greater than the node, go right
        root.right = insertNode(root.right, data);
    } else {
        // If the data is equal to the node, do nothing
        return root;
    }
 
    // Check if the node needs to be balanced
    return balanceTree(root);
}

public static boolean searchNode(Node node, int data) {
    if (node == null) {
        // If the tree is empty, return false
        return false;
    } else if (data < node.data) {
        // If the data is smaller than the node, go left
        return searchNode(node.left, data);
    } else if (data > node.data) {
        // If the data is greater than the node, go right
        return searchNode(node.right, data);
    } else {
        // If the data is equal to the node, return true
        return true;
    }
}

public static Node deleteNode(Node node, int data) {
    if (node == null) {
        // If the tree is empty, return null
        return null;
    } else if (data < node.data) {
        // If the data is smaller than the node, go left
        node.left = deleteNode(node.left, data);
    } else if (data > node.data) {
        // If the data is greater than the node, go right
        node.right = deleteNode(node.right, data);
    } else {
        // If the data is equal to the node, delete the node
        if (node.left == null && node.right == null) {
            // If the node is a leaf node, set it to null
            node = null;
        } else if (node.left == null) {
            // If the node has one child, set it to the child
            node = node.right;
        } else if (node.right == null) {
            // If the node has one child, set it to the child
            node = node.left;
        } else {
            // If the node has two children, replace it with its in-order successor
            Node successor = findMin(node.right);
            node.data = successor.data;
            node.right = deleteNode(node.right, successor.data);
        }
    }
 
    // Check if the node needs to be balanced
    return balanceTree(node);
}

public static Node findMin(Node node) {
    // If the tree is empty, return null
    if (node == null) {
        return null;
    }
 
    // If the node has no left child, it is the in-order successor
    if (node.left == null) {
        return node;
    }
 
    // Otherwise, go left
    return findMin(node.left);
}