SHARE
TWEET

Untitled

a guest Jan 28th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "binary_tree.h"
  2.  
  3. binary_tree *create_empty_binary_tree() {
  4.     return NULL;
  5. }
  6.  
  7. binary_tree *create_binary_tree(lli item, binary_tree *left, binary_tree *right) {
  8.     binary_tree *new_bt = (binary_tree*) malloc(sizeof(binary_tree));
  9.     new_bt->item = item;
  10.     new_bt->height = 1;
  11.     new_bt->left = new_bt->right = NULL;
  12.     return new_bt;
  13. }
  14.  
  15. int is_empty(binary_tree *bt) {
  16.     return bt == NULL;
  17. }
  18.  
  19. int max(int a, int b) {
  20.     return (a > b) ? a : b;
  21. }
  22.  
  23. int height(binary_tree *bt) {
  24.     if (bt == NULL) {
  25.         return -1;
  26.     } else {
  27.         return 1 + max(height(bt->left), height(bt->right));
  28.     }
  29. }
  30.  
  31. binary_tree *min_value_node(binary_tree *bt) {
  32.     binary_tree *current = bt;
  33.  
  34.     /* loop down to find the leftmost leaf */
  35.     while (current->left != NULL) {
  36.         current = current->left;
  37.     }
  38.  
  39.     return current;
  40. }
  41.  
  42. binary_tree *search(binary_tree *bt, lli item, lli *cont) {
  43.     binary_tree *new_bt = bt;
  44.     *cont += 1;
  45.     if ((new_bt == NULL) || (new_bt->item == item)) {
  46.         return new_bt;
  47.     } else if (new_bt->item > item) {
  48.         search(new_bt->left, item, cont);
  49.     } else {
  50.         search(new_bt->right, item, cont);
  51.     }
  52. }
  53.  
  54. void print_tree(binary_tree *bt) {
  55.     if (!is_empty(bt)) {
  56.         printf(" ( ");
  57.         printf("%lld ", bt->item);
  58.  
  59.         if (bt->left == NULL) {
  60.             printf(" () ");
  61.         } else {
  62.             print_tree(bt->left);
  63.         } if (bt->right == NULL) {
  64.             printf(" () ");
  65.         } else {
  66.             print_tree(bt->right);
  67.         }
  68.         printf(") ");
  69.     }
  70. }
  71.  
  72. /*--------------------------------------------------------------------------*/
  73. // AVL:
  74.  
  75. int is_balanced_avl(binary_tree *bt) {
  76.     if (bt == NULL) {
  77.         return 0;
  78.     }
  79.     return height(bt->left) - height(bt->right);
  80. }
  81.  
  82. // Four cases:
  83. // y is left child of z and x is left child of y (Left Left Case)
  84. // y is left child of z and x is right child of y (Left Right Case)
  85. // y is right child of z and x is right child of y (Right Right Case)
  86. // y is right child of z and x is left child of y (Right Left Case)
  87.  
  88. binary_tree *rotate_right_avl(binary_tree *bt) {
  89.     binary_tree *child = bt->left;
  90.     binary_tree *right_child = child->right;
  91.  
  92.     // Perform rotation
  93.     child->right = bt;
  94.     bt->left = right_child;
  95.  
  96.     // Update height_avls
  97.     bt->height = max(height(bt->left), height(bt->right)) + 1;
  98.     child->height = max(height(child->left), height(child->right)) + 1;
  99.  
  100.     // Return new bt
  101.     return child;
  102. }
  103.  
  104. // A utility function to left rotate subtree bted with x
  105. // See the diagram given above.
  106. binary_tree *rotate_left_avl(binary_tree *bt) {
  107.     binary_tree *child = bt->right;
  108.     binary_tree *left_child = child->left;
  109.  
  110.     // Perform rotation
  111.     child->left = bt;
  112.     bt->right = left_child;
  113.  
  114.     //  Update height_avls
  115.     bt->height = max(height(bt->left), height(bt->right))+1;
  116.     child->height = max(height(child->left), height(child->right))+1;
  117.  
  118.     // Return new bt
  119.     return child;
  120. }
  121.  
  122. binary_tree *add_avl(binary_tree *bt, lli key) {
  123.     /* 1.  Perform the normal BST rotation */
  124.     if (bt == NULL)
  125.         return (create_binary_tree(key, NULL, NULL));
  126.  
  127.     if (key < bt->item) {
  128.         bt->left  = add_avl(bt->left, key);
  129.     }
  130.     else if (key > bt->item) {
  131.         bt->right = add_avl(bt->right, key);
  132.     } else {// Equal keys not allowed
  133.          return bt;
  134.     }
  135.     /* 2. Update height_avl of this ancestor bt */
  136.     bt->height = 1 + max(height(bt->left), height(bt->right));
  137.  
  138.     /* 3. Get the balance factor of this ancestor
  139.           bt to check whether this bt became
  140.           unbalanced */
  141.     //printf("bt -> item %lld /// key -> %lld\n", bt->item, key);
  142.     int balance = is_balanced_avl(bt);
  143.  
  144.     // If this bt becomes unbalanced, then there are 4 cases
  145.  
  146.     // Left Left Case
  147.     if (balance > 1 && key < bt->left->item) {
  148.         return rotate_right_avl(bt);
  149.     }
  150.  
  151.     // Right Right Case
  152.     if (balance < -1 && key > bt->right->item) {
  153.         return rotate_left_avl(bt);
  154.     }
  155.  
  156.     // Left Right Case
  157.     if (balance > 1 && key > bt->left->item) {
  158.         bt->left =  rotate_left_avl(bt->left);
  159.         return rotate_right_avl(bt);
  160.     }
  161.  
  162.     // Right Left Case
  163.     if (balance < -1 && key < bt->right->item) {
  164.         bt->right = rotate_right_avl(bt->right);
  165.         return rotate_left_avl(bt);
  166.     }
  167.  
  168.     /* return the (unchanged) bt pointer */
  169.     return bt;
  170. }
  171.  
  172. binary_tree *delete_node_avl(binary_tree *bt, lli key) {
  173.     // ETAPA 1: EXECUTAR PADRÃO BST DELETE
  174.     if (bt == NULL) {
  175.         return bt;
  176.     }
  177.  
  178.     // Se a chave a ser apagada é menor que a
  179.     // chave do bt, então está na subárvore esquerda
  180.     if (key < bt->item) {
  181.         bt->left = delete_node_avl(bt->left, key);
  182.     }
  183.     // Se a chave a ser apagada for maior que a chave
  184.     // chave do bt, então está na subárvore direita
  185.     else if(key > bt->item) {
  186.         bt->right = delete_node_avl(bt->right, key);
  187.     }
  188.  
  189.     // se a chave é a mesma que a chave do bt, então
  190.     // ele é o nó a ser deletado
  191.     else
  192.     {
  193.         // node com apenas um filho ou sem filho
  194.         if((bt->left == NULL) || (bt->right == NULL))
  195.         {
  196.             //binary_tree *temp = bt->left ? bt->left : bt->right;
  197.             binary_tree *temp;
  198.  
  199.             if (bt->left == NULL) {
  200.                 temp = bt->right;
  201.             } else {
  202.                 temp = bt->left;
  203.             }
  204.  
  205.             // Caso sem filhos
  206.             if (temp == NULL) {
  207.                 temp = bt;
  208.                 bt = NULL;
  209.             }
  210.             // Case de um filho
  211.             else {
  212.                 // Copie o conteúdo de a criança não vazia
  213.                 // se nao usar esses ponteiros a saida fica assim quando for eliminar a cabeca:
  214.                 //( 94555905660672  ()  () )
  215.                 *bt = *temp;
  216.                 free(temp);
  217.             }
  218.         } else {
  219.             // node com dois filhos: pegar o sucessor
  220.             // em ordem (menor na subarvore a direita)
  221.             binary_tree *temp = min_value_node(bt->right);
  222.  
  223.             // copiar o conteudo do sucessor em ordem para este node
  224.             bt->item = temp->item;
  225.  
  226.             // deletar este sucessor em ordem
  227.             bt->right = delete_node_avl(bt->right, temp->item);
  228.         }
  229.     }
  230.  
  231.     // se a arvore tem apenas um node entao retorna
  232.     if (bt == NULL) {
  233.         return bt;
  234.     }
  235.  
  236.     // ETAPA 2: Atualizar a altura do node atual
  237.     bt->height = 1 + max(height(bt->left), height(bt->right));
  238.  
  239.     // STEP 3: Pegar o fator de balanceamento deste node(para
  240.     // verificar se o node se tornou desbalanceou
  241.     int balance = is_balanced_avl(bt);
  242.     //printf("%d\n", balance);
  243.     // Se este nó se tornar desbalanceado, existem 4 casos
  244.  
  245.     // Caso esquerda esquerda
  246.     if (balance > 1 && is_balanced_avl(bt->left) >= 0) {
  247.         return rotate_right_avl(bt);
  248.     }
  249.  
  250.     // Caso Esquerda Direita
  251.     if (balance > 1 && is_balanced_avl(bt->left) < 0) {
  252.         bt->left =  rotate_left_avl(bt->left);
  253.         return rotate_right_avl(bt);
  254.     }
  255.  
  256.     // Caso Direita Direita
  257.     if (balance < -1 && is_balanced_avl(bt->right) <= 0) {
  258.         return rotate_left_avl(bt);
  259.     }
  260.  
  261.     // Caso Direita Esquerda
  262.     if (balance < -1 && is_balanced_avl(bt->right) > 0) {
  263.         bt->right = rotate_right_avl(bt->right);
  264.         return rotate_left_avl(bt);
  265.     }
  266.  
  267.     return bt;
  268. }
  269.  
  270. /*--------------------------------------------------------------------------*/
  271. // ABB:
  272.  
  273. binary_tree *add_ubt(binary_tree *bt, lli key)
  274. {
  275.     /* 1.  Perform the normal BST rotation */
  276.     if (bt == NULL) {
  277.         return (create_binary_tree(key, NULL, NULL));
  278.     }
  279.  
  280.     binary_tree *aux = bt;
  281.     binary_tree *previous;
  282.  
  283.     while (aux != NULL) {
  284.         previous = aux;
  285.         if (key < aux->item) {
  286.             aux = aux->left;
  287.         } else {
  288.             aux = aux->right;
  289.         }
  290.     }
  291.  
  292.     if (key < previous->item) {
  293.         previous->left = create_binary_tree(key, NULL, NULL);
  294.     } else {
  295.         previous->right = create_binary_tree(key, NULL, NULL);
  296.     }
  297.  
  298.     /* return the (unchanged) bt pointer */
  299.     return bt;
  300. }
  301.  
  302. binary_tree *delete_node_ubt(binary_tree *bt, lli key)
  303. {
  304.     // ETAPA 1: EXECUTAR PADRÃO BST DELETE
  305.     if (bt == NULL) {
  306.         return bt;
  307.     }
  308.  
  309.     // Se a chave a ser apagada é menor que a
  310.     // chave do bt, então está na subárvore esquerda
  311.     if (key < bt->item) {
  312.         bt->left = delete_node_ubt(bt->left, key);
  313.     }
  314.     // Se a chave a ser apagada for maior que a chave
  315.     // chave do bt, então está na subárvore direita
  316.     else if(key > bt->item) {
  317.         bt->right = delete_node_ubt(bt->right, key);
  318.     }
  319.  
  320.     // se a chave é a mesma que a chave do bt, então
  321.     // ele é o nó a ser deletado
  322.     else {
  323.         // node with only one child or no child
  324.         if (bt->left == NULL) {
  325.             binary_tree *temp = bt->right;
  326.             free(bt);
  327.             return temp;
  328.         } else if (bt->right == NULL) {
  329.             binary_tree *temp = bt->left;
  330.             free(bt);
  331.             return temp;
  332.         }
  333.         // node with two children: Get the inorder successor (smallest
  334.         // in the right sbtree)
  335.         binary_tree *temp = min_value_node(bt->right);
  336.  
  337.         // Copy the inorder successor's content to this node
  338.         bt->item = temp->item;
  339.  
  340.         // Delete the inorder successor
  341.         bt->right = delete_node_ubt(bt->right, temp->item);
  342.     }
  343.  
  344.     bt->height = 1 + max(height(bt->left), height(bt->right));
  345.     // ETAPA 2: Atualizar a altura do node atual
  346.     return bt;
  347. }
RAW Paste Data
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
Top