#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
// Structure of AVL Tree Node
struct Node
{
int key;
Node *left;
Node *right;
int height;
};
// Function to get height
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// Return maximum of two numbers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Create a new node
Node *newNode(int key)
{
Node *node = new Node;
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
// Right Rotation
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
// Left Rotation
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
// Balance Factor
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Insert a node
Node *insert(Node *node, int key)
{
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// Left Left
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// Find minimum value node
Node *minValueNode(Node *node)
{
Node *current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// Delete a node
Node *deleteNode(Node *root, int key)
{
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else
{
if ((root->left == NULL) || (root->right == NULL))
{
Node *temp = root->left ? root->left : root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
delete temp;
}
else
{
Node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
// Left Left
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right
if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left
if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// Inorder Traversal
void inorder(Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
// Write inorder traversal into output file
void writeToFile(Node *root, ofstream &fout)
{
if (root != NULL)
{
writeToFile(root->left, fout);
fout << root->key << " ";
writeToFile(root->right, fout);
}
}
int main()
{
Node *root = NULL;
ifstream fin("[Link]");
int value;
// Read elements from file
while (fin >> value)
{
root = insert(root, value);
}
[Link]();
cout << "AVL Tree (Inorder): ";
inorder(root);
int insertValue, deleteValue;
cout << "\n\nEnter element to insert: ";
cin >> insertValue;
root = insert(root, insertValue);
cout << "After Insertion: ";
inorder(root);
cout << "\n\nEnter element to delete: ";
cin >> deleteValue;
root = deleteNode(root, deleteValue);
cout << "After Deletion: ";
inorder(root);
ofstream fout("[Link]");
writeToFile(root, fout);
[Link]();
cout << "\n\nFinal inorder traversal written to [Link]";
return 0;
}