Java Red-Black Tree Tutorial 🌲🔒

Welcome to our comprehensive Java Red-Black Tree tutorial! In this lesson, we'll dive deep into one of the most efficient self-balancing binary search trees. By the end of this tutorial, you'll have a solid understanding of Red-Black Trees, and you'll even write your own implementation. Let's get started!

1. Introduction to Red-Black Trees 🌲

Red-Black Trees are a type of self-balancing binary search tree, and they offer several advantages over traditional binary search trees. The primary benefits include:

Fast insertion and deletion: The self-balancing property ensures that the tree remains efficient even after many operations.
Guaranteed height: The height of a Red-Black Tree is logarithmic, which means it grows slowly as more elements are added.
Easy to implement: Although it might seem complex at first glance, the Red-Black Tree is easier to implement compared to other self-balancing data structures like AVL Trees.

2. Properties and Operations 🔒

Before we delve into the implementation, let's take a look at the properties and operations that make Red-Black Trees unique.

Properties

Every node has a color: Nodes can be either red or black.
Root node is black: The root of the tree must always be black.
Leaf (null) nodes are black: Even though leaf nodes don't store data, they're considered black for the sake of the properties.
Red nodes cannot have red children: A red node cannot have any red child nodes.
Black height is twice that of red height: If we consider the number of red nodes as R and the number of black nodes as B, then the height of the red subtree (R) is always less than or equal to the height of the black subtree (B) by one.
Every path from a node (N) to any of its descendant null nodes contains the same number of black nodes

Operations

Insertion: Adding a new node to the tree while maintaining the Red-Black Tree properties.
Deletion: Removing a node from the tree while maintaining the Red-Black Tree properties.
Rotation: Used to rebalance the tree by swapping the positions of nodes. There are two types of rotations: Left Rotation (LL, LR, RL, RR) and Right Rotation (LL, LR, RL, RR).

3. Implementation Details 💻

In this section, we'll discuss the implementation details for our Red-Black Tree. We'll use the following types:

RedBlackNode: Represents a single node in the Red-Black Tree.
RedBlackTree: Represents the Red-Black Tree data structure.

Here's the complete implementation of the Red-Black Tree:

java

public class RedBlackNode {
    private final int value;
    private RedBlackNode left, right;
    private boolean color; // true for red, false for black
    private int height;

    // Constructor
    public RedBlackNode(int value) {
        this.value = value;
        this.left = this.right = null;
        this.color = true; // default to red
        this.height = 0;
    }

    // Getters and Setters
    public int getValue() {
        return value;
    }

    public RedBlackNode getLeft() {
        return left;
    }

    public RedBlackNode getRight() {
        return right;
    }

    public boolean getColor() {
        return color;
    }

    public int getHeight() {
        return height;
    }

    // Update height
    public void updateHeight() {
        this.height = 1 + Math.max(getLeft().getHeight(), getRight().getHeight());
    }

    // Calculate balance factor
    public int getBalanceFactor() {
        return getLeft().getHeight() - getRight().getHeight();
    }
}

public class RedBlackTree {
    private RedBlackNode root;

    // Getter for the root
    public RedBlackNode getRoot() {
        return root;
    }

    // Perform a left rotation
    private void leftRotate(RedBlackNode node) {
        // Create a new temporary node for the rotation
        RedBlackNode newNode = node.getRight();
        node.right = newNode.left;
        newNode.left = node;

        // Update heights and colors
        newNode.updateHeight();
        node.updateHeight();

        // Set the new root if it's the root of the tree
        if (newNode.getLeft() == null) {
            root = newNode;
        }
    }

    // Perform a right rotation
    private void rightRotate(RedBlackNode node) {
        // Create a new temporary node for the rotation
        RedBlackNode newNode = node.getLeft();
        node.left = newNode.right;
        newNode.right = node;

        // Update heights and colors
        newNode.updateHeight();
        node.updateHeight();

        // Set the new root if it's the root of the tree
        if (newNode.getRight() == null) {
            root = newNode;
        }
    }

    // Insert a new node into the Red-Black Tree
    public void insert(RedBlackNode node) {
        // Base case: the tree is empty
        if (root == null) {
            root = node;
            return;
        }

        RedBlackNode currentNode = root;
        RedBlackNode parentNode = null;

        // Traverse the tree to find the correct position for the new node
        while (true) {
            parentNode = currentNode;
            // Insert the new node as a left child
            if (node.getValue() < currentNode.getValue()) {
                currentNode = currentNode.getLeft();
                if (currentNode == null) {
                    parentNode.left = node;
                    break;
                }
            }
            // Insert the new node as a right child
            else {
                currentNode = currentNode.getRight();
                if (currentNode == null) {
                    parentNode.right = node;
                    break;
                }
            }
        }

        // Perform the necessary rotations and color adjustments to maintain the properties of the Red-Black Tree
        // ...
    }
}

4. Practical Example 📝

Now that we've discussed the implementation, let's take a look at a practical example of using a Red-Black Tree to sort and search a list of integers.

java

public static void main(String[] args) {
    RedBlackTree redBlackTree = new RedBlackTree();
    int[] values = {50, 3, 6, 8, 40, 70, 9, 15, 4, 5, 60, 7, 45};

    for (int value : values) {
        redBlackTree.insert(new RedBlackNode(value));
    }

    System.out.println("Sorted list:");
    inOrderTraversal(redBlackTree.getRoot());
}

private static void inOrderTraversal(RedBlackNode node) {
    if (node != null) {
        inOrderTraversal(node.getLeft());
        System.out.print(node.getValue() + " ");
        inOrderTraversal(node.getRight());
    }
}

Java Red-Black Tree Tutorial 🌲🔒

Java Red-Black Tree Tutorial 🌲🔒

Table of Contents 📝

1. Introduction to Red-Black Trees 🌲

2. Properties and Operations 🔒

Properties

Operations

3. Implementation Details 💻

4. Practical Example 📝

5. Quiz 🎯