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 !
Normally speaking
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).