Untitled

include <iostream>
using namespace std;
 
class Node
{
public:
    int data;
    Node* left;
    Node* right;
    int height;
 
    Node(int value)
    {
        data = value;
        left = NULL;
        right = NULL;
        height = 1;  
    }
};
 
class AVL
{
    Node* root;
 
    int height(Node* node) {
        if (node == NULL) {
            return 0;
        }
        return node->height;
    }
 
    int getBalance(Node* node) {
        if (node == NULL) {
            return 0;
        }
        return height(node->left) - height(node->right);
    }
 
    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 value) {
        if (node == NULL) {
            return new Node(value);
        }
 
        if (value < node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        } else {
            return node;
        }
 
        node->height = 1 + max(height(node->left), height(node->right));
 
        int balance = getBalance(node);
 
        if (balance > 1 && value < node->left->data) {
            return rightRotate(node);
        }
 
        if (balance < -1 && value > node->right->data) {
            return leftRotate(node);
        }
 
        if (balance > 1 && value > node->left->data) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
 
        if (balance < -1 && value < node->right->data) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
 
        return node;
    }
 
    void inorder(Node* root) {
        if (root != NULL) {
            inorder(root->left);
            cout << root->data << " ";
            inorder(root->right);
        }
    }
 
    void preorder(Node* root) {
        if (root != NULL) {
            cout << root->data << " ";
            preorder(root->left);
            preorder(root->right);
        }
    }
 
    void postorder(Node* root) {
        if (root != NULL) {
            postorder(root->left);
            postorder(root->right);
            cout << root->data << " ";
        }
    }
 
public:
    AVL() {
        root = NULL;
    }
 
    void insert(int value) {
        root = insert(root, value);
    }
 
    void inorder() {
        inorder(root);
        cout << endl;
    }
 
    void preorder() {
        preorder(root);
        cout << endl;
    }
 
    void postorder() {
        postorder(root);
        cout << endl;
    }
};
 
int main() {
    AVL tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);
    tree.insert(60);
    tree.insert(70);
 
    tree.inorder();
    tree.preorder();
    tree.postorder();
 
    return 0;
}