4.3. Red-Black Trees

This section discusses a type of balanced binary search trees called Red-Black Trees.

Red-Black trees preserve the balance at most time by satisfying the following conditions:

• Every node is either red or black.

• The root and all leaves (null) are black.

• Every red node must have two black children.

• Every path from a given node to any of its leaves goes through the same number of black nodes.

Red-Black Node

Let us create the RedBlackNode class inheriting AbstractBinaryNode:

public class RedBlackNode<T extends Comparable<T>> extends AbstractBinaryNode<T, RedBlackNode<T>> {
    private boolean is_red;

    public RedBlackNode(T key) {
        super(key);
        setToRed();
    }

    public void setToRed() { is_red = true; }

    public void setToBlack() { is_red = false; }

    public boolean isRed() { return is_red; }

    public boolean isBlack() { return !is_red; }
}

• L2: if is_red is true, the color of this node is red; otherwise, it is black.

• L6: the color of the node is black by default upon instantiation.

Let us the RedBlackTree class inheriting AbstractBalancedBinarySearchTree:

public class RedBlackTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, RedBlackNode<T>> {
    @Override
    public RedBlackNode<T> createNode(T key) {
        return new RedBlackNode<T>(key);
    }
}

Finally, let us override balance() method that handles 3 cases:

@Override
protected void balance(RedBlackNode<T> node) {
    if (isRoot(node))
        node.setToBlack();
    else if (node.getParent().isRed()) {
        RedBlackNode<T> uncle = node.getUncle();

        if (uncle != null && uncle.isRed())
            balanceWithRedUncle(node, uncle);
        else
            balanceWithBlackUncle(node);
    }
}

• L3: sets the color to black if node is the root.

• L5: if the color of node's parent is red:

  • L8: checks if the color of node's uncle is also red.

  • L10: the color of node's uncle is black.

What about the case when the color of node's parent is black?

The following shows a method that handles when both the parent and the uncle are red:

private void balanceWithRedUncle(RedBlackNode<T> node, RedBlackNode<T> uncle) {
    node.getParent().setToBlack();
    uncle.setToBlack();
    RedBlackNode<T> grandParent = node.getGrandParent();
    grandParent.setToRed();
    balance(grandParent);
}

Are there any structural changes after this method is called?

The following shows a method that handles when the parent is red but the uncle is black:

private void balanceWithBlackUncle(RedBlackNode<T> node) {
    RedBlackNode<T> grandParent = node.getGrandParent();

    if (grandParent != null) {
        RedBlackNode<T> parent = node.getParent();

        if (grandParent.isLeftChild(parent) && parent.isRightChild(node)) {
            rotateLeft(parent);
            node = parent;
        }
        else if (grandParent.isRightChild(parent) && parent.isLeftChild(node)) {
            rotateRight(parent);
            node = parent;
        }

        node.getParent().setToBlack();
        grandParent.setToRed();

        if (node.getParent().isLeftChild(node))
            rotateRight(grandParent);
        else
            rotateLeft(grandParent);
    }
}

• L7: the case of left zig-zag.

• L11: the case of right zig-zag.

• L19: the case of left linear.

• L21: the case of right linear.

The followings demonstrate how the balance() method works in Red-Black trees:

How does a Red-Black tree know when it is unbalanced?