#include <iostream>
#include <algorithm>
// Node structure for AVL tree
class AVLNode {
int key;
AVLNode* left;
AVLNode* right;
int height;
// Function to create a new AVL node
AVLNode(int key) {
node->key = key;
node->left = nullptr;
node->right = nullptr;
node->height = 0; // New node is initially at height 1
}
};
Class AVLTree{
AVLNode *root;
AVLTree() { root = nullptr;}
// Function to get the height of a nod
int height(AVLNode* node) {
if (node == nullptr) {
return -1;
}
return node->height; }
// Function to get the balance factor of a node
int getBalance(AVLNode* node) {
if (node == nullptr) {
return 0;
}
return height(node->left) - height(node->right);
}
// Function to rotate right
AVLNode* rightRotate(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = 1 + std::max(height(y->left), height(y->right));
x->height = 1 + std::max(height(x->left), height(x->right));
// Return new root
return x;
}
// Function to rotate left
AVLNode* leftRotate(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = 1 + std::max(height(x->left), height(x->right));
y->height = 1 + std::max(height(y->left), height(y->right));
// Return new root
return y;
}
// Function to insert a key into the AVL tree
AVLNode* insert(AVLNode* root, int key) {
// Standard BST insert
if (root == nullptr) {
AVLNode* node = new AVLNode(key);
return node;
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
} else {
// Duplicate keys are not allowed
return root;
}
// Update height of current node
root->height = 1 + std::max(height(root->left), height(root->right));
// Get the balance factor to check if this node became unbalanced
int balance = getBalance(root);
// Left Left Case
if (balance > 1 && key < root->left->key) {
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && key > root->right->key) {
return leftRotate(root);
}
// Left Right Case
if (balance > 1 && key > root->left->key) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Left Case
if (balance < -1 && key < root->right->key) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
// No rotation needed
return root;
}
// Function to print the AVL tree
void printTree(AVLNode* root, int space = 0) {
const int COUNT = 5;
if (root == nullptr) {
return;
}
space += COUNT;
// Print right child first
printTree(root->right, space);
// Print current node after space
std::cout << std::endl;
for (int i = COUNT; i < space; i++) {
std::cout << " ";
}
std::cout << root->key << "\n";
// Print left child
printTree(root->left, space);
}
