To insert a node into an RB-Tree, we first insert it the same way we insert a node into a binary-search tree. We start from root and compare it’s value against the value of node being added. If lesser, we compare it against the left sub-tree and right sub-tree otherwise. This is repeated until a NULL node is encountered, where this new node is inserted. After insertion, color it “Red” and perform an RB-Table fixup to maintain the properties of RB-Tree. Let’s look at the code for Red Black Trees Insertion:
void insert(RBNode* node)
{
if(root == &sentinel)
{
node->m_isRed = false;
root = node;
return;
}
RBNode* current = root;
RBNode* target = root;
while(current != &sentinel)
{
target = current;
if(node->m_size > current->m_size){ current = current->m_right; }
else if (node->m_size == current->m_size) {
if(node > current) { current = current->m_right; }
else { current = current->m_left; }
}
else { current = current->m_left; }
}
if(node->m_size > target->m_size) { target->m_right = node; }
else if(node->m_size == target->m_size) {
if(node > target) { target->m_right = node; }
else { target->m_left = node; }
}
else { target->m_left = node; }
node->m_parent = target;
node->m_isRed = true;
RBInsertFixup(node);
}
Insert-Fixup:
Once we inserted new node and colored it RED, there are 2 possible violations to the properties of RB-Tree. First, if the inserted node is Root, we colored it red, when it should’ve been black. Second, if the parent of inserted node is red, then we have violated 5th property which states that both children of RED nodes should be BLACK.
Now that we have inserted a node into the tree, let’s look at implementing the fix-up function. For this, I consider the node’s parent to be a left-child and “uncle” as node->parent->parent->right. With that, we will have 3 scenarios:
– If uncle is RED, we will color the uncle and inserted node’s parent BLACK. Then, make node’s parent as the next node to be processed in the loop.
– If the uncle is black and node being checked is a right-child. In this case, we try to transform it into 3rd scenario by making the next node to be processed as current node’s parent and performing Left-Rotate operation on inserted node.
– Finally, if uncle is black and node being checked is left child, we color node->parent as BLACK and node->parent->parent as RED.
Here’s the code snippet
void RBInsertFixup(RBNode* node)
{
while(node->m_parent != &sentinel && node->m_parent->m_isRed)
{
//If Node's parent is red, we have a violation in RB-Tree Property
if(node->m_parent->m_parent->m_right == node->m_parent)
{
//If the current node's parent is right child
//Case - 1: We know that node->parent->parent(NPP) is black. So, if NPP's left child is red,
//we can simply switch colors
RBNode* uncle = node->m_parent->m_parent->m_left;
if(uncle != &sentinel && uncle->m_isRed)
{
node->m_parent->m_parent->m_isRed = true;
uncle->m_isRed = false;
node->m_parent->m_isRed = false;
node = node->m_parent->m_parent;
}
// Now we know that NPP's left child is black or nullptr. Now, depending on whether current node is
// left or right child, we perform rotations
else
{
//The goal here is to make newly added node as a root to node's parent and parent's parent.
if(node->m_parent->m_left == node)
{
// We right rotate here to transform newly added node as parent.
// With this node's parent effectively becomes it's right-child
// and Node's parent's parent will become node's parent
node = node->m_parent;
RightRotate(node);
}
// Finally Left Rotate on node's parent.
// Newly added node will become the new parent.
node->m_parent->m_isRed = false;
node->m_parent->m_parent->m_isRed = true;
LeftRotate(node->m_parent->m_parent);
}
}
else if(node->m_parent->m_parent->m_left == node->m_parent)
{ //Same as the block above with left and right interchanged }
}
root->m_isRed = false;
}