KsaneK

C - AVL tree w/ delete

May 23rd, 2017
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.92 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. struct node{
  4.     int key;
  5.     int bf; // balance factor
  6.     struct node * parent;
  7.     struct node * left;
  8.     struct node * right;
  9. };
  10.  
  11. void add(struct node * head, int key)
  12. {
  13.     if(!head)return;
  14.     if(key < head->key)
  15.     {
  16.         if(head->left)add(head->left, key);
  17.         else
  18.         {
  19.             struct node * n = (struct node *)malloc(sizeof(struct node));
  20.             n->key = key;
  21.             n->parent = head;
  22.             n->left = n->right = NULL;
  23.             head->left = n;
  24.             struct node * tmp = n;
  25.             while(tmp->parent)tmp=tmp->parent;
  26.             update_bf(tmp);
  27.             //balance_tree(tmp);
  28.         }
  29.     } else if(head->key < key) {
  30.         if(head->right)add(head->right, key);
  31.         else
  32.         {
  33.             struct node * n = (struct node *)malloc(sizeof(struct node));
  34.             n->key = key;
  35.             n->parent = head;
  36.             n->left = n->right = NULL;
  37.             head->right = n;
  38.             struct node * tmp = n;
  39.             while(tmp->parent)tmp=tmp->parent;
  40.             update_bf(tmp);
  41.             //balance_tree(tmp);
  42.         }
  43.     }
  44. }
  45.  
  46. struct node * delete_node(struct node * head, int key)
  47. {
  48.     struct node * tmp = head;
  49.     short change_root = 0;
  50.     while(1)
  51.     {
  52.         if(tmp->key == key)
  53.         {
  54.             if(tmp->parent == NULL)
  55.                 change_root = 1;
  56.             if(tmp->left == NULL && tmp->right == NULL)
  57.             {
  58.                 if(!tmp->parent)
  59.                 {
  60.                     free(tmp);
  61.                     return NULL;
  62.                 } else {
  63.                     if(tmp->parent->key > key)
  64.                         tmp->parent->left = NULL;
  65.                     else
  66.                         tmp->parent->right = NULL;
  67.                     free(tmp);
  68.                     return head;
  69.                 }
  70.             } else if (tmp->right != NULL) {
  71.                 tmp->right->parent = tmp->parent;
  72.                 if(tmp->parent && tmp->parent->key > key)
  73.                     tmp->parent->left = tmp->right;
  74.                 else if(tmp->parent && tmp->parent->key < key)
  75.                     tmp->parent->right = tmp->right;
  76.                 struct node * last_left = tmp->right;
  77.                 while(last_left->left) last_left = last_left->left;
  78.                 last_left->left = tmp->left;
  79.                 if(tmp->left)tmp->left->parent = last_left;
  80.                 struct node * new_tmp = tmp->right;
  81.                 free(tmp);
  82.                 if(change_root)
  83.                     return new_tmp;
  84.                 else
  85.                     return head;
  86.             } else {
  87.                 tmp->left->parent = tmp->parent;
  88.                 if(tmp->parent && tmp->parent->key > key)
  89.                     tmp->parent->left = tmp->left;
  90.                 else if(tmp->parent && tmp->parent->key < key)
  91.                     tmp->parent->right = tmp->left;
  92.                 tmp = tmp->left;
  93.                 free(tmp->parent);
  94.                 if(change_root)
  95.                     return tmp;
  96.                 else
  97.                     return head;
  98.             }
  99.         } else if(tmp->key > key) {
  100.             if(tmp->left)
  101.                 tmp = tmp->left;
  102.             else
  103.             {
  104.                 printf("W drzewie nie znaleziono wartosci %d.", key);
  105.                 return head;
  106.             }
  107.         } else if(tmp->key < key) {
  108.             if(tmp->right)
  109.                 tmp = tmp->right;
  110.             else
  111.             {
  112.                 printf("W drzewie nie znaleziono wartosci %d.", key);
  113.                 return head;
  114.             }
  115.         }
  116.     }
  117. }
  118.  
  119. int update_bf(struct node * head)
  120. {
  121.     // returns tree height and updates balance factor of all nodes
  122.     if(head)
  123.     {
  124.         //printf("%d, %d, %d, %d -> ", head->key,head->left,head->right,head->parent);
  125.         int lh = 1 + update_bf(head->left);
  126.         int rh = 1 + update_bf(head->right);
  127.         head->bf = lh - rh;
  128.         return lh > rh ? lh : rh;
  129.     }
  130. }
  131.  
  132. void LL_rotation(struct node * head)
  133. {
  134.     if(head->parent == NULL)return;
  135.     struct node * parent = head->parent;
  136.     struct node * right = head->right;
  137.     if(parent->key > head->key)
  138.         parent->left = head->right;
  139.     else
  140.         parent->right = head->right;
  141.     head->parent = right;
  142.     head->right = right->left;
  143.     right->parent = parent;
  144.     if(right->left)right->left->parent = head;
  145.     right->left = head;
  146.     struct node * tmp = parent;
  147.     while(tmp->parent)tmp = tmp->parent;
  148.     update_bf(tmp);
  149. }
  150.  
  151. void RR_rotation(struct node * head)
  152. {
  153.     if(head->parent == NULL)return;
  154.     struct node * parent = head->parent;
  155.     struct node * left = head->left;
  156.     if(parent->key > head->key)
  157.         parent->left = head->left;
  158.     else
  159.         parent->right = head->left;
  160.     head->parent = left;
  161.     head->left = left->right;
  162.     left->parent = parent;
  163.     if(left->right)left->right->parent = head;
  164.     left->right = head;
  165.     struct node * tmp = parent;
  166.     while(tmp->parent)tmp = tmp->parent;
  167.     update_bf(tmp);
  168. }
  169.  
  170. void balance_tree(struct node * head)
  171. {
  172.     if(head)
  173.     {
  174.         balance_tree(head->left);
  175.         balance_tree(head->right);
  176.         if(head->bf <= -2 && head->right->bf < 0)
  177.             LL_rotation(head);
  178.         else if(head->bf >= 2 && head->left->bf > 0)
  179.             RR_rotation(head);
  180.     }
  181. }
  182.  
  183. void print_pre(struct node * head)
  184. {
  185.     // print binary tree(pre-order)
  186.     if(head)
  187.     {
  188.         printf("%d, bf: %d\n", head->key, head->bf);
  189.         print_pre(head->left);
  190.         print_pre(head->right);
  191.     }
  192. }
  193.  
  194. int get_tree_height(struct node * head)
  195. {
  196.     if(head)
  197.     {
  198.         int lh = 1 + get_tree_height(head->left);
  199.         int rh = 1 + get_tree_height(head->right);
  200.         return lh > rh ? lh : rh;
  201.     }
  202. }
  203.  
  204. int main()
  205. {
  206.     printf("AVL BINARY TREE\n\n");
  207.     struct node * head = (struct node *)malloc(sizeof(struct node));
  208.     head->parent = head->left = head->right = NULL;
  209.     head->key = 7;
  210.     head->bf = 0;
  211.     add(head, 10);
  212.     add(head, 8);
  213.     add(head, 5);
  214.     add(head, 4);
  215.     add(head, 6);
  216.     add(head, 15);
  217.     add(head, 14);
  218.     add(head, 17);
  219.     add(head, 18);
  220.     add(head, 3);
  221.     add(head, 2);
  222.     add(head, 1);
  223.     int height = get_tree_height(head);
  224.     printf("PREORDER:\n");
  225.     print_pre(head);
  226.     printf("Tree height: %d\n", height);
  227.     balance_tree(head);
  228.     printf("\n\nBALANCED:\n");
  229.     print_pre(head);
  230.     height = get_tree_height(head);
  231.     printf("Tree height: %d\n", height);
  232.     head = delete_node(head, 5);
  233.     head = delete_node(head, 6);
  234.     //head = delete_node(head, 3);
  235.     struct node * t = head->left->left;
  236.     printf("\n\n%d - %d - %d\n\n", t->key, t->left, t->right);
  237.     //head = delete_node(head, 2);
  238.     //head = delete_node(head, 5);
  239.     //head = delete_node(head, 6);
  240.  
  241.     update_bf(head);
  242.     print_pre(head);
  243.     balance_tree(head);
  244.     printf("---\n");
  245.     print_pre(head);
  246.     return 0;
  247. }
Advertisement
Add Comment
Please, Sign In to add comment