• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# AVL.CPP

a guest Oct 21st, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include "AVL.h"
2. #include <iostream>
3. using namespace std;
4. int iq = 0;
5. int max(int a, int b)
6. {
7.     return (a > b ? a : b);
8. }
9.
10. //calculates the longest path from a current node to a leaf
11. int maxPathLength(NodeAVL* node)
12. {
13.     if (node == NULL)
14.         return 0;
15.     return (max(maxPathLength(node->right), maxPathLength(node->left)) + 1);
16. }
17.
18. //calculates the balance indicator of each node of the tree
19. void computeBalanceFactor(NodeAVL* node)
20. {
21.     int maxLeft = 0, maxRight = 0;
22.
23.     if (node->left != NULL)
24.         maxLeft = maxPathLength(node->left);
25.     else
26.         maxLeft = 0;
27.
28.     if (node->right != NULL)
29.         maxRight = maxPathLength(node->right);
30.     else
31.         maxRight = 0;
32.
33.     node->echi = maxRight - maxLeft;
34. }
35.
36. //simple left rotation
37. NodeAVL* leftRotation(NodeAVL* root, NodeAVL* node) //p is critical node
38. {
39.     NodeAVL* heavyChild;
40.
41.     heavyChild = node->right;
42.     node->right = heavyChild->left;
43.     heavyChild->left = node;
44.
45.     computeBalanceFactor(node);
46.     computeBalanceFactor(heavyChild);
47.
48.     node = heavyChild;
49.     cout << "Rotation number " << ++iq << endl;
50.     displayAVLTree(root, 10);
51.     return node;
52. }
53.
54. //simple right rotation
55. NodeAVL* rightRotation(NodeAVL* root, NodeAVL* node)
56. {
57.     NodeAVL* heavyChild;
58.
59.     heavyChild = node->left;
60.     node->left = heavyChild->right;
61.     heavyChild->right = node;
62.
63.     computeBalanceFactor(node);
64.     computeBalanceFactor(heavyChild);
65.
66.     node = heavyChild;
67.     cout << "Rotation number " << ++iq << endl;
68.     displayAVLTree(root, 10);
69.     return node;
70. }
71.
72. //double left rotation
73. NodeAVL* doubleLeftRotation(NodeAVL* root, NodeAVL* node)
74. {
75.     node->right = rightRotation(root, node->right);
76.     node = leftRotation(root, node);
77.     cout << "Rotation number " << ++iq << endl;
78.     displayAVLTree(root, 10);
79.     return node;
80. }
81.
82. //double right rotation
83. NodeAVL* doubleRightRotation(NodeAVL* root, NodeAVL* node)
84. {
85.     node->left = leftRotation(root, node->left);
86.     node = rightRotation(root, node);
87.     cout << "Rotation number " << ++iq << endl;
88.     displayAVLTree(root, 10);
89.     return node;
90. }
91.
92. //tree balancing function
93. NodeAVL* balance(NodeAVL* root, NodeAVL* node)
94. {
95.     NodeAVL* heavyChild;
96.
97.     computeBalanceFactor(node);
98.
99.     if (node->echi == -2)   // if p is a critical junction (LEFT hanging)
100.     {
101.         heavyChild = node->left;    // heavyChild - left child of p
102.
103.         if (heavyChild->echi == 1)
104.             node = doubleRightRotation(root, node);
105.         else
106.             node = rightRotation(root, node);
107.     }
108.     else
109.         if (node->echi == 2)        // // if p is a critical junction (RIGHT hanging)
110.         {
111.             heavyChild = node->right;   // heavyChild - right child of p
112.
113.             if (heavyChild->echi == -1)
114.                 node = doubleLeftRotation(root, node);
115.             else
116.                 node = leftRotation(root, node);
117.         }
118.
119.     return node;
120. }
121.
122. //function for inserting a node
123. NodeAVL* insertAVLNode(NodeAVL* root, NodeAVL* node, int value)
124. {
125.     if (node == NULL)
126.     {
127.         node = new NodeAVL;
128.         node->key = value;
129.         node->echi = 0;
130.         node->left = NULL;
131.         node->right = NULL;
132.         return node;
133.     }
134.     else
135.         if (value < node->key)
136.             node->left = insertAVLNode(root, node->left, value);
137.         else
138.             if (value > node->key)
139.                 node->right = insertAVLNode(root, node->right, value);
140.             else
141.                 printf("The key %d already exists! \n", value);
142.
143.     node = balance(root, node);
144.
145.     return node;
146. }
147.
148. //printing function
149. void displayAVLTree(NodeAVL* node, int level)
150. {
151.     if (node != NULL)
152.     {
153.         displayAVLTree(node->right, level + 7);
154.         for (int i = 0; i < level; i++)
155.             printf(" ");
156.
157.         printf("%d(%d) \n", node->key, node->echi);
158.         displayAVLTree(node->left, level + 7);
159.     }
160. }
161.
162. //function for deleting a node
163. NodeAVL* deleteAVLNode(NodeAVL* root, NodeAVL* node, int value)
164. {
165.     if (node == NULL)
166.     {
167.         printf("Can't delete key %d, it is not in AVL tree!\n", value);
168.         return node;
169.     }
170.
171.     if (value < node->key)
172.         node->left = deleteAVLNode(root, node->left, value);
173.
174.     else if (value > node->key)
175.         node->right = deleteAVLNode(root, node->right, value);
176.
177.     else
178.     {
179.         // node with only one child or no child
180.         if ((node->left == NULL) || (node->right == NULL))
181.         {
182.             NodeAVL* temp;
183.
184.             if (node->left != NULL)
185.                 temp = node->left;
186.             else
187.                 temp = node->right;
188.
189.             // No child case
190.             if (temp == NULL)
191.                 node = NULL;
192.
193.             else // One child case
194.             {
195.                 *node = *temp;
196.                 free(temp);
197.             }
198.         }
199.         else
200.         {
201.             // node with two children: Get the inorder successor
202.             // (smallest in the right subtree)
203.             NodeAVL* temp = node->right;
204.
205.             while (temp->left != NULL)
206.                 temp = temp->left;
207.
208.             // Copy the inorder successor's data to this node
209.             node->key = temp->key;
210.
211.             // Delete the inorder successor
212.             node->right = deleteAVLNode(root, node->right, temp->key);
213.         }
214.     }
215.
216.     // If the tree had only one node then return
217.     if (node != NULL)
218.         node = balance(root, node);
219.
220.     return node;
221. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?