API tools faq
paste
tsnaik

appid_sessionstore

tsnaik
Feb 10th, 2016
250
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 18.16 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include<stdint.h>
  4. //#include"appid_hashing.c"
  5.  
  6.   struct AVLTree_Node
  7.   {
  8.         uint16_t data, bfactor;
  9.         struct AVLTree_Node *link[2];
  10.     struct node *head;
  11.   };
  12.  
  13.   struct AVLTree_Node *root = NULL;
  14.  
  15.   struct AVLTree_Node * createNode(uint16_t data , struct node *head)
  16.   {
  17.         struct AVLTree_Node *newnode;
  18.         newnode = (struct AVLTree_Node *)malloc(sizeof (struct AVLTree_Node));
  19.         newnode->data    = data;
  20.         newnode->bfactor = 0;
  21.         newnode->link[0] = newnode->link[1] = NULL;
  22.     newnode->head = head;
  23.         return newnode;
  24.   }
  25.  
  26.  
  27.   void insertion (uint16_t data , struct node *head)
  28.   {
  29.         struct AVLTree_Node *bf, *parent_bf, *subtree, *temp;
  30.         struct AVLTree_Node *current, *parent, *newnode, *ptr;
  31.         uint16_t res = 0, link_dir[32], i = 0;
  32.  
  33.         if (!root) {
  34.                 root = createNode(data,head);
  35.                 return;
  36.         }
  37.  
  38.         bf = parent_bf = root;
  39.         /* find the location for inserting the new node*/
  40.         for (current = root; current != NULL; ptr = current, current = current->link[res]) {
  41.                 if (data == current->data) {
  42.                         printf("Cannot insert duplicates!!\n");
  43.                         return;
  44.                 }
  45.                 res = (data > current->data) ? 1 : 0;
  46.                 parent = current;
  47.  
  48.                 if (current->bfactor != 0) {
  49.                         bf = current;
  50.                         parent_bf = ptr;
  51.                         i = 0;
  52.                 }
  53.                 link_dir[i++] = res;
  54.         }
  55.         /* create the new node */
  56.         newnode = createNode(data,head);
  57.         parent->link[res] = newnode;
  58.         res = link_dir[i = 0];
  59.         /* updating the height balance after insertion */
  60.         for (current = bf; current != newnode; res = link_dir[++i]) {
  61.                 if (res == 0)
  62.                         current->bfactor--;
  63.                 else
  64.                         current->bfactor++;
  65.                 current = current->link[res];
  66.         }
  67.  
  68.         /* right sub-tree */
  69.         if (bf->bfactor == 2) {
  70.                 printf("bfactor = 2\n");
  71.                 temp = bf->link[1];
  72.                 if (temp->bfactor == 1) {
  73.                         /*
  74.                          * single rotation(SR) left
  75.                          *         x              y
  76.                          *          \           /   \
  77.                          *           y    =>   x     z
  78.                          *            \
  79.                          *             z
  80.                          */
  81.                         subtree = temp;
  82.                         bf->link[1] = temp->link[0];
  83.                         temp->link[0] = bf;
  84.                         temp->bfactor = bf->bfactor = 0;
  85.                 } else {
  86.                         /*
  87.                          * double rotation (SR right + SR left)
  88.                          *       x        x           z
  89.                          *        \        \        /   \
  90.                          *         y   =>   z  =>  x     y
  91.                          *        /          \       ///
  92.                          *       z            y
  93.                          */
  94.                         subtree = temp->link[0];
  95.                         temp->link[0] = subtree->link[1];
  96.                         subtree->link[1] = temp;
  97.                         bf->link[1] = subtree->link[0];
  98.                         subtree->link[0] = bf;
  99.                         /* update balance factors */
  100.                         if (subtree->bfactor == -1) {
  101.                                 bf->bfactor = 0;
  102.                                 temp->bfactor = 1;
  103.                         } else if (subtree->bfactor == 0) {
  104.                                 bf->bfactor = 0;
  105.                                 temp->bfactor = 0;
  106.                         } else if (subtree->bfactor == 1) {
  107.                                 bf->bfactor = -1;
  108.                                 temp->bfactor = 0;
  109.                         }
  110.                         subtree->bfactor = 0;
  111.                 }
  112.         /* left sub-tree */
  113.         } else if (bf->bfactor == -2) {
  114.                 temp = bf->link[0];
  115.                 if (temp->bfactor == -1) {
  116.                         /*
  117.                          * single rotation(SR) right
  118.                          *          x          y
  119.                          *         /         /   \
  120.                          *        y     =>  z     x
  121.                          *       /
  122.                          *      z
  123.                          */
  124.                         subtree = temp;
  125.                         bf->link[0] = temp->link[1];
  126.                         temp->link[1] = bf;
  127.                         temp->bfactor = bf->bfactor = 0;
  128.                 } else {
  129.                         /*
  130.                          * double rotation - (SR left + SR right)
  131.                          *         x         x         z
  132.                          *        /         /        /   \
  133.                          *       y    =>   z    =>  y     x
  134.                          *        \       /
  135.                          *         z     y
  136.                          */
  137.                         subtree = temp->link[1];
  138.                         temp->link[1] = subtree->link[0];
  139.                         subtree->link[0] = temp;
  140.                         bf->link[0] = subtree->link[1];
  141.                         subtree->link[1] = bf;
  142.                         /* update balance factors */
  143.                         if (subtree->bfactor == -1) {
  144.                                 bf->bfactor = 1;
  145.                                 temp->bfactor = 0;
  146.                         } else if (subtree->bfactor == 0) {
  147.                                 bf->bfactor = 0;
  148.                                 temp->bfactor = 0;
  149.                         } else if (subtree->bfactor == 1) {
  150.                                 bf->bfactor = 0;
  151.                                 temp->bfactor = -1;
  152.                         }
  153.                         subtree->bfactor = 0;
  154.                 }
  155.         } else {
  156.                 return;
  157.         }
  158.  
  159.         if (bf == root) {
  160.                 root = subtree;
  161.                 return;
  162.         }
  163.         if (bf != parent_bf->link[0]) {
  164.                 parent_bf->link[1] = subtree;
  165.         } else {
  166.                 parent_bf->link[0] = subtree;
  167.         }
  168.         return;
  169.   }
  170.  
  171.   void deletion(uint16_t data) {
  172.         uint16_t link_dir[32], res = 0, i = 0, j = 0, index = 0;
  173.         struct AVLTree_Node *ptr[32], *current, *temp, *x, *y, *z;
  174.  
  175.         current = root;
  176.         if (!root) {
  177.                 printf("Tree not present\n");
  178.                 return;
  179.         }
  180.  
  181.         if ((root->data == data) && (root->link[0] == NULL)
  182.                  && (root->link[1] == NULL)) {
  183.                 free(root);
  184.                 root = NULL;
  185.                 return;
  186.         }
  187.         /* search the node to delete */
  188.         while (current != NULL) {
  189.                 if (current->data == data)
  190.                         break;
  191.                 res = data > current->data ? 1 : 0;
  192.                 link_dir[i] = res;
  193.                 ptr[i++] = current;
  194.                 current = current->link[res];
  195.         }
  196.  
  197.         if (!current) {
  198.                 printf("Given data is not present!!\n");
  199.                 return;
  200.         }
  201.         index = link_dir[i - 1];
  202.         temp = current->link[1];
  203.         /* delete the node from the AVL tree - similar to BST deletion */
  204.         if (current->link[1] == NULL) {
  205.                 if (i == 0) {
  206.                         temp = current->link[0];
  207.                         free(current);
  208.                         root = temp;
  209.                         return;
  210.                 } else {
  211.                         ptr[i - 1]->link[index] = current->link[0];
  212.                 }
  213.         } else if (temp->link[0] == NULL) {
  214.                 temp->link[0] = current->link[0];
  215.                 temp->bfactor = current->bfactor;
  216.                 if (i > 0) {
  217.                         ptr[i-1]->link[index] = temp;
  218.                 } else {
  219.                         root = temp;
  220.                 }
  221.                 link_dir[i] = 1;
  222.                 ptr[i++] = temp;
  223.         } else {
  224.                 /* delete node with two children */
  225.                 j = i++;
  226.                 while (1) {
  227.                         link_dir[i] = 0;
  228.                         ptr[i++] = temp;
  229.                         x = temp->link[0];
  230.                         if (x->link[0] == NULL)
  231.                                 break;
  232.                         temp = x;
  233.                 }
  234.                 x->link[0] = current->link[0];
  235.                 temp->link[0] = x->link[1];
  236.                 x->link[1] = current->link[1];
  237.                 x->bfactor = current->bfactor;
  238.                 if (j > 0) {
  239.                         ptr[j - 1]->link[index] = x;
  240.                 } else {
  241.                         root = x;
  242.                 }
  243.                 link_dir[j] = 1;
  244.                 ptr[j] = x;
  245.         }
  246.         free(current);
  247.         for (i = i - 1; i >= 0; i = i--) {
  248.                 x = ptr[i];
  249.                 if (link_dir[i] == 0) {
  250.                         x->bfactor++;
  251.                         if (x->bfactor == 1) {
  252.                                 break;
  253.                         } else if (x->bfactor == 2) {
  254.                                 y = x->link[1];
  255.                                 if (y->bfactor == -1) {
  256.                                         /* double rotation - (SR right + SR left) */
  257.                                         z = y->link[0];
  258.                                         y->link[0] = z->link[1];
  259.                                         z->link[1] = y;
  260.                                         x->link[1] = z->link[0];
  261.                                         z->link[0] = x;
  262.                                         /* update balance factors */
  263.                                         if (z->bfactor == -1) {
  264.                                                 x->bfactor = 0;
  265.                                                 y->bfactor = 1;
  266.                                         } else if (z->bfactor == 0) {
  267.                                                 x->bfactor = 0;
  268.                                                 y->bfactor = 0;
  269.                                         } else if (z->bfactor == 1) {
  270.                                                 x->bfactor = -1;
  271.                                                 y->bfactor = 0;
  272.                                         }
  273.                                         z->bfactor = 0;
  274.                                         if (i > 0) {
  275.                                                 index = link_dir[i - 1];
  276.                                                 ptr[i - 1]->link[index] = z;
  277.                                         } else {
  278.                                                 root = z;
  279.                                         }
  280.                                 } else {
  281.                                         /* single rotation left */
  282.                                         x->link[1] = y->link[0];
  283.                                         y->link[0] = x;
  284.                                         if (i > 0) {
  285.                                                 index = link_dir[i - 1];
  286.                                                 ptr[i - 1]->link[index] = y;
  287.                                         } else  {
  288.                                                 root = y;
  289.                                         }
  290.                                         /* update balance factors */
  291.                                         if (y->bfactor == 0) {
  292.                                                 x->bfactor = 1;
  293.                                                 y->bfactor = -1;
  294.                                                 break;
  295.                                         } else {
  296.                                                 x->bfactor = 0;
  297.                                                 y->bfactor = 0;
  298.                                         }
  299.                                 }
  300.                         }
  301.                 } else {
  302.                         x->bfactor--;
  303.                         if (x->bfactor == -1) {
  304.                                 break;
  305.                         } else if (x->bfactor == -2) {
  306.                                 y = x->link[0];
  307.                                 if  (y->bfactor == 1) {
  308.                                         /* double rotation - (SR right + SR left) */
  309.                                         z = y->link[1];
  310.                                         y->link[1] = z->link[0];
  311.                                         z->link[0] = y;
  312.                                         x->link[0] = z->link[1];
  313.                                         z->link[1] = x;
  314.                                         /* update balance factors */
  315.                                         if (z->bfactor == -1) {
  316.                                                 x->bfactor = 1;
  317.                                                 y->bfactor = 0;
  318.                                         } else if (z->bfactor == 0) {
  319.                                                 x->bfactor = 0;
  320.                                                 y->bfactor = 0;
  321.                                         } else if (z->bfactor == 1) {
  322.                                                 x->bfactor = 0;
  323.                                                 y->bfactor = -1;
  324.                                         }
  325.                                         z->bfactor = 0;
  326.                                         if (i > 0) {
  327.                                                 index = link_dir[i - 1];
  328.                                                 ptr[i - 1]->link[index] = z;
  329.                                         } else {
  330.                                                 root = z;
  331.                                         }
  332.                                 } else {
  333.                                         /* single rotation right */
  334.                                         x->link[0] = y->link[1];
  335.                                         y->link[1] = x;
  336.                                         if (i <= 0) {
  337.                                                 root = y;
  338.                                         } else {
  339.                                                 index = link_dir[i - 1];
  340.                                                 ptr[i - 1]->link[index] = y;
  341.                                         }
  342.                                         /* update balance factors */
  343.                                         if (y->bfactor == 0) {
  344.                                                 x->bfactor = -1;
  345.                                                 y->bfactor = 1;
  346.                                                 break;
  347.                                         } else {
  348.                                                 x->bfactor = 0;
  349.                                                 y->bfactor = 0;
  350.                                         }
  351.                                 }
  352.                         }
  353.                 }
  354.         }
  355.   }
  356.  
  357.   uint16_t searchElement(uint16_t data) {
  358.         uint16_t flag = 0, res = 0;
  359.         struct AVLTree_Node *node = root;
  360.         if (!node) {
  361.           //      printf("AVL tree unavailable!!\n");
  362.                 return 0;
  363.         }
  364.         while (node != NULL) {
  365.                 if (data == node->data) {
  366.                         printf("%d is present in AVL Tree\n", data);
  367.                         flag = 1;
  368.                         break;
  369.                 }
  370.                 res = data > node->data ? 1 : 0;
  371.                 node = node->link[res];
  372.         }
  373.         if (!flag)
  374.         return 0;
  375.                // printf("Search Element not found in AVL tree\n");
  376.         return 1;
  377.   }
  378.  
  379. struct node * searchHead(uint16_t data){
  380.  
  381.         uint16_t flag = 0, res = 0;
  382.         struct AVLTree_Node *node = root;
  383.         if (!node) {
  384.           //      printf("AVL tree unavailable!!\n");
  385.                 return NULL;
  386.         }
  387.         while (node != NULL) {
  388.                 if (data == node->data) {
  389.                         //printf("%d is present in AVL Tree\n", data);
  390.                         flag = 1;
  391.                         break;
  392.                 }
  393.                 res = data > node->data ? 1 : 0;
  394.                 node = node->link[res];
  395.         }
  396.         if (!flag)
  397.         return NULL;
  398.                // printf("Search Element not found in AVL tree\n");
  399.         return (node-> head);
  400.  
  401.  
  402. }
  403.  
  404.  
  405.  
  406.   void inorderTraversal(struct AVLTree_Node *myNode) {
  407.         if (myNode) {
  408.                 inorderTraversal(myNode->link[0]);
  409.                 printf("%d  ", myNode->data);
  410.                 inorderTraversal(myNode->link[1]);
  411.         }
  412.         return;
  413.   }
  414.  
  415.   /*uint16_t main() {
  416.         uint16_t key, ch;
  417.         while (1) {
  418.                 printf("1. Insertion\t2. Deletion\n");
  419.                 printf("3. Searching\t4. Traversal\n");
  420.                 printf("5. Exit\nEnter your choice:");
  421.                 scanf("%d", &ch);
  422.                 switch (ch) {
  423.                         case 1:
  424.                                 printf("Enter the key value:");
  425.                                 scanf("%d", &key);
  426.                                 insertion(key);
  427.                                 break;
  428.                         case 2:
  429.                                 printf("Enter the key value to delete:");
  430.                                 scanf("%d", &key);
  431.                                 deletion(key);
  432.                                 break;
  433.                         case 3:
  434.                                 printf("Enter the search key:");
  435.                                 scanf("%d", &key);
  436.                                 searchElement(key);
  437.                                 break;
  438.                         case 4:
  439.                                 inorderTraversal(root);
  440.                                 printf("\n");
  441.                                 break;
  442.                         case 5:
  443.                                 exit(0);
  444.                         default:
  445.                                 printf("Wrong Option!!\n");
  446.                                 break;
  447.                 }
  448.                 printf("\n");
  449.         }
  450.         return 0;
  451.   }*/
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!