#include <iostream>

#include <string>
using namespace std;

// AVL Node definition

class AVLnode {
public:
string cWord; // Word stored in the node
string cMean; // Meaning of the word
AVLnode *left, *right; // Left and right child pointers
int iHt; // Height of the node
};

// AVL Tree class definition

class AVLtree {
public:
AVLnode *Root; // Root of the AVL tree
AVLtree () {
Root = NULL; // Initializing the root to NULL
}
// Function declarations for AVL tree operations
AVLnode* insert (AVLnode*, string, string);
AVLnode* deletE (AVLnode*, string);
AVLnode* LL (AVLnode*);
AVLnode* RR (AVLnode*);
AVLnode* LR (AVLnode*);
AVLnode* RL (AVLnode*);
int height (AVLnode*);
int bFactor (AVLnode*);
void inOrder (AVLnode*);
void preOrder (AVLnode*);
};

// Insert a node in the AVL tree

AVLnode* AVLtree::insert (AVLnode *root, string nWord, string nMean) {
if (root == NULL) { // If the root is null, create a new node
root = new AVLnode;
root -> left = root -> right = NULL;
root -> cWord = nWord; // Set the word
root -> cMean = nMean; // Set the meaning
root -> iHt = 0; // Set height to 0 as it's a leaf node
}
else if (root -> cWord != nWord) { // If word is not equal, continue inserting
 if (root -> cWord > nWord)
root -> left = insert (root -> left, nWord, nMean); // Insert in left subtree
else
root -> right = insert (root -> right, nWord, nMean); // Insert in right subtree
}
else {
cout << "\nRedundant AVLnode\n"; // If word already exists, it's a duplicate
}

// Update the height of the current node

root -> iHt = max(height(root -> left), height(root -> right)) + 1;

// Perform balancing if the node has become unbalanced

if (bFactor (root) == 2) { // Left heavy
if (root -> left -> cWord > nWord)
root = RR (root); // Right rotation
else
root = LR (root); // Left-Right rotation
}

if (bFactor (root) == -2) { // Right heavy

if (root -> right -> cWord > nWord)
root = RL (root); // Right-Left rotation
else
root = LL (root); // Left rotation
}

return root; // Return the root of the subtree

}

// Delete a node from the AVL tree

AVLnode *AVLtree::deletE (AVLnode *curr, string x) {
AVLnode *temp;
if (curr == NULL) {
cout << "\nWord not present!\n"; // If word is not found
return curr;
}

else if (x > curr -> cWord) // If the word to be deleted is greater, search in the right subtree
curr -> right = deletE (curr -> right, x);

else if (x < curr -> cWord) // If the word to be deleted is smaller, search in the left subtree
curr -> left = deletE (curr -> left, x);
 else if (curr -> right == NULL || curr -> left == NULL) { // Node has one or no child
curr = curr -> left ? curr -> left : curr -> right; // Replace current node with its non-null child
cout << "\nWord deleted Successfully!\n";
}

else { // Node has two children

temp = curr -> right;
while (temp -> left) // Find the inorder successor (smallest in the right subtree)
temp = temp -> left;
curr -> cWord = temp -> cWord; // Replace current node with successor
curr -> right = deletE (curr -> right, temp -> cWord); // Delete the successor
}

if (curr == NULL) return curr; // If the tree is empty, return null

// Update height after deletion

curr -> iHt = max(height(curr -> left), height(curr -> right)) + 1;

// Balance the tree if it is unbalanced

if (bFactor (curr) == 2) { // Left heavy
if (bFactor (curr -> left) >= 0)
curr = RR (curr); // Right rotation
else
curr = LR (curr); // Left-Right rotation
}

if (bFactor (curr) == -2) { // Right heavy

if (bFactor (curr -> right) <= 0)
curr = LL (curr); // Left rotation
else
curr = RL (curr); // Right-Left rotation
}

return curr; // Return the root of the subtree

}

// Get the height of a node

int AVLtree::height (AVLnode* curr) {
if (curr == NULL)
return -1; // Height of NULL node is -1
else
return curr -> iHt; // Return height of current node
}

