如何修复红黑树，避免不必要的旋转？

Question

我正在用 Java 实现红黑树，并在插入过程中遇到旋转问题。具体来说，当我将数字 10 和 13 插入树中时，它会执行旋转，但据我了解，它不应该执行旋转，因为这些插入不会违反红黑树属性。

这是我的代码的相关部分：

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;
    }
}

彩铃.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()));
}
}

插入这两个数字后出现问题。根据红黑树规则，先插入 10 再插入 13 不需要旋转。但是，我在 RBT.java 中的 fixUp 方法似乎触发了轮换。我怀疑问题可能出在我的 fixUp 方法或我处理节点颜色的方式中，但我不完全确定。

有人可以帮助我理解为什么会发生这些轮换以及如何解决这个问题吗？

Answer 1

这似乎是一棵左倾右黑树，而不仅仅是红黑树。如果确实如此，那么轮换就没有必要了。