#include <iostream>
using namespace std;
class Node {
public:
int key, height;
Node* left;
Node* right;
Node(int k) {
key = k;
height = 1;
left = nullptr;
right = nullptr;
}
};
class AVLTree {
public:
Node* root;
AVLTree() : root(nullptr) {}
int height(Node* n) {
return n ? n->height : 0;
}
int getBalance(Node* n) {
return n ? height(n->left) - height(n->right) : 0;
}
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;
}
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;
}
Node* insert(Node* node, int key) {
if (!node) return new Node(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);
if (balance > 1 && key < node->left->key) return rightRotate(node);
if (balance < -1 && key > node->right->key) return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current->left) current = current->left;
return current;
}
Node* deleteNode(Node* root, int key) {
if (!root) 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 || !root->right) {
Node* temp = root->left ? root->left : root->right;
if (!temp) {
temp = root;
root = nullptr;
} else *root = *temp;
delete temp;
} else {
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (!root) return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
if (balance > 1) {
if (getBalance(root->left) >= 0) return rightRotate(root);
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1) {
if (getBalance(root->right) <= 0) return leftRotate(root);
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
};
int main() {
AVLTree tree;
[Link] = [Link]([Link], 10);
[Link] = [Link]([Link], 20);
[Link] = [Link]([Link], 30);
[Link] = [Link]([Link], 40);
[Link] = [Link]([Link], 50);
[Link] = [Link]([Link], 25);
cout << "Inorder traversal of the AVL tree is: ";
[Link]([Link]);
cout << endl;
[Link] = [Link]([Link], 20);
cout << "Inorder traversal after deleting 20: ";
[Link]([Link]);
cout << endl;
return 0;
}