// проверять именно это решение тут источники:
// https://www.geeksforgeeks.org/find-closest-element-binary-search-tree/
// https://habr.com/ru/post/150732/

#include <iostream>

struct Node {
    int value;
    Node *left;
    Node *right;
    int height;

    explicit Node(int value) : value(value) {
        left = right = nullptr;
        height = 1;
    }
};

class AVLTree {
public:
    AVLTree() {
        root_ = nullptr;
    }

    int getHeight() {
        return getHeight(root_);
    }

    void insert(int value) {
        root_ = insertInto(root_, value);
    }

    void erase(int value) {
        root_ = remove(root_, value);
    }

    int *find(int value) {
        return find(root_, value);
    }

    int *traversal() {
        size_ = 0;
        size_t size = getSize(root_);
        data_ = new int[size];
        traversal(root_);
        return data_;
    }

    int *lowerBound(int value) {
        int min_diff = 10000000, min_diff_key = -1;
        lowerBound(root_, value, min_diff, min_diff_key);
        return find(min_diff_key);
    }

    bool empty() {
        return root_ == nullptr;
    }

    Node *getRoot() {
        return root_;
    }

    int getSize() {
        return getSize(root_);
    }

    void print() {
        print(root_);
    }

    ~AVLTree() {
        clear(root_);
    }

private:
    Node *root_ = nullptr;
    int *data_;
    size_t size_;

    int *find(Node *node, int value) {
        if (node != nullptr) {
            if (value < node->value) {
                return find(node->left, value);
            }
            if (value > node->value) {
                return find(node->right, value);
            }
            if (node->value == value) {
                return &node->value;
            }
        }
        return nullptr;
    }

    void traversal(Node *node) {
        if (node->left != nullptr) {
            traversal(node->left);
        }
        data_[size_++] = node->value;
        if (node->right != nullptr) {
            traversal(node->right);
        }
    }

    void lowerBound(struct Node *node, int lower_value, int &min_diff, int &min_diff_value) {
        if (node == nullptr) {
            return;
        }
        if (node->value == lower_value) {
            min_diff_value = lower_value;
            return;
        }
        if (lower_value <= node->value && min_diff > node->value - lower_value) {
            min_diff = node->value - lower_value;
            min_diff_value = node->value;
        }
        if (lower_value < node->value) {
            lowerBound(node->left, lower_value, min_diff, min_diff_value);
        } else {
            lowerBound(node->right, lower_value, min_diff, min_diff_value);
        }
    }

    Node *findMin(Node *node) {
        return node->left ? findMin(node->left) : node;
    }

    // удаление узла с минимальным ключом из дерева r
    Node *removeMin(Node *r) {
        if (r->left == nullptr) {
            return r->right;
        }
        r->left = removeMin(r->left);
        return balance(r);
    }

    Node *remove(Node *p, int value) {
        if (p == nullptr) {
            return nullptr;
        }
        if (value < p->value) {
            p->left = remove(p->left, value);
        }
        if (value > p->value) {
            p->right = remove(p->right, value);
        }
        if (value == p->value) {
            Node *q = p->left;
            Node *r = p->right;
            delete p;
            if (r == nullptr) {
                return q;
            }
            Node *min = findMin(r);
            min->right = removeMin(r);
            min->left = q;
            return balance(min);
        }
        return balance(p);
    }

    int getHeight(Node *node) {
        int left = 0, right = 0, count = 0;
        if (node != nullptr) {
            left = getHeight(node->left);
            right = getHeight(node->right);
            count = ((left > right) ? left : right) + 1;
        }
        return count;
    }

    int getSize(Node *node) {
        int left = 0, right = 0, sum = 0;
        if (node != nullptr) {
            left = getSize(node->left);
            right = getSize(node->right);
            sum = right + left + 1;
        }
        return sum;
    }

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

    int balanceFactor(Node *node) {
        return height(node->right) - height(node->left);
    }

    void fixHeight(Node *node) {
        int hl = height(node->left);
        int hr = height(node->right);
        node->height = (hl > hr ? hl : hr) + 1;
    }

    // Правый поворот относительно p
    Node *rightRotate(Node *p) {
        Node *q = p->left;
        p->left = q->right;
        q->right = p;
        fixHeight(p);
        fixHeight(q);
        return q;
    }

    Node *leftRotate(Node *q) {
        Node *p = q->right;
        q->right = p->left;
        p->left = q;
        fixHeight(q);
        fixHeight(p);
        return p;
    }

    // балансировка узла p
    Node *balance(Node *p) {
        fixHeight(p);
        // Перекос вправо
        if (balanceFactor(p) == 2) {
            if (balanceFactor(p->right) < 0) {
                p->right = rightRotate(p->right);
            }
            return leftRotate(p);
        }
        // Перекос влево
        if (balanceFactor(p) == -2) {
            if (balanceFactor(p->left) > 0) {
                p->left = leftRotate(p->left);
            }
            return rightRotate(p);
        }
        return p;
    }

    Node *insertInto(Node *node, int value) {
        if (node == nullptr) {
            return new Node(value);
        }
        if (value < node->value) {
            node->left = insertInto(node->left, value);
        }
        if (value > node->value) {
            node->right = insertInto(node->right, value);
        }
        return balance(node);
    }

    void clear(Node *node) {
        if (node != nullptr) {
            if (node->right != nullptr) {
                clear(node->right);
            }
            if (node->left != nullptr) {
                clear(node->left);
            }
            delete node;
        }
    }

    void print(Node *node) {
        if (node == nullptr) {
            return;
        }
        print(node->left);
        std::cout << node->value << ' ';
        print(node->right);
    }
};