Java实现Red-Black Tree插入时不必要旋转问题的排查求助

问题原因分析 #

1. Node类构造函数颜色设置错误 #

你的Node类两个构造函数都硬编码将节点颜色设为Color.RED，完全忽略了传入的color参数。比如：

public Node(int data, Color color) {
    left = null;
    right = null;
    this.color = Color.RED; // 错误：忽略传入的color参数
    this.data = data;
}

这会导致初始化节点时无法正确设置颜色，虽插入新节点时确实应为红色，但该错误可能在后续颜色修复流程中引发异常。

2. FixUp逻辑遵循左倾红黑树规则，而非标准红黑树 #

当前fixUp方法实现的是**左倾红黑树（LLRB）**的修复逻辑，这类红黑树强制要求红色节点只能是左孩子。插入13后，根节点10的右孩子为红色，违反左倾规则，因此触发左旋。但标准红黑树允许红色节点作为右孩子（只要满足无连续红色节点、根节点为黑、所有路径黑节点数一致等核心规则），所以你认为这是“不必要的旋转”。

插入10和13后的标准红黑树合法状态应为：

• 根节点10（黑色）
• 右孩子13（红色）
  该状态完全符合标准红黑树特性，无需任何旋转或颜色翻转。

修复方案 #

步骤1：修复Node构造函数的颜色设置 #

修改两个构造函数，正确使用传入的color参数：

public Node(int data, Color color) {
    left = null;
    right = null;
    this.color = color; // 改为使用传入的参数
    this.data = data;
}

public Node(int data, Color color, Node left, Node right) {
    this.left = left;
    this.right = right;
    this.color = color; // 改为使用传入的参数
    this.data = data;
}

步骤2：替换FixUp逻辑为标准红黑树插入修复逻辑 #

标准红黑树插入后仅在出现连续红色节点（父节点与子节点均为红）时需要修复，修复逻辑需根据叔叔节点的颜色分情况处理。以下是迭代式的插入与修复实现（更易跟踪节点关系）：

替换原insert方法与新增修复方法

public void insert(int x) {
    Node newNode = new Node(x, Node.Color.RED);
    if (root == null) {
        root = newNode;
        root.setColor(Node.Color.BLACK);
        return;
    }

    Node current = root;
    Node parent = null;
    // 查找插入位置
    while (current != null) {
        parent = current;
        if (x < current.getData()) {
            current = current.getLeft();
        } else if (x > current.getData()) {
            current = current.getRight();
        } else {
            // 重复节点，不插入
            return;
        }
    }

    // 设置新节点的父节点
    if (x < parent.getData()) {
        parent.setLeft(newNode);
    } else {
        parent.setRight(newNode);
    }

    // 修复红黑树违规
    fixUpAfterInsert(newNode);
}

private void fixUpAfterInsert(Node node) {
    Node parent = getParent(node);
    while (parent != null && isRed(parent)) {
        Node grandparent = getParent(parent);
        if (grandparent == null) break;
        
        // 父节点是祖父的左孩子
        if (parent == grandparent.getLeft()) {
            Node uncle = grandparent.getRight();
            // 情况1：叔叔是红色，翻转颜色后向上检查
            if (isRed(uncle)) {
                parent.setColor(Node.Color.BLACK);
                uncle.setColor(Node.Color.BLACK);
                grandparent.setColor(Node.Color.RED);
                node = grandparent;
                parent = getParent(node);
            } else {
                // 情况2：当前节点是父节点的右孩子，先左旋父节点
                if (node == parent.getRight()) {
                    rotateLeft(parent);
                    node = parent;
                    parent = getParent(node);
                }
                // 情况3：当前节点是父节点的左孩子，右旋祖父并交换颜色
                parent.setColor(Node.Color.BLACK);
                grandparent.setColor(Node.Color.RED);
                rotateRight(grandparent);
                break;
            }
        } else {
            // 父节点是祖父的右孩子，对称处理
            Node uncle = grandparent.getLeft();
            if (isRed(uncle)) {
                parent.setColor(Node.Color.BLACK);
                uncle.setColor(Node.Color.BLACK);
                grandparent.setColor(Node.Color.RED);
                node = grandparent;
                parent = getParent(node);
            } else {
                if (node == parent.getLeft()) {
                    rotateRight(parent);
                    node = parent;
                    parent = getParent(node);
                }
                parent.setColor(Node.Color.BLACK);
                grandparent.setColor(Node.Color.RED);
                rotateLeft(grandparent);
                break;
            }
        }
    }
    // 确保根节点始终为黑色
    root.setColor(Node.Color.BLACK);
}

// 添加获取父节点的辅助方法
private Node getParent(Node node) {
    if (node == null || node == root) return null;
    Node current = root;
    Node parent = null;
    while (current != null && current != node) {
        parent = current;
        current = node.getData() < current.getData() ? current.getLeft() : current.getRight();
    }
    return parent;
}

调整旋转方法以更新父节点指针

旋转时需同步更新父节点的子节点引用，否则会出现树结构断裂：

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

    Node x = h.getRight();
    Node parent = getParent(h);

    h.setRight(x.getLeft());
    x.setLeft(h);
    x.setColor(h.getColor());
    h.setColor(Node.Color.RED);

    // 更新父节点的指针
    if (parent != null) {
        if (parent.getLeft() == h) {
            parent.setLeft(x);
        } else {
            parent.setRight(x);
        }
    } else {
        root = x;
    }
    return x;
}

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

    Node x = h.getLeft();
    Node parent = getParent(h);

    h.setLeft(x.getRight());
    x.setRight(h);
    x.setColor(h.getColor());
    h.setColor(Node.Color.RED);

    // 更新父节点的指针
    if (parent != null) {
        if (parent.getLeft() == h) {
            parent.setLeft(x);
        } else {
            parent.setRight(x);
        }
    } else {
        root = x;
    }
    return x;
}

修复效果 #

修改后插入10和13时：

• 插入10：根节点设为黑色，无额外操作。
• 插入13：作为10的右红色子节点，父节点为黑色，无违规情况，无需旋转或颜色翻转，完全符合标准红黑树规则。

内容的提问来源于stack exchange，提问作者ShadowPoke3