How do I fix my Red Black Tree from rotating unnecessarily?

Question

I am implementing a Red-Black Tree in Java and encountering an issue with rotations during insertion. Specifically, when I insert the numbers 10 and then 13 into the tree, it performs a rotation even though, to my understanding, it should not, as these insertions do not violate the Red-Black Tree properties.

Here is the relevant part of my code:

Node.java

public class Node {
    public enum Color {
        RED, BLACK
    }

    private Color color;
    private int data;
    private Node left;
    private Node right;

    public Node(int data, Color color) {
        left = null;
        right = null;
        this.color = Color.RED;
        this.data = data;
    }

    /**
     * Create a new node given an int, a color, and 
     * the left and right sub-trees.
     * @param data The value stored in the node
     * @param color The initial color of the node
     * @param left The left sub-tree
     * @param right The right sub-tree
     */
    public Node(int data, Color color, Node left, Node right) {
        this.left = left;
        this.right = right;
        this.color = Color.RED;
        this.data = data;
    }

    /**
     * Get the current color of the node
     * @return Color
     */
    public Color getColor() {
        return color;
    }

    /**
     * Return the opposite of the supplied color
     * @param c Color
     * @return Color
     */
    public static Color flipColor(Color c) {
        if (c == Color.RED)
            return Color.BLACK;
        return Color.RED;
    }

    /**
     * Set the color of the node
     * @param color
     */
    public void setColor(Color color) {
        this.color = color;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    /**
     * Set the left sub-tree
     * @param left
     */
    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

RBT.java:

import java.util.*;
public class RBT {
    //private Node root;
    public Node root;

    public RBT() {}

    public boolean isRed(Node x) {
        if (x == null) return false;
        return x.getColor() == Node.Color.RED;
    }
    
    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(int x) {
        return nodeContainsData(root, x);
    }

    private boolean nodeContainsData(Node r, int x) {
        while (r != null) {
            if (r.getData() - x < 0) {
                r = r.getLeft();
            } else if (r.getData() - x > 0) {
                r = r.getRight();
            } else {
                return true;
            }
        }
        return false;
    }

    public List<Integer> serializeTree() {
        return serializeTree(root);
    }

    private List<Integer> serializeTree(Node r) {
        if (r == null) return new LinkedList<>();
        int data = r.getData();
        List<Integer> left = serializeTree(r.getLeft());
        List<Integer> right = serializeTree(r.getRight());
        left.add(data);
        left.addAll(right);
        return left;
    }

    public int maxHeight() {
        return maxHeight(root);
    }

    private int maxHeight(Node r) {
        if (r==null) return 0;        
        return 1 + Math.max(maxHeight(r.getLeft()), maxHeight(r.getRight()));
    }




    // ************************************************************************
    // * INSERT INTO RED-BLACK TREE
    // ************************************************************************

    public void insert(int x) {
        root = nodeInsertData(root, x);
        root.setColor(Node.Color.BLACK);
    }

private Node nodeInsertData(Node h, int x) {
    if (h == null) {
        return new Node(x, Node.Color.RED); // New nodes are always inserted as red
    }

    if (x < h.getData()) {
        h.setLeft(nodeInsertData(h.getLeft(), x)); // Recur on the left
    } else if (x > h.getData()) {
        h.setRight(nodeInsertData(h.getRight(), x)); // Recur on the right
    }
    // If x is equal to h.getData(), we do nothing (assuming no duplicates allowed)

    // Fix up any Red-Black Tree violations
    h = fixUp(h);

    return h;
}
private Node fixUp(Node h) {
    if (isRed(h.getRight()) && !isRed(h.getLeft())) {
        h = rotateLeft(h); // Left rotation
    }
    if (isRed(h.getLeft()) && h.getLeft() != null && isRed(h.getLeft().getLeft())) {
        h = rotateRight(h); // Right rotation
    }
    if (isRed(h.getLeft()) && isRed(h.getRight())) {
        flipColors(h); // Color flip
    }
    return h;
}


private Node rotateLeft(Node h) {
    assert (h != null) && isRed(h.getRight());

    Node x = h.getRight();
    h.setRight(x.getLeft());
    x.setLeft(h);
    x.setColor(h.getColor());
    h.setColor(Node.Color.RED);
    return x;
}

private Node rotateRight(Node h) {
    assert (h != null) && isRed(h.getLeft());

    Node x = h.getLeft();
    h.setLeft(x.getRight());
    x.setRight(h);
    x.setColor(h.getColor());
    h.setColor(Node.Color.RED);
    return x;
}

private void flipColors(Node h) {
    // Node h and its children must not be null
    assert (h != null) && (h.getLeft() != null) && (h.getRight() != null);
    // Flip the colors
    h.setColor(Node.flipColor(h.getColor()));
    h.getLeft().setColor(Node.flipColor(h.getLeft().getColor()));
    h.getRight().setColor(Node.flipColor(h.getRight().getColor()));
}
}

The issue arises after inserting these two numbers. According to Red-Black Tree rules, inserting 10 and then 13 should not require a rotation. However, my fixUp method in RBT.java seems to trigger a rotation. I suspect the problem might be in my fixUp method or the way I'm handling the node colors, but I'm not entirely sure.

Could someone help me understand why these rotations are occurring and how to fix this issue?

Answer 1

You are right that in a standard red black tree it is not necessary to perform a rotation when the tree is in this state (after insertion of 10 and 13 in that order):

    10 (black)
      \
       13 (red)

But, your implementation is the one that Robert Sedgewick presented in his 2008 paper. The idea of that approach is to introduce an additional restriction on the red-black tree compared to the standard red-black tree, whereby a node is not allowed to have a red child at the right unless it has two red children. This requirement makes the tree left-leaning.

For your example that means the tree will violate that additional constraint once 13 is added as a red leaf at the right side of the existing node 10, which can be resolved with a rotation, giving this tree:

       13 (red)
      / 
    10 (black)

Also compare your fixUp function with the post-processing code that Sedgewick has in his Java implementation:

Your fixUp code:

    if (isRed(h.getRight()) && !isRed(h.getLeft())) {
        h = rotateLeft(h); // Left rotation
    }
    if (isRed(h.getLeft()) && h.getLeft() != null && isRed(h.getLeft().getLeft())) {
        h = rotateRight(h); // Right rotation
    }
    if (isRed(h.getLeft()) && isRed(h.getRight())) {
        flipColors(h); // Color flip
    }

Their fixup code:

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);

These two code variants essentially perform the same operations. Note the important code-comment above their fixup code, and how this algorithm treats left and right subtrees asymmetrically, which is not what you see in the algorithm for red black trees that have no such left-leaning requirement. If you intended to work with such (unconstrained) red-black trees then you took the wrong code. See Wikipedia - red-black trees for the traditional algorithm, which needs to deal with more cases, but on average results in fewer rotations.

Answer 2

This appears to be a left-leaning right-black tree, rather than just red-black. If that is indeed the case then the rotation is not unnecessary.