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

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.