Red Black Tree – Insertion

Introduction:
Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :)


Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions :

• Flipping the color
• Right and left rotation

Insertion:
Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. The insertion of red node can cause red violation so we are going to fix it after the insertion of each new node.
let’s look at the node and tree structure.


struct tnode {

        int data;
        char color;
        struct tnode *left;
        struct tnode *right;

};

struct tree {

        struct tnode *root;
}*Tree;


Here is a helper function that returns a new red node.
struct tnode *makenode(int data)/*make a new node*/
{
        struct tnode *p;
        p = talloc();
        p->data = data;
        p->color = RED;
        p->left = p->right = NULL;
        return p;
}


http://athiraamazhichira.wordpress.com/2011/11/07/red-black-tree-insertion/