Tag: Adroit Things

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