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
  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. // A utility function to print preorder traversal of the tree.
  136. // The function also prints height of every node
  137. void preOrder(struct node *root)
  138. {
  139.     if(root != NULL)
  140.     {
  141.         printf("%d ", root->key);
  142.         preOrder(root->left);
  143.         preOrder(root->right);
  144.     }
  145. }
  146.  
  147. /* Drier program to test above function*/
  148. int main()
  149. {
  150.   struct node *root = NULL;
  151.  
  152.   /* Constructing tree given in the above figure */
  153.   root = insert(root, 10);
  154.   root = insert(root, 20);
  155.   root = insert(root, 30);
  156.   root = insert(root, 40);
  157.   root = insert(root, 50);
  158.   root = insert(root, 25);
  159.  
  160.   /* The constructed AVL Tree would be
  161.             30
  162.            /  \
  163.          20   40
  164.         /  \     \
  165.        10  25    50
  166.   */
  167.  
  168.   printf("Pre order traversal of the constructed AVL tree is \n");
  169.   preOrder(root);
  170.  
  171.   return 0;
  172. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pre order traversal of the constructed AVL tree is 
30 20 10 25 40 50
https://ideone.com/jd3ljs
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!