Friday, 3 May 2013

Insertion, Deletion and Traversal in AVL Tree

AVL tree is a self balancing binary search tree and it was named after its founders, Adelson, Velski and Landiis.

For every internal node of AVL tree, the height of the children of v can differ by at most 1.

Example:
                                    a
                                  /    \
                                b       c 
                              /   \    /  \
                            e      f  g   h

Above tree is an example for AVL tree.  The height of internal nodes c,d and a are 1, 1 and 2 correspondingly.  And the difference in height of children of any internal is not exceeding 1.

Insertion:
The height of few nodes might get changed on inserting a new node into an AVL tree.
If AVL tree becomes unbalanced during the insertion operation, then we need to travel up the tree from the newly created node until we find the first node X such that its grandparent Z is unbalanced node and we need to re-balance or reorganize it using either single rotation or double rotation.

Rotation allows user to reorganize Binary Search Tree locally.  And it is of two types.
1. Single rotation
2. Double rotation

Single rotations:
ST   - sub-tree
ST1 - subtree 1
                                 y                                              x
                               /    \                                         /   \
                             x      ST3         =>                      ST1     y
                           /   \                                                  /   \
                      ST1     ST2                                       ST2    ST3


                                  y                                              x
                                /   \              =>                        /   \
                           ST3     x                                       y     ST2
                                    /   \                                   /   \
                               ST1    ST2                         ST3    ST1


Example 1(insertion in left sub-tree):
BF(balance factor) = (height of left sub-tree) - (height of right sub-tree)

                        (ht: 1) 10 (BF = 1)
                                 /
                               5

Insert 3 to the above AVL tree.
                        (ht: 2) 10 (BF = 2)
                                 /
                               5(BF = 1 & ht = 1)
                              /
                            3
There is an unbalance in the above AVL tree.  We need to reorganize it using rotation.

                                         5 (BF=0 & ht = 1)
                                       /   \
                                     3     10


Example 2(insertion in right sub-tree):

                              10(ht = 1 & BF = 1)
                                  \ 
                                   20

Insert 30 to the above AVL tree.
                                10 (ht = 2 & BF= 2)
                                   \
                                    20(ht = 1 & BF = 1)
                                       \
                                        30

There is an unbalance in the above AVL tree. We need to reorganize it using rotation.
                                           20 (BF = 0 & ht = 1)
                                          /   \
                                        10   30

Double Rotation:

                        x                              x                                  z
                      /   \                          /    \                            /      \
                     y    ST4                    z      ST4                     y         x
                   /   \             =>        /    \             =>          /   \     /    \
              ST1      z                     y      ST3                 ST1  ST2 ST3  ST4 
                        /   \                 /  \
                  ST2     ST3       ST1   ST2


                          x                            x                                   z
                       /     \                       /    \                            /       \
                   ST1      y      =>          ST1     z      =>               x          y
                            /  \                         /   \                     /    \      /   \
                          z     ST4                ST2      y             ST1     ST2 ST3  ST4
                        /   \                                 /  \
                   ST2    ST3                        ST3   ST4

Example 3:
Insert 45 to the below AVL tree.

                                 50  (BF= 1 & ht = 2)
                               /     \
           (Bf=0&ht=1)40     60(BF=0 & ht=0)
                            /   \
                         30    48



                                 50  (BF= 2 & ht = 3)
                               /     \
           (Bf=1&ht=2)40     60(BF=0 & ht=0)
                            /   \
                         30    48 (BF=0 & ht=0)
                                /
                              45

Height balance property is violated at root node since its balance factor is 2.  So, we need to double rotation for this case in order to make the above AVL tree balanced.

Single rotation between 40 and 48(left rotation).

                            50
                          /    \
                        48    60
                      / 
                   40 
                  /   \
               30    45

Single rotation between 48 and 50(right rotation).

                                     48
                                   /     \
                                40      50 
                              /    \         \
                           30     45       60
So, after double rotation the above AVL tree is height balanced.


Example 4:

                                50 (BF = 1 & ht = 2)
                              /     \
                           40      70 (BF = 0 & ht = 1)
                                   /    \
                                60      80

