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

Question

I'm learning about how to implement Red Black Tree in Java, i have consulted the source code from Sanfoundry: https://www.sanfoundry.com/java-program-implement-red-black-tree/ But i can't understand the function to insert node The code is here:

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;

    }

Can anyone explain to me why we need to fix the color when a black node have both 2 red children and the meaning of handleReorient function, tks all !

Answer 1

Normally speaking

1. You find the leaf position for the node you wish to insert
2. You insert the node and colour it Red
3. If this node has a parent and it is Red, then that is violation of the Red-Black rules and you traverse the tree back in the direction of the root node, fixing these violations until the tree is corrected.

But I have seen insertion code, particularly with Sedgewick's Left-Leaning Red-Black trees where by the Red-Black tree is "prepared" for insertion on the way down. See here Left-Leaning Red-Black Trees and look at page 20 and 21. You will find that for 2-3-4 trees, nodes with 4 elements are split on the way down. A 4-node is equivalent in Red-Black trees to a black node with 2 red children.

handleReorient() is equivalent to the code that does the splitting (which amounts to recolouration).