C++ Program to Perform Left and Right Rotation on AVL Tree

«
»
This is a C++ Program to perform Left Rotation in Binary Search Trees. In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root’s place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.

Here is source code of the C++ Program to Perform Left Rotation on a Binary Search Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include<iostream>`
2. `#include<cstdio>`
3. `#include<sstream>`
4. `#include<algorithm>`
5. `#define pow2(n) (1 << (n))`
6. `using namespace std;`
7. `/*`
8. ` * Node Declaration`
9. ` */`
10. `struct avl_node`
11. `{`
12. `        int data;`
13. `        struct avl_node *left;`
14. `        struct avl_node *right;`
15. `}*root;`
16. `/*`
17. ` * Class Declaration`
18. ` */`
19. `class avlTree`
20. `{`
21. `    public:`
22. `        int height(avl_node *);`
23. `        int diff(avl_node *);`
24. `        avl_node *rr_rotation(avl_node *);`
25. `        avl_node *ll_rotation(avl_node *);`
26. `        avl_node *lr_rotation(avl_node *);`
27. `        avl_node *rl_rotation(avl_node *);`
28. `        avl_node* balance(avl_node *);`
29. `        avl_node* insert(avl_node *, int);`
30. `        void display(avl_node *, int);`
31. `        void inorder(avl_node *);`
32. `        void preorder(avl_node *);`
33. `        void postorder(avl_node *);`
34. `        avlTree()`
35. `        {`
36. `            root = NULL;`
37. `        }`
38. `};`
39. `/*`
40. ` * Main Contains Menu`
41. ` */`
42. `int main()`
43. `{`
44. `    int choice, item;`
45. `    avlTree avl;`
46. `    while (1)`
47. `    {`
48. `        cout << "\n---------------------" << endl;`
49. `        cout << "AVL Tree Implementation" << endl;`
50. `        cout << "\n---------------------" << endl;`
51. `        cout << "1.Insert Element into the tree" << endl;`
52. `        cout << "2.Display Balanced AVL Tree" << endl;`
53. `        cout << "3.InOrder traversal" << endl;`
54. `        cout << "4.PreOrder traversal" << endl;`
55. `        cout << "5.PostOrder traversal" << endl;`
56. `        cout << "6.Exit" << endl;`
57. `        cout << "Enter your Choice: ";`
58. `        cin >> choice;`
59. `        switch (choice)`
60. `        {`
61. `            case 1:`
62. `                cout << "Enter value to be inserted: ";`
63. `                cin >> item;`
64. `                root = avl.insert(root, item);`
65. `                break;`
66. `            case 2:`
67. `                if (root == NULL)`
68. `                {`
69. `                    cout << "Tree is Empty" << endl;`
70. `                    continue;`
71. `                }`
72. `                cout << "Balanced AVL Tree:" << endl;`
73. `                avl.display(root, 1);`
74. `                break;`
75. `            case 3:`
76. `                cout << "Inorder Traversal:" << endl;`
77. `                avl.inorder(root);`
78. `                cout << endl;`
79. `                break;`
80. `            case 4:`
81. `                cout << "Preorder Traversal:" << endl;`
82. `                avl.preorder(root);`
83. `                cout << endl;`
84. `                break;`
85. `            case 5:`
86. `                cout << "Postorder Traversal:" << endl;`
87. `                avl.postorder(root);`
88. `                cout << endl;`
89. `                break;`
90. `            case 6:`
91. `                exit(1);`
92. `                break;`
93. `            default:`
94. `                cout << "Wrong Choice" << endl;`
95. `        }`
96. `    }`
97. `    return 0;`
98. `}`
99. `/*`
100. ` * Height of AVL Tree`
101. ` */`
102. `int avlTree::height(avl_node *temp)`
103. `{`
104. `    int h = 0;`
105. `    if (temp != NULL)`
106. `    {`
107. `        int l_height = height(temp->left);`
108. `        int r_height = height(temp->right);`
109. `        int max_height = max(l_height, r_height);`
110. `        h = max_height + 1;`
111. `    }`
112. `    return h;`
113. `}`
114. `/*`
115. ` * Height Difference`
116. ` */`
117. `int avlTree::diff(avl_node *temp)`
118. `{`
119. `    int l_height = height(temp->left);`
120. `    int r_height = height(temp->right);`
121. `    int b_factor = l_height - r_height;`
122. `    return b_factor;`
123. `}`
124. `/*`
125. ` * Right- Right Rotation`
126. ` */`
127. `avl_node *avlTree::rr_rotation(avl_node *parent)`
128. `{`
129. `    avl_node *temp;`
130. `    temp = parent->right;`
131. `    parent->right = temp->left;`
132. `    temp->left = parent;`
133. `    return temp;`
134. `}`
135. `/*`
136. ` * Left- Left Rotation`
137. ` */`
138. `avl_node *avlTree::ll_rotation(avl_node *parent)`
139. `{`
140. `    avl_node *temp;`
141. `    temp = parent->left;`
142. `    parent->left = temp->right;`
143. `    temp->right = parent;`
144. `    return temp;`
145. `}`
146. `/*`
147. ` * Left - Right Rotation`
148. ` */`
149. `avl_node *avlTree::lr_rotation(avl_node *parent)`
150. `{`
151. `    avl_node *temp;`
152. `    temp = parent->left;`
153. `    parent->left = rr_rotation(temp);`
154. `    return ll_rotation(parent);`
155. `}`
156. `/*`
157. ` * Right- Left Rotation`
158. ` */`
159. `avl_node *avlTree::rl_rotation(avl_node *parent)`
160. `{`
161. `    avl_node *temp;`
162. `    temp = parent->right;`
163. `    parent->right = ll_rotation(temp);`
164. `    return rr_rotation(parent);`
165. `}`
166. `/*`
167. ` * Balancing AVL Tree`
168. ` */`
169. `avl_node *avlTree::balance(avl_node *temp)`
170. `{`
171. `    int bal_factor = diff(temp);`
172. `    if (bal_factor > 1)`
173. `    {`
174. `        if (diff(temp->left) > 0)`
175. `            temp = ll_rotation(temp);`
176. `        else`
177. `            temp = lr_rotation(temp);`
178. `    }`
179. `    else if (bal_factor < -1)`
180. `    {`
181. `        if (diff(temp->right) > 0)`
182. `            temp = rl_rotation(temp);`
183. `        else`
184. `            temp = rr_rotation(temp);`
185. `    }`
186. `    return temp;`
187. `}`
188. `/*`
189. ` * Insert Element into the tree`
190. ` */`
191. `avl_node *avlTree::insert(avl_node *root, int value)`
192. `{`
193. `    if (root == NULL)`
194. `    {`
195. `        root = new avl_node;`
196. `        root->data = value;`
197. `        root->left = NULL;`
198. `        root->right = NULL;`
199. `        return root;`
200. `    }`
201. `    else if (value < root->data)`
202. `    {`
203. `        root->left = insert(root->left, value);`
204. `        root = balance(root);`
205. `    }`
206. `    else if (value >= root->data)`
207. `    {`
208. `        root->right = insert(root->right, value);`
209. `        root = balance(root);`
210. `    }`
211. `    return root;`
212. `}`
213. `/*`
214. ` * Display AVL Tree`
215. ` */`
216. `void avlTree::display(avl_node *ptr, int level)`
217. `{`
218. `    int i;`
219. `    if (ptr != NULL)`
220. `    {`
221. `        display(ptr->right, level + 1);`
222. `        printf("\n");`
223. `        if (ptr == root)`
224. `            cout << "Root -> ";`
225. `        for (i = 0; i < level && ptr != root; i++)`
226. `            cout << "        ";`
227. `        cout << ptr->data;`
228. `        display(ptr->left, level + 1);`
229. `    }`
230. `}`
231. `/*`
232. ` * Inorder Traversal of AVL Tree`
233. ` */`
234. `void avlTree::inorder(avl_node *tree)`
235. `{`
236. `    if (tree == NULL)`
237. `        return;`
238. `    inorder(tree->left);`
239. `    cout << tree->data << "  ";`
240. `    inorder(tree->right);`
241. `}`
242. `/*`
243. ` * Preorder Traversal of AVL Tree`
244. ` */`
245. `void avlTree::preorder(avl_node *tree)`
246. `{`
247. `    if (tree == NULL)`
248. `        return;`
249. `    cout << tree->data << "  ";`
250. `    preorder(tree->left);`
251. `    preorder(tree->right);`
252. `}/*`
253. ` * Postorder Traversal of AVL Tree`
254. ` */`
255. `void avlTree::postorder(avl_node *tree)`
256. `{`
257. `    if (tree == NULL)`
258. `        return;`
259. `    postorder(tree ->left);`
260. `    postorder(tree ->right);`
261. `    cout << tree->data << "  ";`
262. `}`

Output:

```\$ g++ ALVLeftRotation.cpp
\$ a.out

AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Tree is Empty

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 8

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

Root -> 8
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 5

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

Root -> 8
5
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 4

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

8
Root -> 5
4
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 11

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

11
8
Root -> 5
4
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 15

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

15
11
8
Root -> 5
4
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 3

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

15
11
8
Root -> 5
4
3
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 6

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

15
11
8
6
Root -> 5
4
3
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Enter value to be inserted: 2

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

15
11
8
6
Root -> 5
4
3
2
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Preorder Traversal:
5  3  2  4  11  8  6  15

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Postorder Traversal:
2  4  3  6  8  15  11  5

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Inorder Traversal:
2  3  4  5  6  8  11  15

---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit
Balanced AVL Tree:

15
11
8
6
Root -> 5
4
3
2
---------------------
AVL Tree Implementation

---------------------
1.Insert Element into the tree
2.Display Balanced AVL Tree
3.InOrder traversal
4.PreOrder traversal
5.PostOrder traversal
6.Exit

------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!