Guest User

Untitled

a guest
May 1st, 2021
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // C program to insert a node in AVL tree
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4.  
  5. // An AVL tree node
  6. struct Node
  7. {
  8.     int key;
  9.     struct Node *left;
  10.     struct Node *right;
  11.     int height;
  12. };
  13.  
  14. // A utility function to get maximum of two integers
  15. int max(int a, int b);
  16.  
  17. // A utility function to get the height of the tree
  18. int height(struct Node *N)
  19. {
  20.     if (N == NULL)
  21.         return 0;
  22.     return N->height;
  23. }
  24.  
  25. // A utility function to get maximum of two integers
  26. int max(int a, int b)
  27. {
  28.     return (a > b)? a : b;
  29. }
  30.  
  31. /* Helper function that allocates a new node with the given key and
  32.     NULL left and right pointers. */
  33. struct Node* newNode(int key)
  34. {
  35.     struct Node* node = (struct Node*)
  36.                         malloc(sizeof(struct Node));
  37.     node->key   = key;
  38.     node->left   = NULL;
  39.     node->right  = NULL;
  40.     node->height = 1;  // new node is initially added at leaf
  41.     return(node);
  42. }
  43.  
  44. // A utility function to right rotate subtree rooted with y
  45. // See the diagram given above.
  46. struct Node *rightRotate(struct Node *y)
  47. {
  48.     struct Node *x = y->left;
  49.     struct Node *T2 = x->right;
  50.  
  51.     // Perform rotation
  52.     x->right = y;
  53.     y->left = T2;
  54.  
  55.     // Update heights
  56.     y->height = max(height(y->left), height(y->right))+1;
  57.     x->height = max(height(x->left), height(x->right))+1;
  58.  
  59.     // Return new root
  60.     return x;
  61. }
  62.  
  63. // A utility function to left rotate subtree rooted with x
  64. // See the diagram given above.
  65. struct Node *leftRotate(struct Node *x)
  66. {
  67.     struct Node *y = x->right;
  68.     struct Node *T2 = y->left;
  69.  
  70.     // Perform rotation
  71.     y->left = x;
  72.     x->right = T2;
  73.  
  74.     //  Update heights
  75.     x->height = max(height(x->left), height(x->right))+1;
  76.     y->height = max(height(y->left), height(y->right))+1;
  77.  
  78.     // Return new root
  79.     return y;
  80. }
  81.  
  82. // Get Balance factor of node N
  83. int getBalance(struct Node *N)
  84. {
  85.     if (N == NULL)
  86.         return 0;
  87.     return height(N->left) - height(N->right);
  88. }
  89.  
  90. // Recursive function to insert a key in the subtree rooted
  91. // with node and returns the new root of the subtree.
  92. struct Node* insert(struct Node* node, int key)
  93. {
  94.     /* 1.  Perform the normal BST insertion */
  95.     if (node == NULL)
  96.         return(newNode(key));
  97.  
  98.     if (key < node->key)
  99.         node->left  = insert(node->left, key);
  100.     else if (key > node->key)
  101.         node->right = insert(node->right, key);
  102.     else // Equal keys are not allowed in BST
  103.         return node;
  104.  
  105.     /* 2. Update height of this ancestor node */
  106.     node->height = 1 + max(height(node->left),
  107.                            height(node->right));
  108.  
  109.     /* 3. Get the balance factor of this ancestor
  110.           node to check whether this node became
  111.           unbalanced */
  112.     int balance = getBalance(node);
  113.  
  114.     // If this node becomes unbalanced, then
  115.     // there are 4 cases
  116.  
  117.     // Left Left Case
  118.     if (balance > 1 && key < node->left->key)
  119.         return rightRotate(node);
  120.  
  121.     // Right Right Case
  122.     if (balance < -1 && key > node->right->key)
  123.         return leftRotate(node);
  124.  
  125.     // Left Right Case
  126.     if (balance > 1 && key > node->left->key)
  127.     {
  128.         node->left =  leftRotate(node->left);
  129.         return rightRotate(node);
  130.     }
  131.  
  132.     // Right Left Case
  133.     if (balance < -1 && key < node->right->key)
  134.     {
  135.         node->right = rightRotate(node->right);
  136.         return leftRotate(node);
  137.     }
  138.  
  139.     /* return the (unchanged) node pointer */
  140.     return node;
  141. }
  142.  
  143. // A utility function to print preorder traversal
  144. // of the tree.
  145. // The function also prints height of every node
  146. void preOrder(struct Node *root)
  147. {
  148.     if(root != NULL)
  149.     {
  150.         printf("%d ", root->key);
  151.         preOrder(root->left);
  152.         preOrder(root->right);
  153.     }
  154. }
  155.  
  156. /* Driver program to test above function*/
  157. int main()
  158. {
  159.   struct Node *root = NULL;
  160.  
  161.   /* Constructing tree given in the above figure */
  162.   root = insert(root, 10);
  163.   root = insert(root, 20);
  164.   root = insert(root, 30);
  165.   root = insert(root, 40);
  166.   root = insert(root, 50);
  167.   root = insert(root, 25);
  168.  
  169.   /* The constructed AVL Tree would be
  170.             30
  171.            /  \
  172.          20   40
  173.         /  \     \
  174.        10  25    50
  175.   */
  176.  
  177.   printf("Preorder traversal of the constructed AVL"
  178.          " tree is \n");
  179.   preOrder(root);
  180.  
  181.   return 0;
  182. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×