fork download
  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
stdin
Standard input is empty
stdout
Pre order traversal of the constructed AVL tree is 
30 20 10 25 40 50