-
Notifications
You must be signed in to change notification settings - Fork 0
/
PartII_B_AVL.cpp
407 lines (325 loc) · 10.5 KB
/
PartII_B_AVL.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
/******************************************************************
* PART II.B: Binary Search Tree by Volume implemented as AVL tree *
******************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
struct dateVolume // Data record stored in binary tree node
{
char Date[11];
int Volume;
};
typedef struct dateVolume dataItem;
struct binaryTreeNode // Binary Search Tree node implemented as AVL tree node
{
dataItem data;
struct binaryTreeNode *left;
struct binaryTreeNode *right;
int height;
};
typedef struct binaryTreeNode btNode;
btNode *root = NULL; // Root of the tree initially empty
// Declaration of functions
void binaryTreeByVolumeMenu(int argc, char *argv[]);
void readFileToBinTree(int argc, char *argv[]);
btNode *createbtNode(dataItem x);
int btNodeHeight(btNode *r);
int btNodeBalance(btNode *r);
btNode *rotateL(btNode *r);
btNode *rotateR(btNode *r);
btNode *insertToBinTree(btNode *r, dataItem x);
void reportBinTree(btNode *r, int x);
btNode *minValuebtNode(btNode *r);
btNode *maxValuebtNode(btNode *r);
int max(int a, int b);
void inorderBinTree(btNode *r);
void printBinTree(btNode *r, int k);
int cmpVolumeDate(dataItem a, dataItem b);
int main(int argc, char *argv[])
{
binaryTreeByVolumeMenu(argc, argv);
return 0;
}
// Binary tree by Volume menu: Read file by Volume and display user menu
void binaryTreeByVolumeMenu(int argc, char *argv[])
{
readFileToBinTree(argc, argv);
int selection, v;
while (1)
{
printf("1. Find date(s) with MIN volume");
printf("\n2. Find date(s) with MAX volume\n");
printf("\nEnter your choice (1 - 2): ");
scanf("%d",&selection);
switch (selection)
{
case 1 :
/* // This code is used for verification: Display tree nodes info in inorder and the tree structure
printf("\n\nDate Volume\tHeight\tBalance\n");
printf("---------------------------------------");
inorderBinTree(root);
printf("\n\n");system("pause");
printf("\n\n\nTree structure:\n");
printf("---------------\n\n");
printBinTree(root, 1);
printf("\n\n"); */
if (!root)
printf("\n\nTree is empty\n\n");
else
{
v = minValuebtNode(root)->data.Volume;
printf("\nDates with MIN volume: ");
reportBinTree(root, v);
printf("\nMIN volume: %d\n", v);
}
return;
case 2 :
if (!root)
printf("\n\nTree is empty\n\n");
else
{
v = maxValuebtNode(root)->data.Volume;
printf("\nDates with MAX volume: ");
reportBinTree(root, v);
printf("\nMAX volume: %d\n", v);
}
return;
default :
printf("\nWrong option, try again ...\n\n\n");
break;
}
}
}
// Open the file, read data records and store them to a binary tree implemented as an AVL tree
void readFileToBinTree(int argc, char *argv[])
{
FILE *fp;
char *fileName;
char line[80];
dataItem dt;
float a, b, c, d;
int e;
if (argc >= 2) // Data filename passed as a command line argument
fileName = strdup(argv[1]);
else
{
printf("Give the stock data filename: "); // Data filename asked by user
scanf("%ms", &fileName);
printf("\n\n");
}
// Check if the file exists
if (access(fileName, F_OK) == -1)
{
printf("\nERROR: File '%s' not found\n", fileName);
free(fileName);
exit(1);
}
fp = fopen(fileName, "r");
if (!fp) // fp == NULL
{
printf("\nERROR: can't open file\n");
free(fileName);
exit(1);
}
fgets(line, 80, fp); // Get the first line
while (fgets(line, 80, fp))
{
sscanf(line, "%10s,%f,%f,%f,%f,%d,%d", dt.Date, &a, &b, &c, &d, &dt.Volume, &e); // a, b, c, d and e are dummy variables
root = insertToBinTree(root, dt);
root->height = btNodeHeight(root); // Update height of root node
}
free(fileName);
fclose(fp);
}
// Allocate memory to a new tree node n and set left and right pointers to NULL and height to 0
btNode *createbtNode(dataItem x)
{
btNode *n = (btNode *) malloc(sizeof(btNode));
if (!n)
{
printf("\nERROR: Memory failure\n\n");
exit (1);
}
n->data = x;
n->left = n->right = NULL;
n->height = 0;
return n;
}
// Inorder traversal of the tree rooted at r
void inorderBinTree(btNode *r)
{
if (r)
{
inorderBinTree(r->left);
printf("\n%s %d\t%d\t%d", r->data.Date, r->data.Volume, r->height, btNodeBalance(r));
inorderBinTree(r->right);
}
}
// Rotate right subtree rooted at T1
btNode *rotateR(btNode *T1)
{
btNode *T2 = T1->left;
btNode *T3 = T2->right;
// Perform rotation
T2->right = T1;
T1->left = T3;
// Update heights
T1->height = btNodeHeight(T1);
T2->height = btNodeHeight(T2);
// Return new root
return T2;
}
// Rotate left subtree rooted at T1
btNode *rotateL(btNode *T1)
{
btNode *T2 = T1->right;
btNode *T3 = T2->left;
// Perform rotation
T2->left = T1;
T1->right = T3;
// Update heights
T1->height = btNodeHeight(T1);
T2->height = btNodeHeight(T2);
// Return new root
return T2;
}
// Get balance of node r
int btNodeBalance(btNode *r)
{
if (!r)
return 0;
return btNodeHeight(r->left) - btNodeHeight(r->right);
}
// Recursive function to insert a data record x in the subtree rooted at r. It returns the new root of the subtree
btNode *insertToBinTree(btNode *r, dataItem x)
{
// 1. Perform the standard insertion to binary tree
if (!r)
return createbtNode(x);
if (cmpVolumeDate(x, r->data) < 0) // The key of each data record is the pair (Volume, Date)
r->left = insertToBinTree(r->left, x); // Insert x to r's left subtree
else if (strcmp(x.Date, r->data.Date) > 0)
r->right = insertToBinTree(r->right, x); // Insert x to r's right subtree
else
return r; // Duplicates are not allowed in an AVL tree. Actually, as the Date value of each data record is unique, we have no duplicates
// 2. Update height of ancestor node r
r->height = btNodeHeight(r);
// 3. Get balance of ancestor node r to check whether the node became unbalanced
int balance = btNodeBalance(r);
// If the node becomes unbalanced, then there are 4 Cases
// Left Left Case - Right rotation
if (balance > 1 && cmpVolumeDate(x, r->left->data) < 0)
return rotateR(r);
// Right Left Case - Double rotation: Rotate right and then rotate left
if (balance < -1 && cmpVolumeDate(x, r->right->data) < 0)
{
r->right = rotateR(r->right);
return rotateL(r);
}
// Left Right Case - Double rotation: Rotate left and then rotate right
if (balance > 1 && cmpVolumeDate(x, r->left->data) > 0)
{
r->left = rotateL(r->left);
return rotateR(r);
}
// Right Right Case - Left rotation
if (balance < -1 && cmpVolumeDate(x, r->right->data) > 0)
return rotateL(r);
// Return the (unchanged) node pointer if node stays balanced
return r;
}
// Report the date(s) with Volume value == x
void reportBinTree(btNode *r, int x)
{
if (r)
{
if (r->data.Volume == x) // x can be stored in many tree nodes
{
printf("%s ", r->data.Date);
reportBinTree(r->left, x);
reportBinTree(r->right, x);
}
else if (x < r->data.Volume)
reportBinTree(r->left, x);
else
reportBinTree(r->right, x);
}
}
// Print tree structure
void printBinTree(btNode *r, int k)
{
if (r)
{
printBinTree(r->right, k+1);
for (int i = 0; i < k; i++)
printf(" ");
printf("%d (%d)\n", r->data.Volume, btNodeBalance(r));
printBinTree(r->left, k+1);
}
}
// Utility function
int max(int a, int b)
{
return a >= b ? a : b;
}
// Compute the height of the tree rooted at r from height info stored in the roots of left and right subtrees
int btNodeHeight(btNode *r)
{
if (!r)
return -1;
if (r->left == r->right) // A leaf
return 0;
if (r->left && !r->right) // r has only left son
return 1 + r->left->height;
if (!r->left && r->right) // r has only right son
return 1 + r->right->height;
return 1 + max(r->left->height, r->right->height); // r has two sons
}
// Given a non-empty binary tree rooted at r, return the node with minimum value stored in the tree
btNode *minValuebtNode(btNode *r)
{
btNode *p = r;
// Loop down to find the leftmost node
while (p->left)
p = p->left;
return p;
}
/* // Given a non-empty binary tree rooted at r, return the node with minimum value stored in the tree
btNode *minValuebtNode(btNode *r)
{
if (r->left)
return minValuebtNode(r->left);
else
return r;
} */
// Given a non-empty binary tree rooted at r, return the node with maximun value stored in the tree
btNode *maxValuebtNode(btNode *r)
{
btNode *p = r;
// Loop down to find the rightmost node
while (p->right)
p = p->right;
return p;
}
/* // Given a non-empty binary tree rooted at r, return the node with maximum value stored in the tree
btNode *maxValuebtNode(btNode *r)
{
if (r->right)
return maxValuebtNode(r->right);
else
return r;
} */
// Compare pairs (Date, Volume)
int cmpVolumeDate(dataItem a, dataItem b)
{
if (a.Volume > b.Volume)
return 1;
if (a.Volume < b.Volume)
return -1;
if (strcmp(a.Date, b.Date) > 0)
return 1;
if (strcmp(a.Date, b.Date) < 0)
return -1;
return 0;
}