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

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;

    }

任何人都可以向我解释为什么当黑色节点同时具有 2 个红色时我们需要修复颜色 children 以及 handleReorient 函数的含义，tks all !

Answer 1

一般来说

您找到要插入的节点的叶位置
您插入节点并将其着色为红色
如果这个节点有一个父节点并且它是红色的，那么这就违反了红黑规则，并且你沿着根节点的方向遍历树，修复这些违规，直到树被纠正。

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

handleReorient() 等同于执行拆分（相当于重新着色）的代码。

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

Why we need fix color when a black node of Red Black Tree has two children both red?

java

data-structures

red-black-tree-insertion