Inserting into Augmented Red Black Tree

Question

I am looking at the code of inserting into an augmented Red black tree. This tree has an additional field called "size" and it keeps the size of a subtree rooted at a node x. Here is the pseudocode for inserting a new node:

AugmentedRBT_Insert(T,x){
    BST_Insert(T,x); //insert as if it is a normal BST
    x[color]=red; //insert as a red node
    size[x]=1;
    tmp=parent[x];
    while(tmp!=NULL){   //start from the node x and follow the path to root
        size[tmp]=size[tmp]+1;  //update the size of each node
        tmp=parent[tmp];
    }
}

Forget about fixing the coloring and rotations, they will be done in another function. My question is, why do we set the size of the newly added node "x" to 1? I understand that it will not have any subtrees, so its size must be 1, but one of the requirements of RBT is that every red node has two black children, in fact every leaf node is NULL and even if we insert the node "x" as black, it still should have 2 black NULL nodes and i think we must set its size to 3? Am i wrong?

Thanks.

Andrew Mao Andrew Mao · Accepted Answer · 2013-03-23T23:09:18

An insertion in a red-black tree, as in most binary trees, happens directly at a leaf. Hence the size of the subtree rooted at the leaf is 1. The red node does have two black children, because leaves always have the "root" or "nil" as a child, which is black. Those null elements aren't nodes, so we wouldn't count them.

Then, we go and adjust the sizes of all parents up to the root (they each get +1 for the node we just added).

Finally, we fix these values when we rotate the tree to balance it, if necessary. In your implementation, you will probably want to do both the size updates and rotations in one pass instead of two.

Inserting into Augmented Red Black Tree

1 Answers