红黑树节点插入的非常规Java实现及递归方法咨询

嘿，咱们一步步拆解怎么实现适配你教授给的Node类的红黑树递归插入吧。首先，因为你没贴全Node类的代码，我先基于常规红黑树节点+你指定的颜色规则（0=黑色，1=红色）做个合理假设：

class Node {
    Integer val;
    int color; // 0代表黑色，1代表红色
    Node left, right, parent;

    Node(Integer val, int color) {
        this.val = val;
        this.color = color;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

接下来是完整的递归插入实现，包含核心插入逻辑、红黑树性质修复和辅助旋转方法：

1. 对外暴露的插入入口与递归插入核心 #

首先是对外的put方法，以及递归查找插入位置的核心逻辑——注意新节点默认建议设为红色（因为插入黑色会直接破坏黑高平衡，修复成本更高），不过你也可以通过传入的col参数指定颜色：

private static Node root; // 红黑树的根节点

// 对外暴露的插入方法，调用递归逻辑
private static void put(int val, int col) {
    root = put(root, val, col);
    root.color = 0; // 强制根节点为黑色，保证红黑树性质2
}

// 递归插入的核心方法
private static Node put(Node n, Integer val, int col) {
    // 递归终止：找到空位置，创建新节点
    if (n == null) {
        return new Node(val, col);
    }

    // 按二叉搜索树规则递归查找插入位置（val作为排序依据）
    if (val.compareTo(n.val) < 0) {
        Node leftChild = put(n.left, val, col);
        n.left = leftChild;
        leftChild.parent = n; // 必须维护父节点引用，否则后续修复和旋转会出错
    } else if (val.compareTo(n.val) > 0) {
        Node rightChild = put(n.right, val, col);
        n.right = rightChild;
        rightChild.parent = n;
    } else {
        // 处理重复值：根据需求选择覆盖val/颜色，或者直接返回原节点
        return n;
    }

    // 插入完成后，修复红黑树的性质
    return fixAfterInsertion(n);
}

2. 插入后的红黑树性质修复 #

插入新节点后，可能违反红黑树的性质4（红色节点的子节点必须是黑色），我们需要分情况修复：

private static Node fixAfterInsertion(Node node) {
    Node current = node;

    // 循环修复，直到当前节点是根，或者父节点不是红色
    while (current.parent != null && current.parent.color == 1) {
        Node parent = current.parent;
        Node grandparent = parent.parent; // 祖父节点一定存在，因为父节点是红色（根是黑色）

        // 情况1：父节点是祖父节点的左孩子
        if (grandparent.left == parent) {
            Node uncle = grandparent.right;

            // 子情况1a：叔叔节点是红色——只需重染色，继续向上检查
            if (uncle != null && uncle.color == 1) {
                parent.color = 0;
                uncle.color = 0;
                grandparent.color = 1;
                current = grandparent;
            } else {
                // 子情况1b：叔叔是黑色，且当前节点是父节点的右孩子——先左旋父节点，转为情况1c
                if (parent.right == current) {
                    current = parent;
                    rotateLeft(current);
                }
                // 子情况1c：叔叔是黑色，当前节点是父节点的左孩子——右旋祖父节点+重染色
                parent.color = 0;
                grandparent.color = 1;
                rotateRight(grandparent);
            }
        } else {
            // 情况2：父节点是祖父节点的右孩子，和情况1完全对称
            Node uncle = grandparent.left;

            // 子情况2a：叔叔节点是红色——重染色
            if (uncle != null && uncle.color == 1) {
                parent.color = 0;
                uncle.color = 0;
                grandparent.color = 1;
                current = grandparent;
            } else {
                // 子情况2b：叔叔是黑色，当前节点是父节点的左孩子——先右旋父节点
                if (parent.left == current) {
                    current = parent;
                    rotateRight(current);
                }
                // 子情况2c：叔叔是黑色，当前节点是父节点的右孩子——左旋祖父节点+重染色
                parent.color = 0;
                grandparent.color = 1;
                rotateLeft(grandparent);
            }
        }
    }

    // 最后再次确保根节点是黑色
    root.color = 0;
    return root;
}

3. 辅助旋转方法 #

红黑树修复需要左旋和右旋操作，这两个方法是核心辅助工具：

左旋实现 #

private static void rotateLeft(Node node) {
    Node rightChild = node.right;
    node.right = rightChild.left;

    // 维护右孩子的左子节点的父引用
    if (rightChild.left != null) {
        rightChild.left.parent = node;
    }

    // 维护右孩子的父引用
    rightChild.parent = node.parent;

    if (node.parent == null) {
        root = rightChild; // 如果node是根，旋转后右孩子成为新根
    } else if (node == node.parent.left) {
        node.parent.left = rightChild;
    } else {
        node.parent.right = rightChild;
    }

    // 完成旋转的最后一步关联
    rightChild.left = node;
    node.parent = rightChild;
}

右旋实现 #

private static void rotateRight(Node node) {
    Node leftChild = node.left;
    node.left = leftChild.right;

    // 维护左孩子的右子节点的父引用
    if (leftChild.right != null) {
        leftChild.right.parent = node;
    }

    // 维护左孩子的父引用
    leftChild.parent = node.parent;

    if (node.parent == null) {
        root = leftChild; // 如果node是根，旋转后左孩子成为新根
    } else if (node == node.parent.right) {
        node.parent.right = leftChild;
    } else {
        node.parent.left = leftChild;
    }

    // 完成旋转的最后一步关联
    leftChild.right = node;
    node.parent = leftChild;
}

关键注意点 #

• 颜色规则严格对应：所有颜色判断和赋值都要遵循0=黑、1=红，别搞混。
• 父节点引用必须维护：递归插入时一定要给新节点设置父节点，否则旋转和修复逻辑会完全失效。
• 根节点强制黑色：无论插入过程中根节点颜色怎么变，最后都要设为黑色，保证红黑树的基本性质。
• 重复值处理：如果你的场景允许重复val，可以调整插入逻辑（比如插入到右子树），否则直接返回原节点即可。
• 哨兵节点适配：如果你的Node类用哨兵节点（代替null），需要修改修复逻辑中的null判断，但当前代码是基于null叶子节点实现的。

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