#include <iostream>
#include <algorithm>
struct Node {
int key;
Node* left;
Node* right;
int height;
};
// Function to calculate the height of a node
int getHeight(Node* node) {
if (node == nullptr)
return 0;
return node->height;
}
// Function to update the height of a node
void updateHeight(Node* node) {
node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
}
// Function to perform a right rotation
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
}
// Function to perform a left rotation
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
// Function to balance a node and update its height
Node* balance(Node* node) {
if (node == nullptr)
return node;
updateHeight(node);
int balanceFactor = getHeight(node->left) - getHeight(node->right);
// Left Heavy
if (balanceFactor > 1) {
if (getHeight(node->left->left) >= getHeight(node->left->right)) {
return rightRotate(node);
} else {
node->left = leftRotate(node->left);
return rightRotate(node);
}
}
// Right Heavy
if (balanceFactor < -1) {
if (getHeight(node->right->right) >= getHeight(node->right->left)) {
return leftRotate(node);
} else {
node->right = rightRotate(node->right);
return leftRotate(node);
}
}
return node;
}
// Function to insert a key into the AVL tree
Node* insert(Node* root, int key) {
if (root == nullptr) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = nullptr;
newNode->right = nullptr;
newNode->height = 1;
return newNode;
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
} else {
// Duplicate keys not allowed
return root;
}
return balance(root);
}
// Function to find the node with the minimum key
Node* minValueNode(Node* node) {
Node* current = node;
while (current->left != nullptr)
current = current->left;
return current;
}
// Function to delete a key from the AVL tree
Node* deleteNode(Node* root, int key) {
if (root == nullptr)
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 == nullptr || root->right == nullptr) {
Node* temp = (root->left) ? root->left : root->right;
delete root;
return temp;
}
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return balance(root);
}
// Function to print the tree in-order
void inorderTraversal(Node* root) {
if (root == nullptr)
return;
inorderTraversal(root->left);
std::cout << root->key << " ";
inorderTraversal(root->right);
}
int main() {
Node* root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
std::cout << "In-order traversal of the AVL tree: ";
inorderTraversal(root);
std::cout << std::endl;
root = deleteNode(root, 30);
std::cout << "In-order traversal after deleting 30: ";
inorderTraversal(root);
std::cout << std::endl;
return 0;
}
