This blog is under construction

Friday, 3 May 2013

Insertion, Deletion And Traversal In Red Black Tree

  • Red Black tree is a self-balanced binary search tree.
  • Each node in Red Black tree is colored either red or black.
  • The advantage of Red-Black tree over AVL tree is that the insertion and deletion operation can be performed more effectively (in Red Black tree).

Re-balancing rules in Red Black tree:
  • Red Node should have only black children.
  • The black depth of any external node should be the same and black depth indicates the number of black ancestor that external node has.

Example:
               B
             /   \
            R    B
          /   \
         B    B

In the above Red Black tree, no red node has red children and the black depth of any external node is same.

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs


Example program To Perform Insertion, Deletion & traversal In Red Black Tree:



  #include <stdio.h>
  #include <stdlib.h>
  enum nodeColor {
        RED,
        BLACK
  };

  struct rbNode {
        int data, color;
        struct rbNode *link[2];
  };

  struct rbNode *root = NULL;

  struct rbNode * createNode(int data) {
        struct rbNode *newnode;
        newnode = (struct rbNode *)malloc(sizeof(struct rbNode));
        newnode->data = data;
        newnode->color = RED;
        newnode->link[0] = newnode->link[1] = NULL;
        return newnode;
  }

  void insertion (int data) {
        struct rbNode *stack[98], *ptr, *newnode, *xPtr, *yPtr;
        int dir[98], ht = 0, index;
        ptr = root;
        if (!root) {
                root = createNode(data);
                return;
        }
        stack[ht] = root;
        dir[ht++] = 0;
        /* find the place to insert the new node */
        while (ptr != NULL) {
                if (ptr->data == data) {
                        printf("Duplicates Not Allowed!!\n");
                        return;
                }
                index = (data - ptr->data) > 0 ? 1 : 0;
                stack[ht] = ptr;
                ptr = ptr->link[index];
                dir[ht++] = index;
        }
        /* insert the new node */
        stack[ht - 1]->link[index] = newnode = createNode(data);
        while ((ht >= 3) && (stack[ht - 1]->color == RED)) {
                if (dir[ht - 2] == 0) {
                        yPtr = stack[ht - 2]->link[1];
                        if (yPtr != NULL && yPtr->color == RED) {
                                /*
                                 * Red node having red child. B- black, R-red
                                 *     B                R
                                 *    / \             /   \
                                 *   R   R  =>     B     B
                                 *  /               /   
                                 * R               R
                                 */
                                stack[ht - 2]->color = RED;
                                stack[ht - 1]->color = yPtr->color = BLACK;
                                ht = ht -2;
                        } else {
                                if (dir[ht - 1] == 0) {
                                        yPtr = stack[ht - 1];
                                } else {
                                        /*
                                         * XR - node X with red color
                                         * YR - node Y with red color
                                         * Red node having red child
                                         *(do single rotation left b/w X and Y)
                                         *         B             B
                                         *        /             /
                                         *      XR     =>      YR
                                         *        \           /
                                         *         YR        XR
                                         * one more additional processing will be
                                         * performed after this else part.  Since
                                         * we have red node (YR) with red child(XR)
                                         */
                                        xPtr = stack[ht - 1];
                                        yPtr = xPtr->link[1];
                                        xPtr->link[1] = yPtr->link[0];
                                        yPtr->link[0] = xPtr;
                                        stack[ht - 2]->link[0] = yPtr;
                                }
                                /*
                                 *  Red node(YR) with red child (XR) - single
                                 *  rotation b/w YR and XR for height balance. Still,
                                 *  red node (YR) is having red child.  So, change the
                                 *  color of Y to black and Black child B to Red R
                                 *          B           YR          YB
                                 *         /           /  \        /  \
                                 *        YR  =>   XR   B  =>  XR  R
                                 *       /
                                 *      XR
                                 */
                                xPtr = stack[ht - 2];
                                xPtr->color = RED;
                                yPtr->color = BLACK;
                                xPtr->link[0] = yPtr->link[1];
                                yPtr->link[1] = xPtr;
                                if (xPtr == root) {
                                        root = yPtr;
                                } else {
                                        stack[ht - 3]->link[dir[ht - 3]] = yPtr;
                                }
                                break;
                        }
                } else {
                        yPtr = stack[ht - 2]->link[0];
                        if ((yPtr != NULL) && (yPtr->color == RED)) {
                                /*
                                 * Red node with red child
                                 *        B             R
                                 *      /   \         /   \
                                 *     R     R =>  B     B
                                 *             \              \
                                 *              R              R
                                 *
                                 */
                                stack[ht - 2]->color = RED;
                                stack[ht - 1]->color = yPtr->color = BLACK;
                                ht = ht - 2;
                        } else {
                                if (dir[ht - 1] == 1) {
                                        yPtr = stack[ht - 1];
                                } else {
                                        /*
                                         * Red node(XR) with red child(YR) 
                                         *   B          B
                                         *    \          \
                                         *     XR  => YR
                                         *    /            \
                                         *   YR             XR
                                         * Single rotation b/w XR(node x with red color) & YR
                                         */
                                        xPtr = stack[ht - 1];
                                        yPtr = xPtr->link[0];
                                        xPtr->link[0] = yPtr->link[1];
                                        yPtr->link[1] = xPtr;
                                        stack[ht - 2]->link[1] = yPtr;
                                }
                                /*
                                 *   B              YR          YB
                                 *    \             /  \        /  \
                                 *     YR  =>   B   XR => R    XR
                                 *      \
                                 *       XR
                                 * Single rotation b/w YR and XR and change the color to
                                 * satisfy rebalance property.
                                 */
                                xPtr = stack[ht - 2];
                                yPtr->color = BLACK;
                                xPtr->color = RED;
                                xPtr->link[1] = yPtr->link[0];
                                yPtr->link[0] = xPtr;
                                if (xPtr == root) {
                                        root = yPtr;
                                } else {
                                        stack[ht - 3]->link[dir[ht - 3]] = yPtr;
                                }
                                break;
                        }
                }
        }
        root->color = BLACK;
  }

  void deletion(int data) {
        struct rbNode *stack[98], *ptr, *xPtr, *yPtr;
        struct rbNode *pPtr, *qPtr, *rPtr;
        int dir[98], ht = 0, diff, i;
        enum nodeColor color;

        if (!root) {
                printf("Tree not available\n");
                return;
        }

        ptr = root;
        /* search the node to delete */
        while (ptr != NULL) {
                if ((data - ptr->data) == 0)
                        break;
                diff = (data - ptr->data) > 0 ? 1 : 0;
                stack[ht] = ptr;
                dir[ht++] = diff;
                ptr = ptr->link[diff];
        }

        if (ptr->link[1] == NULL) {
                /* node with no children */
                if ((ptr == root) && (ptr->link[0] == NULL)) {
                        free(ptr);
                        root = NULL;
                } else if (ptr == root) {
                        /* deleting root - root with one child */
                        root = ptr->link[0];
                        free(ptr);
                } else {
                        /* node with one child */
                        stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0];
                }
        } else {
                xPtr = ptr->link[1];
                if (xPtr->link[0] == NULL) {
                        /*
                         * node with 2 children - deleting node 
                         * whose right child has no left child
                         */
                        xPtr->link[0] = ptr->link[0];
                        color = xPtr->color;
                        xPtr->color = ptr->color;
                        ptr->color = color;

                        if (ptr == root) {
                                root = xPtr;
                        } else {
                                stack[ht - 1]->link[dir[ht - 1]] = xPtr;
                        }

                        dir[ht] = 1;
                        stack[ht++] = xPtr;
                } else {
                        /* deleting node with 2 children */
                        i = ht++;
                        while (1) {
                                dir[ht] = 0;
                                stack[ht++] = xPtr;
                                yPtr = xPtr->link[0];
                                if (!yPtr->link[0])
                                        break;
                                xPtr = yPtr;
                        }

                        dir[i] = 1;
                        stack[i] = yPtr;
                        if (i > 0)
                                stack[i - 1]->link[dir[i - 1]] = yPtr;

                        yPtr->link[0] = ptr->link[0];
                        xPtr->link[0] = yPtr->link[1];
                        yPtr->link[1] = ptr->link[1];

                        if (ptr == root) {
                                root = yPtr;
                        }

                        color = yPtr->color;
                        yPtr->color = ptr->color;
                        ptr->color = color;
                }
        }
        if (ht < 1)
                return;
        if (ptr->color == BLACK) {
                while (1) {
                        pPtr = stack[ht - 1]->link[dir[ht - 1]];
                        if (pPtr && pPtr->color == RED) {
                                pPtr->color = BLACK;
                                break;
                        }

                        if (ht < 2)
                                break;

                        if (dir[ht - 2] == 0) {
                                rPtr = stack[ht - 1]->link[1];

                                if (!rPtr)
                                        break;

                                if (rPtr->color == RED) {
                                        /*
                                         * incase if rPtr is red, we need
                                         * change it to black..
                                         *    aB                 rPtr (red)  rPtr(black)
                                         *   /  \      =>      /    \  =>    /   \
                                         *  ST  rPtr(red)  aB    cB      aR   cB
                                         *       /  \       /  \           /  \
                                         *     bB  cB   ST  bB       ST  bB
                                         *  ST - subtree
                                         *  xB - node x with Black color
                                         *  xR - node x with Red color
                                         * the above operation will simply rebalace
                                         * operation in RB tree
                                         */
                                        stack[ht - 1]->color = RED;
                                        rPtr->color = BLACK;
                                        stack[ht - 1]->link[1] = rPtr->link[0];
                                        rPtr->link[0] = stack[ht - 1];

                                        if (stack[ht - 1] == root) {
                                                root = rPtr;
                                        } else {
                                                stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                                        }
                                        dir[ht] = 0;
                                        stack[ht] = stack[ht - 1];
                                        stack[ht - 1] = rPtr;
                                        ht++;

                                        rPtr = stack[ht - 1]->link[1];
                                }


                                if ( (!rPtr->link[0] || rPtr->link[0]->color == BLACK) &&
                                        (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) {
                                        /*
                                         *      rPtr(black)         rPtr(Red)
                                         *     /    \          =>  /    \
                                         *    B      B            R      R
                                         *
                                         */
                                        rPtr->color = RED;
                                } else {
                                        if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) {
                                                /*
                                                 * Below is a subtree. rPtr with red left child
                                                 * single rotation right b/w yR and rPtr  &
                                                 * change the color as needed
                                                 *        wR                        wR
                                                 *       /  \                      /  \
                                                 *      xB   rPtr(Black) =>   xB  yB
                                                 *     / \   /  \               /  \  /  \
                                                 *    a   b yR   e           a   b c   rPtr(Red)
                                                 *          /  \                          /  \
                                                 *         c    d                        d    e
                                                 */
                                                qPtr = rPtr->link[0];
                                                rPtr->color = RED;
                                                qPtr->color = BLACK;
                                                rPtr->link[0] = qPtr->link[1];
                                                qPtr->link[1] = rPtr;
                                                rPtr = stack[ht - 1]->link[1] = qPtr;
                                        }
                                        /*
                                         * Below is a subtree. rPtr with Right red child
                                         * single rotation b/w rPtr & wR and change colors
                                         *       wR (stack[ht-1])      rPtr(Red)
                                         *     /   \                        /    \
                                         *    xB    rPtr(black)     wB     yB
                                         *   / \   /  \        =>    /   \   /  \
                                         *  a   b c    yR         xB    c d    e
                                         *              /  \       /  \
                                         *             d    e    a    b
                                         */
                                        rPtr->color = stack[ht - 1]->color;
                                        stack[ht - 1]->color = BLACK;
                                        rPtr->link[1]->color = BLACK;
                                        stack[ht - 1]->link[1] = rPtr->link[0];
                                        rPtr->link[0] = stack[ht - 1];
                                        if (stack[ht - 1] == root) {
                                                root = rPtr;
                                        } else {
                                                stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                                        }
                                        break;
                                }
                        } else {
                                rPtr = stack[ht - 1]->link[0];
                                if (!rPtr)
                                        break;

                                if (rPtr->color == RED) {
                                        stack[ht - 1]->color = RED;
                                        rPtr->color = BLACK;
                                        stack[ht - 1]->link[0] = rPtr->link[1];
                                        rPtr->link[1] = stack[ht - 1];

                                        if (stack[ht - 1] == root) {
                                                root = rPtr;
                                        } else {
                                                stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                                        }
                                        dir[ht] = 1;
                                        stack[ht] = stack[ht - 1];
                                        stack[ht - 1] = rPtr;
                                        ht++;

                                        rPtr = stack[ht - 1]->link[0];
                                }
                                if ( (!rPtr->link[0] || rPtr->link[0]->color == BLACK) &&
                                        (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) {
                                        rPtr->color = RED;
                                } else {
                                        if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) {
                                                qPtr = rPtr->link[1];
                                                rPtr->color = RED;
                                                qPtr->color = BLACK;
                                                rPtr->link[1] = qPtr->link[0];
                                                qPtr->link[0] = rPtr;
                                                rPtr = stack[ht - 1]->link[0] = qPtr;
                                        }
                                        rPtr->color = stack[ht - 1]->color;
                                        stack[ht - 1]->color = BLACK;
                                        rPtr->link[0]->color = BLACK;
                                        stack[ht - 1]->link[0] = rPtr->link[1];
                                        rPtr->link[1] = stack[ht - 1];
                                        if (stack[ht - 1] == root) {
                                                root = rPtr;
                                        } else {
                                                stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                                        }
                                        break;
                                }
                        }
                        ht--;
                }
        }
  }

  void searchElement(int data) {
        struct rbNode *temp = root;
        int diff;

        while (temp != NULL) {
                diff = data - temp->data;
                if (diff > 0) {
                        temp = temp->link[1];
                } else if (diff < 0) {
                        temp = temp->link[0];
                } else {
                        printf("Search Element Found!!\n");
                        return;
                }
        }
        printf("Given Data Not Found in RB Tree!!\n");
        return;
  }

  void inorderTraversal(struct rbNode *node) {
        if (node) {
                inorderTraversal(node->link[0]);
                printf("%d  ", node->data);
                inorderTraversal(node->link[1]);
        }
        return;
  }

  int main() {
        int ch, data;
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traverse\n");
                printf("5. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the data to insert:");
                                scanf("%d", &data);
                                insertion(data);
                                break;
                        case 2:
                                printf("Enter the data to delete:");
                                scanf("%d", &data);
                                deletion(data);
                                break;
                        case 3:
                                printf("Enter the search element:");
                                scanf("%d", &data);
                                searchElement(data);
                                break;
                        case 4:
                                inorderTraversal(root);
                                printf("\n");
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("You have entered wrong option!!\n");
                                break;
                }
                printf("\n");
        }
        return 0;
  }



  Output(C Program To Perform Insertion, Deletion In Red Black Tree):
  jp@jp-VirtualBox:$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:50

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:40

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:70

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:30

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:45

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:60

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:1
  Enter the data to insert:80
  
  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:4
  30  40  45  50  60  70  80  

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:2
  Enter the data to delete:50

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:4
  30  40  45  60  70  80  

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:3
  Enter the search element:60
  Search Element Found!!

  1. Insertion 2. Deletion
  3. Searching 4. Traverse
  5. Exit
  Enter your choice:5



4 comments: