# 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