Source.cpp

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int rotations = 0;

template <typename K, typename V>
class Node {
public:
    K key;
    V value;
    Node* left;
    Node* right;
    int height;
    Node(K k, V v) : key(k), value(v), left(nullptr), right(nullptr), height(1) {};
};

template <typename K, typename V>
class Tree {
public:
    Node<K, V>* root;
    Tree() : root(nullptr) {}

    int height(Node<K, V>* node) {
        return node ? node->height : 0;
    }

    int balanceFactor(Node<K, V>* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }

    Node<K, V>* rotateRight(Node<K, V>* y) {
        if (!y || !y->left) return y;
        Node<K, V>* x = y->left;
        Node<K, V>* 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;

        rotations++;
        return x;
    }

    Node<K, V>* rotateLeft(Node<K, V>* x) {
        if (!x || !x->right) return x;
        Node<K, V>* y = x->right;
        Node<K, V>* 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;

        rotations++;
        return y;
    }

    Node<K, V>* add(Node<K, V>* node, K key, V value) {
        if (!node) return new Node<K, V>(key, value);

        if (key < node->key) {
            node->left = add(node->left, key, value);
        }
        else if (key > node->key) {
            node->right = add(node->right, key, value);
        }
        else {
            cout << "KEY ALREADY EXISTS\n";
            return node;
        }

        node->height = max(height(node->left), height(node->right)) + 1;
        int factor = balanceFactor(node);

        if (factor > 1) {
            if (key < node->left->key) {
                return rotateRight(node);
            }
            else {
                node->left = rotateLeft(node->left);
                return rotateRight(node);
            }
        }
        if (factor < -1) {
            if (key > node->right->key) {
                return rotateLeft(node);
            }
            else {
                node->right = rotateRight(node->right);
                return rotateLeft(node);
            }
        }
        return node;
    }

    Node<K, V>* successor(Node<K, V>* node) {
        if (!node || !node->right) return nullptr;
        Node<K, V>* current = node->right;
        while (current->left) current = current->left;
        return current;
    }

    Node<K, V>* remove(Node<K, V>* node, K key) {
        if (!node) {
            cout << "KEY NOT FOUND\n";
            return nullptr;
        }
        if (key < node->key)
            node->left = remove(node->left, key);
        else if (key > node->key)
            node->right = remove(node->right, key);
        else {
            if (!node->left || !node->right) {
                Node<K, V>* temp = node->left ? node->left : node->right;
                delete node;
                return temp;
            }
            else {
                Node<K, V>* temp = successor(node);
                if (temp) {
                    node->key = temp->key;
                    node->value = temp->value;
                    node->right = remove(node->right, temp->key);
                }
            }
        }
        if (!node) return node;

        node->height = max(height(node->left), height(node->right)) + 1;
        int factor = balanceFactor(node);

        if (factor > 1) {
            if (balanceFactor(node->left) >= 0) {
                return rotateRight(node);
            }
            else {
                node->left = rotateLeft(node->left);
                return rotateRight(node);
            }
        }
        if (factor < -1) {
            if (balanceFactor(node->right) <= 0) {
                return rotateLeft(node);
            }
            else {
                node->right = rotateRight(node->right);
                return rotateLeft(node);
            }
        }
        return node;
    }

    void lookup(Node<K, V>* node, K key) {
        if (!node) {
            cout << "KEY NOT FOUND\n";
            return;
        }
        if (key == node->key) {
            cout << node->value << "\n";
        }
        else if (key < node->key) {
            lookup(node->left, key);
        }
        else {
            lookup(node->right, key);
        }
    }

    void insert(K key, V value) {
        root = add(root, key, value);
    }

    void erase(K key) {
        root = remove(root, key);
    }
};

int main() {
    Tree<int, int> tree;
    int n;
    string s;
    cin >> n;
    rotations = 0;
    for (int i = 0; i < n; i++) {
        cin >> s;
        if (s == "ADD") {
            int k, v;
            cin >> k >> v;
            tree.insert(k, v);
        }
        else if (s == "LOOKUP") {
            int k;
            cin >> k;
            tree.lookup(tree.root, k);
        }
        else if (s == "DELETE") {
            int k;
            cin >> k;
            tree.erase(k);
        }
        else if (s == "PRINT_ROTATIONS") {
            cout << rotations << "\n";
        }
    }
}