fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef struct node_avl {
  4.     int key;
  5.     int bal;
  6.     int height;
  7.     struct node_avl *left;
  8.     struct node_avl *right;
  9.     struct node_avl *parent;
  10.  
  11. }node_avl;
  12.  
  13. void free_tree(node_avl *root) {
  14.     if (root == NULL) {
  15.         return;
  16.     }
  17.     free_tree(root->left);
  18.     free_tree(root->right);
  19.     free(root);
  20. }
  21.  
  22. node_avl* create_node(int key) {
  23.     node_avl *root = (node_avl*)malloc(sizeof(node_avl));
  24.     if(root == NULL) {
  25.         printf("\nERORR ALLOCATE");
  26.         exit(1);
  27.     }
  28.     root->key = key;
  29.     root->left = NULL;
  30.     root->right = NULL;
  31.     root->parent = NULL;
  32.     root->bal = 0;
  33.     root->height = 1;
  34.     return root;
  35. }
  36.  
  37. void inOrder(node_avl *root) {
  38.     if(root != NULL) {
  39.         inOrder(root->left);
  40.         printf("\nkey = %-5d bal = %-5d height = %-5d",root->key, root->bal, root->height);
  41.         inOrder(root->right);
  42.     }
  43.  
  44. }
  45.  
  46. int max_(int a, int b) {
  47.     return ( a > b ? a : b);
  48. }
  49.  
  50. int height(node_avl *root) {
  51.     if(root == NULL) return 0;
  52.     else {
  53.         int lheight = height(root->left);
  54.         int rheight = height(root->right);
  55.         root->height = 1 + max_(lheight, rheight);
  56.         return root->height;
  57.     }
  58. }
  59.  
  60. int balance(node_avl *root) {
  61.     if(root == NULL) return 0;
  62.     else {
  63.         int lheight = height(root->left);
  64.         int rheight = height(root->right);
  65.         root->bal = lheight - rheight;
  66.         return root->bal;
  67.     }
  68. }
  69.  
  70. node_avl* rightRotate(node_avl *k2) {
  71.     node_avl *k1 = k2->left;
  72.     node_avl *tmp = k1->right;
  73.  
  74.     // thuc hien xoay
  75.     k1->right = k2;
  76.     k2->left = tmp;
  77.     // update height , bal;
  78.  
  79.     // phai de la height(k2->left) vi neu no null thi con ra 0
  80.     k2->height = max_(height(k2->left), height(k2->right)) + 1;
  81.     k1->height = max_(height(k1->left), height(k2)) + 1;
  82.  
  83.     k2->bal = balance(k2);
  84.     k1->bal = balance(k1);
  85. //    printf("%d", k1->key);
  86. //    inOrder(k1);
  87.     return k1;
  88.  
  89. }
  90.  
  91. node_avl* leftRotate(node_avl *k2) {
  92.     node_avl *k1 = k2->right;
  93.     node_avl *tmp = k1->left;
  94.  
  95.     // thuc hien xoay
  96.     k1->left = k2;
  97.     k2->right = tmp;
  98.     // update height , bal;
  99.     k2->height = max_(height(k2->right), height(k2->left)) + 1;
  100.     k1->height = max_(height(k1->right), height(k2)) + 1;
  101.     k2->bal = balance(k2);
  102.     k1->bal = balance(k1);
  103. //    printf("%d", k1->key);
  104. //    inOrder(k1);
  105.     return k1;
  106.  
  107. }
  108.  
  109. node_avl* insert_avl(node_avl *root, int value) {
  110.     if( root == NULL) {
  111.         root = create_node(value);
  112.     } else if ( value > root->key) {
  113.         root->right = insert_avl(root->right, value);
  114.         /* update pararen cho node them vao do
  115.             se bi trung lap vs cai node truoc do
  116.             nhung khong sao
  117.         */
  118.         root->right->parent = root;
  119.     } else if ( value < root->key) {
  120.         root->left = insert_avl(root->left, value);
  121.         root->left->parent = root;
  122.     } else return root; // truong hop key duplicate
  123.  
  124.     int heigth = height(root);
  125.     int bal = balance(root);
  126.  
  127.     if(bal > 1 && value < root->left->key) {
  128.     /**
  129.             tinh huong 1: xoay phai-lech trai
  130.     */
  131.         return rightRotate(root);
  132.     } else if ( bal < -1 && value > root->right->key) {
  133.         /**
  134.             tinh huong 2: xoay trai-lech phai
  135.     */
  136.         return leftRotate(root);
  137.     }
  138.     else if(bal > 1 && value > root->left->key) {
  139.             /**
  140.             tinh huong 3: xoay phai, xong xoay trai
  141.             cay con trai cao hon cay con phai do cay con phai cua cay con trai
  142.     */
  143.         root->left = leftRotate(root->left);
  144.         return rightRotate(root);
  145.     }
  146.     else if(bal < -1 && value < root->right->key) {
  147.             /**
  148.             tinh huong 4: xoay trai, xong xoay phai
  149.             cay con phai cao hon cay con trai do cay con trai cua cay con phai
  150.     */
  151.         root->right = rightRotate(root->right);
  152.         return leftRotate(root);
  153.     }
  154.     return root;
  155. }
  156.  
  157. node_avl* search_(node_avl *root, int target) {
  158.     if( root!= NULL) {
  159.         if(target < root->key) {
  160.             return search_(root->left, target);
  161.         } else if ( target > root->key) {
  162.             return search_(root->right, target);
  163.         }
  164.         return root;
  165.     }
  166.     return NULL;
  167. }
  168.  
  169. node_avl* find_min(node_avl *root) {
  170.     if(root == NULL) {
  171.         return (NULL);
  172.     } else {
  173.         if(root->left == NULL) return root;
  174.         else return find_min(root->left);
  175.     }
  176. }
  177.  
  178. node_avl *delete_avl(node_avl *root, int value) {
  179.     node_avl *tmp;
  180.     if( value > root->key) {
  181.         root->right = delete_avl(root->right, value);
  182.     } else if( value < root->key) {
  183.         root->left = delete_avl(root->left, value);
  184.     } else if(root->left && root->right){
  185.         /** node co 2 con, roi vao truong hop 4
  186.             tim sucessor y cua node can xoa x
  187.             go y ra khoi cay
  188.             noi con con phai cua y vao cha cua y (VI SUCCESSOR CUA NO LA PHAN TU TRAI NHAT ROI,
  189.              NEN NEU CO, THI CHI CO THE CO CON PHAI THOI)
  190.             thay the y vao vi tri can xoa
  191.         */
  192.         tmp = find_min(root->right);
  193.         root->key = tmp->key;
  194.         /**
  195.             xoa voi tree moi, tra ve goc la root->right
  196.         */
  197.         root->right = delete_avl(root->right, tmp->key);
  198.  
  199.     } else {
  200.         /**den day la tim duoc vi tri can xoa roi
  201.             truong hop 1-3
  202.         */
  203.         tmp = root;
  204.         /**
  205.             node chi co con phai, hoac khong co con nao (leaf)
  206.         */
  207.         if(tmp->left == NULL) {
  208.             root = root->right;
  209.         } else if(tmp->right == NULL) {
  210.         /**
  211.             node chi co con trai
  212.         */
  213.             root = root->left;
  214.         }
  215.         free(tmp);
  216.     }
  217.     int heigth = height(root);
  218.     int bal = balance(root);
  219.  
  220.     if(bal > 1 && value < root->left->key) {
  221.     /**
  222.             tinh huong 1: xoay phai-lech trai
  223.     */
  224.         return rightRotate(root);
  225.     } else if ( bal < -1 && value > root->right->key) {
  226.         /**
  227.             tinh huong 2: xoay trai-lech phai
  228.     */
  229.         return leftRotate(root);
  230.     }
  231.     else if(bal > 1 && value > root->left->key) {
  232.             /**
  233.             tinh huong 3: xoay phai, xong xoay trai
  234.             cay con trai cao hon cay con phai do cay con phai cua cay con trai
  235.     */
  236.         root->left = leftRotate(root->left);
  237.         return rightRotate(root);
  238.     }
  239.     else if(bal < -1 && value < root->right->key) {
  240.             /**
  241.             tinh huong 4: xoay trai, xong xoay phai
  242.             cay con phai cao hon cay con trai do cay con trai cua cay con phai
  243.     */
  244.         root->right = rightRotate(root->right);
  245.         return leftRotate(root);
  246.     }
  247.     return root;
  248. }
  249. node_avl* delete_avl_result(node_avl *root, int value) {
  250.     if(search_(root, value)) {
  251.         return delete_avl(root, value);
  252.     } else {
  253.         printf("\nnode not exist");
  254.         return root;
  255.     }
  256. }
  257.  
  258. int main() {
  259.     node_avl *root = create_node(40);
  260.     root = insert_avl(root,30);
  261.     root = insert_avl(root,65);
  262.     root = insert_avl(root,25);
  263.     root = insert_avl(root,35);
  264.     root = insert_avl(root,50);
  265.     root = insert_avl(root,10);
  266.     root = insert_avl(root,28);
  267.     root = insert_avl(root,33);
  268.     root = insert_avl(root,34);
  269.     root = delete_avl_result(root,50);
  270.     inOrder(root);
  271.     free_tree(root);
  272.     return 0;
  273. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
key = 10    bal = 0     height = 1    
key = 25    bal = 0     height = 2    
key = 28    bal = 0     height = 1    
key = 30    bal = 1     height = 3    
key = 33    bal = 0     height = 1    
key = 34    bal = 1     height = 4    
key = 35    bal = 0     height = 1    
key = 40    bal = 0     height = 2    
key = 65    bal = 0     height = 1
https://ideone.com/PFjLwH
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!