program-3.cpp

/* 
AVL Tree Implementation Based on Operations
*/

#include <iostream>
using namespace std;

class Node {
public:
    int key, height;
    Node *left, *right;

    Node(int k) {
        key = k;
        height = 1;
        left = right = NULL;
    }
};

class AVL {
public:
    int height(Node* n) {
        return n ? n->height : 0;
    }

    int balance(Node* n) {
        return n ? height(n->left) - height(n->right) : 0;
    }

    Node* rightRotate(Node* y) {
        Node* x = y->left;
        Node* t = x->right;

        x->right = y;
        y->left = t;

        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* t = y->left;

        y->left = x;
        x->right = t;

        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 b = balance(node);

        if (b > 1 && key < node->left->key)
            return rightRotate(node);

        if (b < -1 && key > node->right->key)
            return leftRotate(node);

        if (b > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        if (b < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    void inorder(Node* root) {
        if (root) {
            inorder(root->left);
            cout << root->key << " ";
            inorder(root->right);
        }
    }
};

int main() {
    AVL tree;
    Node* root = NULL;

    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x;
        root = tree.insert(root, x);
    }

    tree.inorder(root);

    return 0;
}