当红黑树的一个黑色节点有两个都是红色的子节点时，为什么我们需要固定颜色？

Question

我正在学习如何在Java中实现红黑树，我查阅了Sanfoundry的源代码：https://www.sanfoundry.com/java-program-implement-red-black-tree/ 但是我不能理解插入节点的函数 代码如下：

public void insert(int item) {

        current = parent = grand = header;

        nullNode.element = item;

        while (current.element != item) {

            great = grand;

            grand = parent;

            parent = current;

            current = item < current.element ? current.left : current.right;

            // Check if two red children and fix if so            
            if (current.left.color == RED && current.right.color == RED) {
                handleReorient(item);
            }

        }

        // Insertion fails if already present
        if (current != nullNode) {
            return;
        }

        current = new RedBlackNode(item, nullNode, nullNode);

        // Attach to parent
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }

        handleReorient(item);

    }

    private void handleReorient(int item) {

        // Do the color flip
        current.color = RED;

        current.left.color = BLACK;

        current.right.color = BLACK;

        if (parent.color == RED) {

            // Have to rotate
            grand.color = RED;

            if (item < grand.element != item < parent.element) {
                parent = rotate(item, grand);  // Start dbl rotate
            }
            current = rotate(item, great);

            current.color = BLACK;

        }

        // Make root black
        header.right.color = BLACK;

    }

    private RedBlackNode rotate(int item, RedBlackNode parent) {

        if (item < parent.element) {
            return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) : rotateWithRightChild(parent.left);
        } else {
            return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) : rotateWithRightChild(parent.right);
        }

    }

    /* Rotate binary tree node with left child */
    private RedBlackNode rotateWithLeftChild(RedBlackNode k2) {

        RedBlackNode k1 = k2.left;

        k2.left = k1.right;

        k1.right = k2;

        return k1;

    }

    /* Rotate binary tree node with right child */
    private RedBlackNode rotateWithRightChild(RedBlackNode k1) {

        RedBlackNode k2 = k1.right;

        k1.right = k2.left;

        k2.left = k1;

        return k2;

    }

有谁能解释一下，当一个黑色节点既有两个红色子节点，又有HandleroOrient函数tks all的含义时，为什么我们需要修复颜色

Answer 1

通常来说

1. 找到要插入的节点的叶位置
2. 插入节点并将其涂成红色
3. 如果这个节点有一个父节点，并且它是红色的，那么这违反了红黑规则，您可以沿着根节点的方向遍历树，修复这些违规行为，直到树得到纠正

但我看到了插入代码，尤其是Sedgewick的左倾红黑树，红黑树旁的红黑树为向下插入做好了“准备”。 看这里 Left-Leaning Red-Black Trees 请看第20页和第21页。您会发现，对于2-3-4树，具有4个元素的节点在向下的过程中被拆分。在红黑树中，一个4节点相当于一个有两个红色子节点的黑色节点

handleReorient（）相当于执行拆分（相当于重新资源化）的代码