Insert 55 to the above AVL tree.

                                50 (BF = 2 & ht = 3)
                              /     \
                           40      70 (BF = 1 & ht = 2)
                                   /    \
                                60      80
                                /
                              55

So, height balance property is violated at the root node.  So, we need to do double rotation in order to make the above AVL tree height balanced.

Single rotation(right) between 60 and 70.

                                             50
                                           /     \
                                        40       60
                                                 /    \
                                              55      70
                                                          \
                                                           80

Single rotation(left) between 50 and 60.

                                             60
                                           /     \
                                         50     70
                                       /    \        \
                                     40    55      80

After double rotation, the above AVL tree is height balanced.

Deletion:
We will either delete a leaf or a node with only one child when we do deletion in a Binary search tree.  Deletion in AVL tree is more similar to Binary search tree.  But in addition to deletion, we need to re-balance the AVL tree if the height balance property is violated.

When we delete a node from AVL tree, we need to check the height balance from the deleted node to the root node.  We need to reorganize the nodes where ever(height balance property violated) necessary.


Example Program For Insertion, Deletion & Traversal In AVL Tree(in C):



  #include <stdio.h>
  #include <stdlib.h>

  struct AVLTree_Node {
        int data, bfactor;
        struct AVLTree_Node *link[2];
  };

  struct AVLTree_Node *root = NULL;

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


  void insertion (int data) {
        struct AVLTree_Node *bf, *parent_bf, *subtree, *temp;
        struct AVLTree_Node *current, *parent, *newnode, *ptr;
        int res = 0, link_dir[32], i = 0;

        if (!root) {
                root = createNode(data);
                return;
        }

        bf = parent_bf = root;
        /* find the location for inserting the new node*/
        for (current = root; current != NULL; ptr = current, current = current->link[res]) {
                if (data == current->data) {
                        printf("Cannot insert duplicates!!\n");
                        return;
                }
                res = (data > current->data) ? 1 : 0;
                parent = current;

                if (current->bfactor != 0) {
                        bf = current;
                        parent_bf = ptr;
                        i = 0;
                }
                link_dir[i++] = res;
        }
        /* create the new node */
        newnode = createNode(data);
        parent->link[res] = newnode;
        res = link_dir[i = 0];
        /* updating the height balance after insertion */
        for (current = bf; current != newnode; res = link_dir[++i]) {
                if (res == 0)
                        current->bfactor--;
                else
                        current->bfactor++;
                current = current->link[res];
        }

        /* right sub-tree */
        if (bf->bfactor == 2) {
                printf("bfactor = 2\n");
                temp = bf->link[1];
                if (temp->bfactor == 1) {
                        /* 
                         * single rotation(SR) left
                         *         x              y
                         *          \           /   \
                         *           y    =>   x     z
                         *            \
                         *             z
                         */
                        subtree = temp;
                        bf->link[1] = temp->link[0];
                        temp->link[0] = bf;
                        temp->bfactor = bf->bfactor = 0;
                } else {
                        /*
                         * double rotation (SR right + SR left)
                         *       x        x           z
                         *        \        \        /   \
                         *         y   =>   z  =>  x     y
                         *        /          \       ///
                         *       z            y
                         */
                        subtree = temp->link[0];
                        temp->link[0] = subtree->link[1];
                        subtree->link[1] = temp;
                        bf->link[1] = subtree->link[0];
                        subtree->link[0] = bf;
                        /* update balance factors */
                        if (subtree->bfactor == -1) {
                                bf->bfactor = 0;
                                temp->bfactor = 1;
                        } else if (subtree->bfactor == 0) {
                                bf->bfactor = 0;
                                temp->bfactor = 0;
                        } else if (subtree->bfactor == 1) {
                                bf->bfactor = -1;
                                temp->bfactor = 0;
                        }
                        subtree->bfactor = 0;
                }
        /* left sub-tree */
        } else if (bf->bfactor == -2) {
                temp = bf->link[0];
                if (temp->bfactor == -1) {
                        /*
                         * single rotation(SR) right
                         *          x          y
                         *         /         /   \
                         *        y     =>  z     x
                         *       /
                         *      z
                         */
                        subtree = temp;
                        bf->link[0] = temp->link[1];
                        temp->link[1] = bf;
                        temp->bfactor = bf->bfactor = 0;
                } else {
                        /*
                         * double rotation - (SR left + SR right)
                         *         x         x         z
                         *        /         /        /   \
                         *       y    =>   z    =>  y     x
                         *        \       /
                         *         z     y
                         */
                        subtree = temp->link[1];
                        temp->link[1] = subtree->link[0];
                        subtree->link[0] = temp;
                        bf->link[0] = subtree->link[1];
                        subtree->link[1] = bf;
                        /* update balance factors */
                        if (subtree->bfactor == -1) {
                                bf->bfactor = 1;
                                temp->bfactor = 0;
                        } else if (subtree->bfactor == 0) {
                                bf->bfactor = 0;
                                temp->bfactor = 0;
                        } else if (subtree->bfactor == 1) {
                                bf->bfactor = 0;
                                temp->bfactor = -1;
                        }
                        subtree->bfactor = 0;
                }
        } else {
                return;
        }

        if (bf == root) {
                root = subtree;
                return;
        }
        if (bf != parent_bf->link[0]) {
                parent_bf->link[1] = subtree;
        } else {
                parent_bf->link[0] = subtree;
        }
        return;
  }

  void deletion(int data) {
        int link_dir[32], res = 0, i = 0, j = 0, index = 0;
        struct AVLTree_Node *ptr[32], *current, *temp, *x, *y, *z;

        current = root;
        if (!root) {
                printf("Tree not present\n");
                return;
        }

        if ((root->data == data) && (root->link[0] == NULL)
                 && (root->link[1] == NULL)) {
                free(root);
                root = NULL;
                return;
        }
        /* search the node to delete */
        while (current != NULL) {
                if (current->data == data)
                        break;
                res = data > current->data ? 1 : 0;
                link_dir[i] = res;
                ptr[i++] = current;
                current = current->link[res];
        }

        if (!current) {
                printf("Given data is not present!!\n");
                return;
        }
        index = link_dir[i - 1];
        temp = current->link[1];
        /* delete the node from the AVL tree - similar to BST deletion */
        if (current->link[1] == NULL) {
                if (i == 0) {
                        temp = current->link[0];
                        free(current);
                        root = temp;
                        return;
                } else {
                        ptr[i - 1]->link[index] = current->link[0];
                }
        } else if (temp->link[0] == NULL) {
                temp->link[0] = current->link[0];
                temp->bfactor = current->bfactor;
                if (i > 0) {
                        ptr[i-1]->link[index] = temp;
                } else {
                        root = temp;
                }
                link_dir[i] = 1;
                ptr[i++] = temp;
        } else {
                /* delete node with two children */
                j = i++;
                while (1) {
                        link_dir[i] = 0;
                        ptr[i++] = temp;
                        x = temp->link[0];
                        if (x->link[0] == NULL)
                                break;
                        temp = x;
                }
                x->link[0] = current->link[0];
                temp->link[0] = x->link[1];
                x->link[1] = current->link[1];
                x->bfactor = current->bfactor;
                if (j > 0) {
                        ptr[j - 1]->link[index] = x;
                } else {
                        root = x;
                }
                link_dir[j] = 1;
                ptr[j] = x;
        }
        free(current);
        for (i = i - 1; i >= 0; i = i--) {
                x = ptr[i];
                if (link_dir[i] == 0) {
                        x->bfactor++;
                        if (x->bfactor == 1) {
                                break;
                        } else if (x->bfactor == 2) {
                                y = x->link[1];
                                if (y->bfactor == -1) {
                                        /* double rotation - (SR right + SR left) */
                                        z = y->link[0];
                                        y->link[0] = z->link[1];
                                        z->link[1] = y;
                                        x->link[1] = z->link[0];
                                        z->link[0] = x;
                                        /* update balance factors */
                                        if (z->bfactor == -1) {
                                                x->bfactor = 0;
                                                y->bfactor = 1;
                                        } else if (z->bfactor == 0) {
                                                x->bfactor = 0;
                                                y->bfactor = 0;
                                        } else if (z->bfactor == 1) {
                                                x->bfactor = -1;
                                                y->bfactor = 0;
                                        }
                                        z->bfactor = 0;
                                        if (i > 0) {
                                                index = link_dir[i - 1];
                                                ptr[i - 1]->link[index] = z;
                                        } else {
                                                root = z;
                                        }
                                } else {
                                        /* single rotation left */
                                        x->link[1] = y->link[0];
                                        y->link[0] = x;
                                        if (i > 0) {
                                                index = link_dir[i - 1];
                                                ptr[i - 1]->link[index] = y;
                                        } else  {
                                                root = y;
                                        }
                                        /* update balance factors */
                                        if (y->bfactor == 0) {
                                                x->bfactor = 1;
                                                y->bfactor = -1;
                                                break;
                                        } else {
                                                x->bfactor = 0;
                                                y->bfactor = 0;
                                        }
                                }
                        }
                } else {
                        x->bfactor--;
                        if (x->bfactor == -1) {
                                break;
                        } else if (x->bfactor == -2) {
                                y = x->link[0];
                                if  (y->bfactor == 1) {
                                        /* double rotation - (SR right + SR left) */
                                        z = y->link[1];
                                        y->link[1] = z->link[0];
                                        z->link[0] = y;
                                        x->link[0] = z->link[1];
                                        z->link[1] = x;
                                        /* update balance factors */
                                        if (z->bfactor == -1) {
                                                x->bfactor = 1;
                                                y->bfactor = 0;
                                        } else if (z->bfactor == 0) {
                                                x->bfactor = 0;
                                                y->bfactor = 0;
                                        } else if (z->bfactor == 1) {
                                                x->bfactor = 0;
                                                y->bfactor = -1;
                                        }
                                        z->bfactor = 0;
                                        if (i > 0) {
                                                index = link_dir[i - 1];
                                                ptr[i - 1]->link[index] = z;
                                        } else {
                                                root = z;
                                        }
                                } else {
                                        /* single rotation right */
                                        x->link[0] = y->link[1];
                                        y->link[1] = x;
                                        if (i <= 0) {
                                                root = y;
                                        } else {
                                                index = link_dir[i - 1];
                                                ptr[i - 1]->link[index] = y;
                                        }
                                        /* update balance factors */
                                        if (y->bfactor == 0) {
                                                x->bfactor = -1;
                                                y->bfactor = 1;
                                                break;
                                        } else {
                                                x->bfactor = 0;
                                                y->bfactor = 0;
                                        }
                                }
                        }
                }
        }
  }

  void searchElement(int data) {
        int flag = 0, res = 0;
        struct AVLTree_Node *node = root;
        if (!node) {
                printf("AVL tree unavailable!!\n");
                return;
        }
        while (node != NULL) {
                if (data == node->data) {
                        printf("%d is present in AVL Tree\n", data);
                        flag = 1;
                        break;
                }
                res = data > node->data ? 1 : 0;
                node = node->link[res];
        }
        if (!flag)
                printf("Search Element not found in AVL tree\n");
        return;
  }



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

  int main() {
        int key, ch;
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traversal\n");
                printf("5. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the key value:");
                                scanf("%d", &key);
                                insertion(key);
                                break;
                        case 2:
                                printf("Enter the key value to delete:");
                                scanf("%d", &key);
                                deletion(key);
                                break;
                        case 3:
                                printf("Enter the search key:");
                                scanf("%d", &key);
                                searchElement(key);
                                break;
                        case 4:
                                inorderTraversal(root);
                                printf("\n");
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("Wrong Option!!\n");
                                break;
                }
                printf("\n");
        }
        return 0;
  }
                                                                                                                                                    



  Output(AVL Tree - insertion, deletion, traversal & search - C Program):
  jp@jp-VirtualBox:$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:30

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:15
  
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:40

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:10

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:25

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter the key value:50
  
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  10  15  25  30  40  50  

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:3
  Enter the search key:30
  30 is present in AVL Tree

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:2
  Enter the key value to delete:40

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:2 
  Enter the key value to delete:50

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:2
  Enter the key value to delete:15

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  10  25  30  

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


No comments:

Post a Comment