Category: Red-Black Trees

Red-Black Trees: Delete and Delete-Fixup Analysis

February 25th, 2023

Deleting a node is the hardest part of implementing an RB-Tree. Let’s write a helper function that moves the parent of node U to node V. This function is called “Transplant”. We will also use another helper function to get the least node in a sub-tree.

void transplant(RBNode* u, RBNode* v)
{
    if(u->m_parent == &sentinel) { root = v; }
    else if(u->m_parent->m_left == u) { u->m_parent->m_left = v; }
    else { u->m_parent->m_right = v; }
    v->m_parent = u->m_parent;
}
RBNode* getMinimumInSubTree(RBNode* node)
{
    RBNode* current = node;
    while(current->m_left != &sentinel)
    {
        current = current->m_left;
    }
    return current;
}

When deleting, we keep track of the color of node that’s being deleted and also a node(X) that takes the place of the node that’s being deleted, which might introduce violations. And, 2 things must be considered when deleting a node:
– If node has a single/no child. In this case, we store the original color of this node and make left/right child or sentinel take the node’s place.
– If node has 2 valid children, we get the least node in the right sub-tree(Y) and have that replace the node being deleted. During this operation, there should be another node that takes Y’s place. That will be Y->Right, our X in this case. Here, we keep track of Y’s(successor ) original color.
Once we delete the node, we call a DeleteFixup function if the original color of deleted node is BLACK.

void remove(RBNode* node)
{
    RBNode* y = node;
    bool yOriginalColorIsRed = y->m_isRed;
    RBNode* x = &sentinel;
    
    if(node->m_left == &sentinel)
    {
        x = node->m_right;
        transplant(node, node->m_right);
    }
    else if(node->m_right == &sentinel)
    {
        x = node->m_left;
        transplant(node, node->m_left);
    }
    else
    {
        //Node has 2 valid children
        y = getMinimumInSubTree(node->m_right);
        yOriginalColorIsRed = y->m_isRed;
        // we color Y the same color as z.
        // y->right take's Y's place.
        x = y->m_right;
        //Node being deleted is not immediate parent of Y.
        if(y->m_parent == node)
        {
            //This check is for sentinel. If y has no children, we store the parent info in sentinel
            x->m_parent = y;
        }
        else
        {
            //Move X To Y's place
            transplant(y, x);
            y->m_right = node->m_right;
            y->m_right->m_parent = y;   
        }
        //Move Y To Z'a Place and take it's color
        transplant(node, y);
        y->m_left = node->m_left;
        node->m_left->m_parent = y;
        y->m_isRed = node->m_isRed;
    }
    if(!yOriginalColorIsRed){ RBDeleteFixup(x); }
}

Delete-Fixup:

Once deleted, we could have following violations:
– If the delete node is root, then the node that replaces it might be RED.
– If the node replacing could be a RED node and it’s parent could also be RED.
– The number of black nodes in any simple path might not be equal anymore.
To fix the third scenario, we introduce “Double Blackness” and “Red/Black”. If the node that replaces the deleted node is BLACK/RED, the sub-tree would be deficit by one black node. If the replacing node is BLACK, then it would be “Double Black”, and “RED-BLACK” otherwise.

Double-Black and Red-Black are kind of abstract properties. They dont need to be represented as data in code. Now that we have established that, let’s look at the Delete Fixup scenarios. Here, I assume the node under focus is left child and “Sibling” is a right child. We are looking at 4 cases here:
1. If sibling is RED, it must mean that our parent is BLACK. We can switch colors of Sibling to BLACK and parent to RED and perform Left Rotation on parent and update the Sibling’s pointer. The might not fix the violations introduced, but it transforms the problem in a way that ensures sibling is BLACK and will be handled by following cases.

2. If sibling is BLACK and both it’s children are also BLACK. This case is simple. We just color sibling RED and make the active node as our current parent. Since we have an Double-Blackness on the left subtree, making sibling RED will make it lose a black node, thereby balancing both sub-trees.

3. If sibling is BLACK and it’s left child is RED. We color sibling RED and it’s left child to BLACK and perform RightRotation on sibling to convert this to Case 4. This might not fix the violations, but leads into Case-4

4. If sibling is BLACK and it’s right child is RED, sibling takes the color of it’s parent and parent is made RED and LeftRotation is performed on Parent. Now, the left sub-tree will have an additional black node, fixing the violation.

