1.
/*
2. * AVL Tree Program in C
3. */
4.
5. #include<stdio.h>
6. #include<stdlib.h>
7.
8. // structure of the tree node
9. struct node
10. {
11. int data;
12. struct node* left;
13. struct node* right;
14. int ht;
15. };
16.
17. // global initialization of root node
18. struct node* root = NULL;
19.
20. // function prototyping
21. struct node* create(int);
22. struct node* insert(struct node*, int);
23. struct node* delete(struct node*, int);
24. struct node* search(struct node*, int);
25. struct node* rotate_left(struct node*);
26. struct node* rotate_right(struct node*);
27. int balance_factor(struct node*);
28. int height(struct node*);
29. void inorder(struct node*);
30. void preorder(struct node*);
31. void postorder(struct node*);
32.
33. int main()
34. {
35. int user_choice, data;
36. char user_continue = 'y';
37. struct node* result = NULL;
38.
39. while (user_continue == 'y' || user_continue == 'Y')
40. {
41. printf("\n\n------- AVL TREE --------\n");
42. printf("\n1. Insert");
43. printf("\n2. Delete");
44. printf("\n3. Search");
45. printf("\n4. Inorder");
46. printf("\n5. Preorder");
47. printf("\n6. Postorder");
48. printf("\n7. EXIT");
49.
50. printf("\n\nEnter Your Choice: ");
51. scanf("%d", &user_choice);
52.
53. switch(user_choice)
54. {
55. case 1:
56. printf("\nEnter data: ");
57. scanf("%d", &data);
58. root = insert(root, data);
59. break;
60.
61. case 2:
62. printf("\nEnter data: ");
63. scanf("%d", &data);
64. root = delete(root, data);
65. break;
66.
67. case 3:
68. printf("\nEnter data: ");
69. scanf("%d", &data);
70. result = search(root, data);
71. if (result == NULL)
72. {
73. printf("\nNode not found!");
74. }
75. else
76. {
77. printf("\n Node found");
78. }
79. break;
80. case 4:
81. inorder(root);
82. break;
83.
84. case 5:
85. preorder(root);
86. break;
87.
88. case 6:
89. postorder(root);
90. break;
91.
92. case 7:
93. printf("\n\tProgram Terminated\n");
94. return 1;
95.
96. default:
97. printf("\n\tInvalid Choice\n");
98. }
99.
100. printf("\n\nDo you want to continue? ");
101. scanf(" %c", &user_continue);
102. }
103.
104. return 0;
105. }
106.
107. // creates a new tree node
108. struct node* create(int data)
109. {
110. struct node* new_node = (struct node*) malloc
(sizeof(struct node));
111.
112. // if a memory error has occurred
113. if (new_node == NULL)
114. {
115. printf("\nMemory can't be allocated\n");
116. return NULL;
117. }
118. new_node->data = data;
119. new_node->left = NULL;
120. new_node->right = NULL;
121. return new_node;
122. }
123.
124. // rotates to the left
125. struct node* rotate_left(struct node* root)
126. {
127. struct node* right_child = root->right;
128. root->right = right_child->left;
129. right_child->left = root;
130.
131. // update the heights of the nodes
132. root->ht = height(root);
133. right_child->ht = height(right_child);
134.
135. // return the new node after rotation
136. return right_child;
137. }
138.
139. // rotates to the right
140. struct node* rotate_right(struct node* root)
141. {
142. struct node* left_child = root->left;
143. root->left = left_child->right;
144. left_child->right = root;
145.
146. // update the heights of the nodes
147. root->ht = height(root);
148. left_child->ht = height(left_child);
149.
150. // return the new node after rotation
151. return left_child;
152. }
153.
154. // calculates the balance factor of a node
155. int balance_factor(struct node* root)
156. {
157. int lh, rh;
158. if (root == NULL)
159. return 0;
160. if (root->left == NULL)
161. lh = 0;
162. else
163. lh = 1 + root->left->ht;
164. if (root->right == NULL)
165. rh = 0;
166. else
167. rh = 1 + root->right->ht;
168. return lh - rh;
169. }
170.
171. // calculate the height of the node
172. int height(struct node* root)
173. {
174. int lh, rh;
175. if (root == NULL)
176. {
177. return 0;
178. }
179. if (root->left == NULL)
180. lh = 0;
181. else
182. lh = 1 + root->left->ht;
183. if (root->right == NULL)
184. rh = 0;
185. else
186. rh = 1 + root->right->ht;
187.
188. if (lh > rh)
189. return (lh);
190. return (rh);
191. }
192.
193. // inserts a new node in the AVL tree
194. struct node* insert(struct node* root, int data)
195. {
196. if (root == NULL)
197. {
198. struct node* new_node = create(data);
199. if (new_node == NULL)
200. {
201. return NULL;
202. }
203. root = new_node;
204. }
205. else if (data > root->data)
206. {
207. // insert the new node to the right
208. root->right = insert(root->right, data);
209.
210. // tree is unbalanced, then rotate it
211. if (balance_factor(root) == -2)
212. {
213. if (data > root->right->data)
214. {
215. root = rotate_left(root);
216. }
217. else
218. {
219. root->right = rotate_right(root->right);
220. root = rotate_left(root);
221. }
222. }
223. }
224. else
225. {
226. // insert the new node to the left
227. root->left = insert(root->left, data);
228.
229. // tree is unbalanced, then rotate it
230. if (balance_factor(root) == 2)
231. {
232. if (data < root->left->data)
233. {
234. root = rotate_right(root);
235. }
236. else
237. {
238. root->left = rotate_left(root->left);
239. root = rotate_right(root);
240. }
241. }
242. }
243. // update the heights of the nodes
244. root->ht = height(root);
245. return root;
246. }
247.
248. // deletes a node from the AVL tree
249. struct node * delete(struct node *root, int x)
250. {
251. struct node * temp = NULL;
252.
253. if (root == NULL)
254. {
255. return NULL;
256. }
257.
258. if (x > root->data)
259. {
260. root->right = delete(root->right, x);
261. if (balance_factor(root) == 2)
262. {
263. if (balance_factor(root->left) >= 0)
264. {
265. root = rotate_right(root);
266. }
267. else
268. {
269. root->left = rotate_left(root->left);
270. root = rotate_right(root);
271. }
272. }
273. }
274. else if (x < root->data)
275. {
276. root->left = delete(root->left, x);
277. if (balance_factor(root) == -2)
278. {
279. if (balance_factor(root->right) <= 0)
280. {
281. root = rotate_left(root);
282. }
283. else
284. {
285. root->right = rotate_right(root->right);
286. root = rotate_left(root);
287. }
288. }
289. }
290. else
291. {
292. if (root->right != NULL)
293. {
294. temp = root->right;
295. while (temp->left != NULL)
296. temp = temp->left;
297.
298. root->data = temp->data;
299. root->right = delete(root->right, temp->data);
300. if (balance_factor(root) == 2)
301. {
302. if (balance_factor(root->left) >= 0)
303. {
304. root = rotate_right(root);
305. }
306. else
307. {
308. root->left = rotate_left(root->left);
309. root = rotate_right(root);
310. }
311. }
312. }
313. else
314. {
315. return (root->left);
316. }
317. }
318. root->ht = height(root);
319. return (root);
320. }
321.
322. // search a node in the AVL tree
323. struct node* search(struct node* root, int key)
324. {
325. if (root == NULL)
326. {
327. return NULL;
328. }
329.
330. if(root->data == key)
331. {
332. return root;
333. }
334.
335. if(key > root->data)
336. {
337. search(root->right, key);
338. }
339. else
340. {
341. search(root->left, key);
342. }
343. }
344.
345. // inorder traversal of the tree
346. void inorder(struct node* root)
347. {
348. if (root == NULL)
349. {
350. return;
351. }
352.
353. inorder(root->left);
354. printf("%d ", root->data);
355. inorder(root->right);
356. }
357.
358. // preorder traversal of the tree
359. void preorder(struct node* root)
360. {
361. if (root == NULL)
362. {
363. return;
364. }
365.
366. printf("%d ", root->data);
367. preorder(root->left);
368. preorder(root->right);
369. }
370.
371. // postorder traversal of the tree
372. void postorder(struct node* root)
373. {
374. if (root == NULL)
375. {
376. return;
377. }
378.
379. postorder(root->left);
380. postorder(root->right);
381. printf("%d ", root->data);
382. }
Program Explanation
The AVL tree is an extension to the binary search tree in which it is
required to balance the height difference between the left and right
subtree of a node. We can balance the height of the tree by rotations.
Let’s understand the main operations of the AVL Tree with the examples
and also discuss their time and space complexities.
Insert a Node in AVL Tree
On Inserting a new node into the AVL Tree it is necessary to maintain the
balance factor of the tree. To insert a new node into the AVL tree, we have
to follow the given steps:
1. Insert a new element in the tree with the same binary search tree
logic.
2. Check the balance factor for each node.
3. If the balanced factor is not -1 or 0 or +1 of any node then do the
proper rotations else terminate.
Example: We are constructing the AVL Tree by inserting the following
values.
10 15 20 9 5 16 17 8 6
Step 1: Insert a new node 10
Step 2: Insert a new node 15
Step 3: Insert a new node 20
Step 4: Insert a new node 9
Step 5: Insert a new node 5
Step 6: Insert a new node 16
Step 7: Insert a new node 17
Step 8: Insert a new node 8
Step 9: Insert a new node 6
Time Complexity: O(log n)
Time complexity of an AVL tree is O(log n). Inserting any node in the AVL
tree takes logarithmic time because each call skips half the tree to
determine the correct position to insert a node.
Space Complexity: O(n)
The space complexity of an avl tree is O(n), because the function calling
stack eventually exceeds the number of nodes in the tree.
Run Time Testcases
In this case, we are inserting the nodes into AVL tree and finding
traversals.
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 34
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 78
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
34 78 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 5
78 34 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 6
34 99 78
Do you want to continue? n
Delete a Node from AVL Tree
Deletion of a node is similar to that of deleting a node in the binary search
tree. In AVL Tree, after deleting the node we have to maintain the
balanced factor again. We need to follow the given steps to delete a node
in AVL Tree:
1. Search the element in the tree
2. Delete the node
3. There are two cases that are possible after deletion
Deleting from the right subtree
Deleting from the left subtree
Case 1: Deleting a Node from the Right Subtree
There are three subcases that are discussed below:
a) Perform LL rotation when after deletion of a node the balance factor of
a node changes to +2 and the balance factor of its left child is +1.
b) Perform LL rotation when after deletion of a node the balance factor of
a node changes to +2 and the balance factor of its left child is 0.
c) Perform LR rotation when after deletion of a node the balance factor of
a node changes to +2 and the balance factor of its left child is -1.
Case 2: Deleting a Node from the Left Subtree
There are three subcases that are discussed below:
a) Perform RR rotation when after deletion of a node the balance factor of
a node changes to -2 and the balance factor of its left child is -1.
b) Perform RR rotation when after deletion of a node the balance factor of
a node changes to -2 and the balance factor of its left child is 0.
c) Perform RL rotation when after deletion of a node the balance factor of
a node changes to -2 and the balance factor of its left child is 1.
Time Complexity: O(log n)
To delete a node from the AVL tree, it takes logarithmic time to find and
delete the given node i.e O(log n).
Space Complexity: O(n)
It takes n function calls for deletion and rebuilding the node from the AVL
tree.
Run Time Testcases
In this case, we are deleting the nodes from the AVL tree.
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 34
Enter Your Choice: 1
Enter data: 78
Enter Your Choice: 1
Enter data: 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
34 78 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 2
Enter data: 78
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
34 99
Searching a Node in AVL Tree
Searching a node in an AVL tree is a similar process that we do in a binary
search Tree. Follow the given steps to search a node in AVL Tree.
1. Start comparing the key with the root node of the tree.
2. If the key is greater than the node value then move to the right
subtree.
3. If the key is less than the node value then move to the left subtree.
4. Repeat the process until the key is not found.
Time Complexity: O(log n)
It takes logarithmic time to search any node in the AVL tree.
Space Complexity: O(h)
There are h function calls required to find the node in the AVL tree, where
h is the height of the AVL tree.
Run Time Testcases
In this case, we are searching the node in the AVL tree.
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 1
Enter data: 34
Enter Your Choice: 1
Enter data: 78
Enter Your Choice: 1
Enter data: 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 4
34 78 99
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 3
Enter data: 99
Node found
Do you want to continue? y
------- AVL TREE --------
1. Insert
2. Delete
3. Search
4. Inorder
5. Preorder
6. Postorder
7. EXIT
Enter Your Choice: 3
Enter data: 66
Node not found!
Do you want to continue? n