// Get the balance factor of a node

int AVLtree::bFactor (AVLnode* curr) {
int lh = 0, rh = 0;
if (curr == NULL)
return 0; // Balance factor of NULL node is 0
else
return height(curr -> left) - height(curr -> right); // Balance factor: Left height - Right height
}

// Right rotation
AVLnode* AVLtree::RR (AVLnode* curr) {
AVLnode* temp = curr -> left; // Save the left child
curr -> left = temp -> right; // Move the left child's right subtree to the left of the current node
temp -> right = curr; // Move the current node to the right of the left child
curr -> iHt = max(height(curr -> left), height(curr -> right)) + 1; // Update the height of the current
node
temp -> iHt = max(height(temp -> left), height(temp -> right)) + 1; // Update the height of the temp
node
return temp; // Return the new root of the subtree
}

// Left rotation
AVLnode* AVLtree::LL (AVLnode* curr) {
AVLnode* temp = curr -> right; // Save the right child
curr -> right = temp -> left; // Move the right child's left subtree to the right of the current node
temp -> left = curr; // Move the current node to the left of the right child
curr -> iHt = max(height(curr -> left), height(curr -> right)) + 1; // Update the height of the current
node
temp -> iHt = max(height(temp -> left), height(temp -> right)) + 1; // Update the height of the temp
node
return temp; // Return the new root of the subtree
}

// Right-Left rotation
AVLnode* AVLtree::RL (AVLnode* curr) {
curr -> right = RR (curr -> right); // Perform right rotation on right child
return LL (curr); // Perform left rotation on current node
}

// Left-Right rotation
AVLnode* AVLtree::LR (AVLnode* curr) {
 curr -> left = LL (curr -> left); // Perform left rotation on left child
return RR (curr); // Perform right rotation on current node
}

// Inorder Traversal (Left, Root, Right)

void AVLtree::inOrder (AVLnode* curr) {
if (curr != NULL) {
inOrder (curr -> left); // Visit left subtree
cout << "\n\t" << curr -> cWord << "\t" << curr -> cMean; // Print the word and meaning
inOrder (curr -> right); // Visit right subtree
}
}

// Preorder Traversal (Root, Left, Right)

void AVLtree::preOrder (AVLnode* curr) {
if (curr != NULL) {
cout << "\n\t" << curr -> cWord << "\t" << curr -> cMean; // Print the word and meaning
preOrder (curr -> left); // Visit left subtree
preOrder (curr -> right); // Visit right subtree
}
}

// Main function to test AVL tree operations

int main () {
int ch;
AVLtree avl; // Create an AVL tree object
AVLnode *temp = NULL;
string word; // Word to be inserted or deleted
string mean; // Meaning of the word

cout << "\n--------------------------------------";

cout << "\n\tAVL TREE IMPLEMENTATION";
cout << "\n--------------------------------------";
do {
cout << "\n\t\tMENU";
cout << "\n1.Insert 2.Inorder 3.Delete 4.Exit";
cout << "\n--------------------------------";
cout << "\nEnter your choice: ";
cin >> ch; // User's choice

switch (ch) {
case 1:
cout << "\nEnter Word: ";
 cin >> word; // Input word
cout << "\nEnter Meaning: ";
cin >> mean; // Input meaning
avl.Root = avl.insert (avl.Root, word, mean); // Insert the word in the AVL tree
break;
case 2:
cout << "\nInorder Traversal:\n\tWORD\tMEANING";
avl.inOrder (avl.Root); // Display the inorder traversal
cout << "\n\nPreorder Traversal:\n\tWORD\tMEANING";
avl.preOrder (avl.Root); // Display the preorder traversal
cout << '\n';
break;
case 3:
cout << "\nEnter the word to be deleted : ";
cin >> word; // Input word to delete
avl.Root = avl.deletE (avl.Root, word); // Delete the word from the AVL tree
break;
case 4:
exit (0); // Exit the program
break;
}
} while (ch != 4); // Repeat until user chooses to exit

return 0;
}