AVL-tree + K-order statistic

/*
 * Дано число N и N строк.
 * Каждая строка содержащит команду добавления или удаления натуральных чисел, а также запрос на получение k-ой порядковой
 * статистики. Команда добавления числа A задается положительным числом A, команда удаления числа A задается отрицательным
 * числом “-A”. Запрос на получение k-ой порядковой статистики задается числом k. Требуемая скорость выполнения запроса -
 * O(log n).
*/
#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int key = 0;
    int height = 0;
    int size = 0;
    Node* left = nullptr;
    Node* right = nullptr;

    Node() = default;

    Node(int _key, int _height, int _size) : key(_key), height(_height), size(_size) {}

    ~Node() {
        delete left;
        delete right;
    }
};

class AVL {
public:
    AVL() = default;

    ~AVL();

    bool IsEmpty() { return root == nullptr; }

    Node* Insert(Node* node, int key);

    void Insert(int key) { root = Insert(root, key); }

    Node* Remove(Node* node, int key);

    void Remove(int key) { root = Remove(root, key); }

    int FindStat(int k) { return FindStat(root, k); }

private:
    Node* root = nullptr;

    Node* FindMin(Node* node) const { return node->left != nullptr ? FindMin(node->left) : node; }

    Node* RemoveMin(Node* node);

    int GetHeight(Node* node) const;

    int GetSize(Node* node) const;

    int BalanceDif(Node* node) const;

    void UpdSize(Node* node);

    void UpdHeight(Node* node);

    Node* RotateLeft(Node* node);

    Node* RotateRight(Node* node);

    Node* Balance(Node* node);

    int FindStat(Node* node, int k);
};

AVL::~AVL() {
    delete root;
}

int AVL::GetHeight(Node* node) const {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

int AVL::GetSize(Node* node) const {
    if (node == nullptr) {
        return 0;
    }
    return node->size;
}

int AVL::BalanceDif(Node* node) const {
    if (node == nullptr) {
        return 0;
    }
    return GetHeight(node->right) - GetHeight(node->left);
}

void AVL::UpdHeight(Node* node) {
    if (node == nullptr) {
        return;
    }
    int heightLeft = GetHeight(node->left);
    int heightRight = GetHeight(node->right);
    node->height = max(heightLeft, heightRight) + 1;
}

void AVL::UpdSize(Node* node) {
    if (node == nullptr) {
        return;
    }
    int sizeLeft = GetSize(node->left);
    int sizeRight = GetSize(node->right);
    node->size = sizeLeft + sizeRight + 1;
}

Node* AVL::RotateLeft(Node* node) {
    Node*_node = node->right;
    node->right = _node->left;
    _node->left = node;

    UpdHeight(node);
    UpdHeight(_node);
    UpdSize(node);
    UpdSize(_node);

    return _node;
}

Node* AVL::RotateRight(Node* node) {
    Node* _node = node->left;
    node->left = _node->right;
    _node->right = node;

    UpdHeight(node);
    UpdHeight(_node);
    UpdSize(node);
    UpdSize(_node);

    return _node;
}

Node* AVL::Balance(Node* node) {
    UpdHeight(node);
    UpdSize(node);

    if (BalanceDif(node) == 2) {
        if (BalanceDif(node->right) < 0) {
            node->right = RotateRight(node->right);
        }
        return RotateLeft(node);
    } else if (BalanceDif(node) == -2) {
        if (BalanceDif(node->left) > 0){
            node->left = RotateLeft(node->left);
        }
        return RotateRight(node);
    }
    return node;
}

Node* AVL::RemoveMin(Node* node) {
    if (node->left == nullptr) {
        return node->right;
    }
    node->left = RemoveMin(node->left);
    return Balance(node);
}

Node* AVL::Insert(Node* node, int key) {
    if (node == nullptr) {
        return new Node(key, 1, 1);
    } else if (key < node->key) {
        node->left = Insert(node->left, key);
    } else {
        node->right = Insert(node->right, key);
    }
    return Balance(node);
}

Node* AVL::Remove(Node* node, int key) {
    if (node == nullptr) {
        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->right == nullptr) {
            return node->left;
        }
        if (node->left == nullptr) {
            return node->right;
        }
        Node* _node = node;
        node = FindMin(_node->right);
        node->right = RemoveMin(_node->right);
        node->left = _node->left;
        return Balance(node);
    }
    return Balance(node);
}

int AVL::FindStat(Node* node, int k) {
    if (GetSize(node->left) + 1 == k) {
        return node->key;
    } else if (GetSize(node->left) >= k) {
        return FindStat(node->left, k);
    } else {
        return FindStat(node->right, k - (GetSize(node->left) + 1));
    }
}

int main() {
    int n;
    AVL tree;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a, k;
        cin >> a >> k;
        if (a > 0) {
            tree.Insert(a);
        } else {
            tree.Remove(abs(a));
        }
        cout << tree.FindStat(k + 1) << endl;
    }
    return 0;
}