fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. // An AVL tree node
  5. struct node
  6. {
  7.     int key;
  8.     struct node *left;
  9.     struct node *right;
  10.     int height;
  11. };
  12.  
  13. // A utility function to get maximum of two integers
  14. int max(int a, int b);
  15.  
  16. // A utility function to get height of the tree
  17. int height(struct node *N)
  18. {
  19.     if (N == NULL)
  20.         return 0;
  21.     return N->height;
  22. }
  23.  
  24. // A utility function to get maximum of two integers
  25. int max(int a, int b)
  26. {
  27.     return (a > b)? a : b;
  28. }
  29.  
  30. /* Helper function that allocates a new node with the given key and
  31.     NULL left and right pointers. */
  32. struct node* newNode(int key)
  33. {
  34.     struct node* node = (struct node*)
  35.                         malloc(sizeof(struct node));
  36.     node->key   = key;
  37.     node->left   = NULL;
  38.     node->right  = NULL;
  39.     node->height = 1;  // new node is initially added at leaf
  40.     return(node);
  41. }
  42.  
  43. // A utility function to right rotate subtree rooted with y
  44. // See the diagram given above.
  45. struct node *rightRotate(struct node *y)
  46. {
  47.     struct node *x = y->left;
  48.     struct node *T2 = x->right;
  49.  
  50.     // Perform rotation
  51.     x->right = y;
  52.     y->left = T2;
  53.  
  54.     // Update heights
  55.     y->height = max(height(y->left), height(y->right))+1;
  56.     x->height = max(height(x->left), height(x->right))+1;
  57.  
  58.     // Return new root
  59.     return x;
  60. }
  61.  
  62. // A utility function to left rotate subtree rooted with x
  63. // See the diagram given above.
  64. struct node *leftRotate(struct node *x)
  65. {
  66.     struct node *y = x->right;
  67.     struct node *T2 = y->left;
  68.  
  69.     // Perform rotation
  70.     y->left = x;
  71.     x->right = T2;
  72.  
  73.     //  Update heights
  74.     x->height = max(height(x->left), height(x->right))+1;
  75.     y->height = max(height(y->left), height(y->right))+1;
  76.  
  77.     // Return new root
  78.     return y;
  79. }
  80.  
  81. // Get Balance factor of node N
  82. int getBalance(struct node *N)
  83. {
  84.     if (N == NULL)
  85.         return 0;
  86.     return height(N->left) - height(N->right);
  87. }
  88.  
  89. struct node* insert(struct node* node, int key)
  90. {
  91.     /* 1.  Perform the normal BST rotation */
  92.     if (node == NULL)
  93.         return(newNode(key));
  94.  
  95.     if (key < node->key)
  96.         node->left  = insert(node->left, key);
  97.     else
  98.         node->right = insert(node->right, key);
  99.  
  100.     /* 2. Update height of this ancestor node */
  101.     node->height = max(height(node->left), height(node->right)) + 1;
  102.  
  103.     /* 3. Get the balance factor of this ancestor node to check whether
  104.        this node became unbalanced */
  105.     int balance = getBalance(node);
  106.  
  107.     // If this node becomes unbalanced, then there are 4 cases
  108.  
  109.     // Left Left Case
  110.     if (balance > 1 && key < node->left->key)
  111.         return rightRotate(node);
  112.  
  113.     // Right Right Case
  114.     if (balance < -1 && key > node->right->key)
  115.         return leftRotate(node);
  116.  
  117.     // Left Right Case
  118.     if (balance > 1 && key > node->left->key)
  119.     {
  120.         node->left =  leftRotate(node->left);
  121.         return rightRotate(node);
  122.     }
  123.  
  124.     // Right Left Case
  125.     if (balance < -1 && key < node->right->key)
  126.     {
  127.         node->right = rightRotate(node->right);
  128.         return leftRotate(node);
  129.     }
  130.  
  131.     /* return the (unchanged) node pointer */
  132.     return node;
  133. }
  134.  
  135. /* Given a non-empty binary search tree, return the node with minimum
  136.    key value found in that tree. Note that the entire tree does not
  137.    need to be searched. */
  138. struct node * minValueNode(struct node* node)
  139. {
  140.     struct node* current = node;
  141.  
  142.     /* loop down to find the leftmost leaf */
  143.     while (current->left != NULL)
  144.         current = current->left;
  145.  
  146.     return current;
  147. }
  148.  
  149. struct node* deleteNode(struct node* root, int key)
  150. {
  151.     // STEP 1: PERFORM STANDARD BST DELETE
  152.  
  153.     if (root == NULL)
  154.         return root;
  155.  
  156.     // If the key to be deleted is smaller than the root's key,
  157.     // then it lies in left subtree
  158.     if ( key < root->key )
  159.         root->left = deleteNode(root->left, key);
  160.  
  161.     // If the key to be deleted is greater than the root's key,
  162.     // then it lies in right subtree
  163.     else if( key > root->key )
  164.         root->right = deleteNode(root->right, key);
  165.  
  166.     // if key is same as root's key, then This is the node
  167.     // to be deleted
  168.     else
  169.     {
  170.         // node with only one child or no child
  171.         if( (root->left == NULL) || (root->right == NULL) )
  172.         {
  173.             struct node *temp = root->left ? root->left : root->right;
  174.  
  175.             // No child case
  176.             if(temp == NULL)
  177.             {
  178.                 temp = root;
  179.                 root = NULL;
  180.             }
  181.             else // One child case
  182.              *root = *temp; // Copy the contents of the non-empty child
  183.  
  184.             free(temp);
  185.         }
  186.         else
  187.         {
  188.             // node with two children: Get the inorder successor (smallest
  189.             // in the right subtree)
  190.             struct node* temp = minValueNode(root->right);
  191.  
  192.             // Copy the inorder successor's data to this node
  193.             root->key = temp->key;
  194.  
  195.             // Delete the inorder successor
  196.             root->right = deleteNode(root->right, temp->key);
  197.         }
  198.     }
  199.  
  200.     // If the tree had only one node then return
  201.     if (root == NULL)
  202.       return root;
  203.  
  204.     // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
  205.     root->height = max(height(root->left), height(root->right)) + 1;
  206.  
  207.     // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
  208.     //  this node became unbalanced)
  209.     int balance = getBalance(root);
  210.  
  211.     // If this node becomes unbalanced, then there are 4 cases
  212.  
  213.     // Left Left Case
  214.     if (balance > 1 && getBalance(root->left) >= 0)
  215.         return rightRotate(root);
  216.  
  217.     // Left Right Case
  218.     if (balance > 1 && getBalance(root->left) < 0)
  219.     {
  220.         root->left =  leftRotate(root->left);
  221.         return rightRotate(root);
  222.     }
  223.  
  224.     // Right Right Case
  225.     if (balance < -1 && getBalance(root->right) <= 0)
  226.         return leftRotate(root);
  227.  
  228.     // Right Left Case
  229.     if (balance < -1 && getBalance(root->right) > 0)
  230.     {
  231.         root->right = rightRotate(root->right);
  232.         return leftRotate(root);
  233.     }
  234.  
  235.     return root;
  236. }
  237.  
  238. // A utility function to print preorder traversal of the tree.
  239. // The function also prints height of every node
  240. void preOrder(struct node *root)
  241. {
  242.     if(root != NULL)
  243.     {
  244.         printf("%d ", root->key);
  245.         preOrder(root->left);
  246.         preOrder(root->right);
  247.     }
  248. }
  249.  
  250. /* Drier program to test above function*/
  251. int main()
  252. {
  253.   struct node *root = NULL;
  254.  
  255.   /* Constructing tree given in the above figure */
  256.     root = insert(root, 9);
  257.     root = insert(root, 5);
  258.     root = insert(root, 10);
  259.     root = insert(root, 0);
  260.     root = insert(root, 6);
  261.     root = insert(root, 11);
  262.     root = insert(root, -1);
  263.     root = insert(root, 1);
  264.     root = insert(root, 2);
  265.  
  266.     /* The constructed AVL Tree would be
  267.             9
  268.            /  \
  269.           1    10
  270.         /  \     \
  271.        0    5     11
  272.       /    /  \
  273.      -1   2    6
  274.     */
  275.  
  276.     printf("Pre order traversal of the constructed AVL tree is \n");
  277.     preOrder(root);
  278.  
  279.     root = deleteNode(root, 10);
  280.  
  281.     /* The AVL Tree after deletion of 10
  282.             1
  283.            /  \
  284.           0    9
  285.         /     /  \
  286.        -1    5     11
  287.            /  \
  288.           2    6
  289.     */
  290.  
  291.     printf("\nPre order traversal after deletion of 10 \n");
  292.     preOrder(root);
  293.  
  294.     return 0;
  295. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pre order traversal of the constructed AVL tree is 
9 1 0 -1 5 2 6 10 11 
Pre order traversal after deletion of 10 
1 0 -1 9 5 2 6 11
https://ideone.com/lbWsmS
language:
C++ (gcc 8.3)
created:
8 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!