fork 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 if (key > node->key)
  98.         node->right = insert(node->right, key);
  99.     else // Equal keys not allowed
  100.         return node;
  101.  
  102.     /* 2. Update height of this ancestor node */
  103.     node->height = 1 + max(height(node->left),
  104.                            height(node->right));
  105.  
  106.     /* 3. Get the balance factor of this ancestor
  107.           node to check whether this node became
  108.           unbalanced */
  109.     int balance = getBalance(node);
  110.  
  111.     // If this node becomes unbalanced, then there are 4 cases
  112.  
  113.     // Left Left Case
  114.     if (balance > 1 && key < node->left->key)
  115.         return rightRotate(node);
  116.  
  117.     // Right Right Case
  118.     if (balance < -1 && key > node->right->key)
  119.         return leftRotate(node);
  120.  
  121.     // Left Right Case
  122.     if (balance > 1 && key > node->left->key)
  123.     {
  124.         node->left =  leftRotate(node->left);
  125.         return rightRotate(node);
  126.     }
  127.  
  128.     // Right Left Case
  129.     if (balance < -1 && key < node->right->key)
  130.     {
  131.         node->right = rightRotate(node->right);
  132.         return leftRotate(node);
  133.     }
  134.  
  135.     /* return the (unchanged) node pointer */
  136.     return node;
  137. }
  138.  
  139. /* Given a non-empty binary search tree, return the
  140.    node with minimum key value found in that tree.
  141.    Note that the entire tree does not need to be
  142.    searched. */
  143. struct Node * minValueNode(struct Node* node)
  144. {
  145.     struct Node* current = node;
  146.  
  147.     /* loop down to find the leftmost leaf */
  148.     while (current->left != NULL)
  149.         current = current->left;
  150.  
  151.     return current;
  152. }
  153.  
  154. // Recursive function to delete a node with given key
  155. // from subtree with given root. It returns root of
  156. // the modified subtree.
  157. struct Node* deleteNode(struct Node* root, int key)
  158. {
  159.     // STEP 1: PERFORM STANDARD BST DELETE
  160.  
  161.     if (root == NULL)
  162.         return root;
  163.  
  164.     // If the key to be deleted is smaller than the
  165.     // root's key, then it lies in left subtree
  166.     if ( key < root->key )
  167.         root->left = deleteNode(root->left, key);
  168.  
  169.     // If the key to be deleted is greater than the
  170.     // root's key, then it lies in right subtree
  171.     else if( key > root->key )
  172.         root->right = deleteNode(root->right, key);
  173.  
  174.     // if key is same as root's key, then This is
  175.     // the node to be deleted
  176.     else
  177.     {
  178.         // node with only one child or no child
  179.         if( (root->left == NULL) || (root->right == NULL) )
  180.         {
  181.             struct Node *temp = root->left ? root->left :
  182.                                              root->right;
  183.  
  184.             // No child case
  185.             if (temp == NULL)
  186.             {
  187.                 temp = root;
  188.                 root = NULL;
  189.             }
  190.             else // One child case
  191.              *root = *temp; // Copy the contents of
  192.                             // the non-empty child
  193.             free(temp);
  194.         }
  195.         else
  196.         {
  197.             // node with two children: Get the inorder
  198.             // successor (smallest in the right subtree)
  199.             struct Node* temp = minValueNode(root->right);
  200.  
  201.             // Copy the inorder successor's data to this node
  202.             root->key = temp->key;
  203.  
  204.             // Delete the inorder successor
  205.             root->right = deleteNode(root->right, temp->key);
  206.         }
  207.     }
  208.  
  209.     // If the tree had only one node then return
  210.     if (root == NULL)
  211.       return root;
  212.  
  213.     // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
  214.     root->height = 1 + max(height(root->left),
  215.                            height(root->right));
  216.  
  217.     // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
  218.     // check whether this node became unbalanced)
  219.     int balance = getBalance(root);
  220.  
  221.     // If this node becomes unbalanced, then there are 4 cases
  222.  
  223.     // Left Left Case
  224.     if (balance > 1 && getBalance(root->left) >= 0)
  225.         return rightRotate(root);
  226.  
  227.     // Left Right Case
  228.     if (balance > 1 && getBalance(root->left) < 0)
  229.     {
  230.         root->left =  leftRotate(root->left);
  231.         return rightRotate(root);
  232.     }
  233.  
  234.     // Right Right Case
  235.     if (balance < -1 && getBalance(root->right) <= 0)
  236.         return leftRotate(root);
  237.  
  238.     // Right Left Case
  239.     if (balance < -1 && getBalance(root->right) > 0)
  240.     {
  241.         root->right = rightRotate(root->right);
  242.         return leftRotate(root);
  243.     }
  244.  
  245.     return root;
  246. }
  247.  
  248. int main()
  249. {
  250.   struct Node *root = NULL;
  251.  
  252.   for(int i=0; i<10000000; i++)
  253.     root = insert(root, i);
  254.  
  255.  for(int i=0; i<10000000; i++)
  256.     root = deleteNode(root, root->key);
  257.  
  258.     return 0;
  259. }
  260.  
Success #stdin #stdout 3.91s 483968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ntehnm
language:
C++ (gcc 8.3)
created:
6 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!