Hope this helped! Please like the posts if you’ve learnt something. Really boosts the motivation and drive to post more content.

Here’s the Code Snippet

void RBDeleteFixup(RBNode* node)
{
    while(node != root && !node->m_isRed)
    {
        if(node->m_parent->m_right == node)
        {
            //Uncle should always be present
            RBNode* sibling = node->m_parent->m_left;
            if(sibling->m_isRed)
            {
                sibling->m_isRed = false;
                sibling->m_parent->m_isRed = true;
                RightRotate(sibling->m_parent);
                sibling = node->m_parent->m_left;
            }
            //Case - 2: Uncle is black and Left and right children of uncle are null or red
            if(sibling == &sentinel || (!sibling->m_left->m_isRed && !sibling->m_right->m_isRed))
            {
                if(sibling != &sentinel)
                {
                    sibling->m_isRed = true;
                }
                // Extra blackness is added to parent, making in RB or BB to compensate for removing 
                // a black on uncle and node
                node = node->m_parent; 
            }
            else
            {   
                //Uncle's right is red, transform to make both left and right as black 
                if(sibling->m_right->m_isRed)
                {
                    sibling->m_right->m_isRed = false;
                    sibling->m_isRed = true;
                    LeftRotate(sibling);
                    sibling = node->m_parent->m_left;
                }
                sibling->m_isRed = node->m_parent->m_isRed;
                node->m_parent->m_isRed = false;
                sibling->m_left->m_isRed = false;

                RightRotate(node->m_parent);
                node = root;
            }
        }
        else
        { //Same as previous block with Left and Right exchanged}
    }
    node->m_isRed = false;
}

Red Black Trees Insertion and Insert-Fixup Analysis

February 24th, 2023

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;
}

Red Black Trees: A brief study with code

February 24th, 2023

Let’s try and de-mystify Red Black trees.
It’s basically a binary-search tree with an additional property, color. Having this property makes it possible to “approximately” balance it. By approximately balance, I mean that going from root to leaf, there’s no path that is twice as long as any other. Let’s first define the structure of RB-tree node as shown on below.
We also use a sentinel node as leaf node to help with the tree fix-up operations. So, all leaf nodes in a RB-Tree are sentinels.

extern RBNode sentinel;
extern RBNode* root;
struct RBNode
{
     RBNode(size_t size) : m_size(size) {}
     RBNode*         m_parent = &sentinel;
     RBNode*         m_left = &sentinel;
     RBNode*         m_right = &sentinel;
     size_t          m_size = { 0 };
     bool            m_isRed = false;
};

A Red-Black tree must satisfy following properties:
– Every node is red or black.
– The root of the node should be black.
– Every leaf should be black.
– Children of a red node should be black.
– For each node, all paths from node to it’s leaves should contain same number of black nodes.

During the course of Insertion and deletion operations, various properties of out RB-Tree might be violated. We shall use Left and Right rotations to restore those traits.

When left-rotating, X should already contain a right-child(Y). Y’s right node will not change and X’s left node will not change.

void LeftRotate(RBNode* x)
{
    // Pre-condition that must be satisfied here is that
    // X already has a valid right child(Y).
    // Y takes X's place
    //Move parents
    RBNode* y = x->m_right;
    y->m_parent = x->m_parent;
    x->m_parent = y;
    if(y->m_parent == &sentinel){ root = y; }
    else if(y->m_parent->m_right == x){ y->m_parent->m_right = y; }
    else { y->m_parent->m_left = y; }
    //x becomes y's left node. y's left node becomes x's right node
    x->m_right = y->m_left;
    if(x->m_right != &sentinel) { x->m_right->m_parent = x; }
    y->m_left = x;
}

When right-rotating, X should already contain a left-child(Y). Y’s left node will not change and X’s right node will not change.

void RightRotate(RBNode* x)
{
    // Pre-Condition that must be satisfied here
    // is that X has a vaild left node(Y). 
    // Y takes X's place
    RBNode* y = x->m_left;
    y->m_parent = x->m_parent;
    x->m_parent = y;
    if(y->m_parent == &sentinel){ root = y; }
    else if(y->m_parent->m_right == x) { y->m_parent->m_right = y; }
    else  { y->m_parent->m_left = y; }

    x->m_left = y->m_right;
    if(x->m_left != &sentinel) { x->m_left->m_parent = x; }
    y->m_right = x;
}