#include <stdio.

h> y->height = max(height(y->left), height(y->right)) +

#include <stdlib.h> 1;

struct Node return y;

{ }
int key;
struct Node *left; int getBalance(struct Node *N)
struct Node *right; {
int height; if (N == NULL)
}; return 0;

int height(struct Node *N) return height(N->left) - height(N->right);

{ }
if (N == NULL)
return 0; struct Node *insert(struct Node *node, int key)
return N->height; {
} if (node == NULL)
return newNode(key);
int max(int a, int b)
{ if (key < node->key)
return (a > b) ? a : b; node->left = insert(node->left, key);
} else if (key > node->key)
node->right = insert(node->right, key);
struct Node *newNode(int key) else
{ return node;
struct Node *node = (struct Node
*)malloc(sizeof(struct Node)); node->height = 1 + max(height(node->left),
height(node->right));
node->key = key;
node->left = NULL; int balance = getBalance(node);
node->right = NULL;
node->height = 1; // LL Case
return node; if (balance > 1 && key < node->left->key)
} return rightRotate(node);

struct Node *rightRotate(struct Node *y) // RR Case

{ if (balance < -1 && key > node->right->key)
struct Node *x = y->left; return leftRotate(node);
struct Node *T2 = x->right;
x->right = y; // LR Case
y->left = T2; if (balance > 1 && key > node->left->key)
y->height = max(height(y->left), height(y->right)) + {
1; node->left = leftRotate(node->left);
x->height = max(height(x->left), height(x->right)) + 1; return rightRotate(node);
return x; }
}
// RL Case
struct Node *leftRotate(struct Node *x) if (balance < -1 && key < node->right->key)
{ {
struct Node *y = x->right; node->right = rightRotate(node->right);
struct Node *T2 = y->left; return leftRotate(node);
}
y->left = x;
x->right = T2; return node;
}
x->height = max(height(x->left), height(x->right)) + 1;
struct Node *minValueNode(struct Node *node)
{ if (root == NULL)
struct Node *current = node; return root;

while (current->left != NULL) root->height = 1 + max(height(root->left),

current = current->left; height(root->right));

return current; int balance = getBalance(root);

}
// LL Case
struct Node *deleteNode(struct Node *root, int key) if (balance > 1 && getBalance(root->left) >= 0)
{ return rightRotate(root);
if (root == NULL)
return root; // LR Case
if (balance > 1 && getBalance(root->left) < 0)
if (key < root->key) {
root->left = deleteNode(root->left, key); root->left = leftRotate(root->left);
return rightRotate(root);
else if (key > root->key) }
root->right = deleteNode(root->right, key);
// RR Case
else if (balance < -1 && getBalance(root->right) <= 0)
{ return leftRotate(root);
// Node with one child or no child
if ((root->left == NULL) || (root->right == NULL)) // RL Case
{ if (balance < -1 && getBalance(root->right) > 0)
struct Node *temp; {
root->right = rightRotate(root->right);
if (root->left != NULL) return leftRotate(root);
temp = root->left; }
else
temp = root->right; return root;
}
if (temp == NULL)
{ void inOrder(struct Node *root, FILE *fp)
temp = root; {
root = NULL; if (root != NULL)
} {
else inOrder(root->left, fp);
{ fprintf(fp, "%d ", root->key);
*root = *temp; inOrder(root->right, fp);
} }
}
free(temp);
} struct Node *constructAVLFromFile(const char
else *filename)
{ {
// Node with two children FILE *fp = fopen(filename, "r");
struct Node *temp = minValueNode(root-
>right); if (fp == NULL)
{
root->key = temp->key; printf("Error opening file %s\n", filename);
return NULL;
root->right = deleteNode(root->right, temp- }
>key);
} struct Node *root = NULL;
} int key;
 while (fscanf(fp, "%d", &key) != EOF) printf("\n");
{
root = insert(root, key); FILE *fp = fopen(outputFile, "w");
}
if (fp == NULL)
fclose(fp); {
printf("Error opening file %s\n", outputFile);
return root; return 1;
} }

void freeTree(struct Node *root) inOrder(root, fp);

{
if (root == NULL) fclose(fp);
return;
printf("AVL Tree operations completed successfully.\
freeTree(root->left); n");
freeTree(root->right); printf("Result written to %s\n", outputFile);
free(root);
} freeTree(root);
void printTree(struct Node *root, int space)
{ return 0;
int i; }

if (root == NULL)
return;

space = space + 5;

printTree(root->right, space);

printf("\n");

for(i = 5; i < space; i++)

printf(" ");

printf("%d\n", root->key);

printTree(root->left, space);
}

int main()
{
const char *inputFile = "[Link]";
const char *outputFile = "[Link]";

struct Node *root =

constructAVLFromFile(inputFile);

root = insert(root, 25);

root = deleteNode(root, 10);

printf("\n\nAVL Tree Structure:\n");

printTree(root,0);

printf("\n\nInorder Traversal: ");

inOrder(root, stdout);