a_tree

#include <bits/stdc++.h>

using namespace std;

struct Node{

    long long int bro;
    long long int left_son;
    long long int parent;
    long long int val;
    long long int size;

    Node(long long int val, long long int parent=-1) {
        this->val = val;
        this->parent = parent;
        bro = -1;
        left_son = -1;
        size = 1;
    }

};
struct Tree{

    void insert(long long int val) {
        if (nodes.empty())
            insert(-1, -1, val);
        else
            insert(get_root(), -1, val);
    }

    void delete_tree(Tree& b) {
        for (auto& x : b.nodes)
            delete_node(x->val);
    }

    void delete_node(long long int val) {
        if (nodes.empty())
            return;
        delete_n(find(get_root(), val));
    }

    void symmetry_print() {
        if (nodes.empty())
            cout << "дерево пустое!";
        else {
            cout << "дерево: ";
            symmetry_print(get_root());
        }
        cout << endl;
    }

    void obr_print() {
        if (nodes.empty())
            cout << "дерево пустое!";
        else {
            cout << "дерево: ";
            obr_print(get_root());
        }
        cout << endl;
    }

private:

    void delete_n(long long int index) {
        if (index == -1)
            return;
        long long int l = get_left_son(index), r = get_right_son(index);
        if (l == -1 && r == -1) {
            if (nodes[index]->parent != -1) {
                if (is_right(nodes[index]->parent, nodes[index]->val)) {
                    if (nodes[nodes[index]->parent]->left_son != -1)
                        nodes[nodes[nodes[index]->parent]->left_son]->bro = -1;
                } else
                    nodes[nodes[index]->parent]->left_son = -1;
            }
            deleting_node(index);
        } else if (r == -1) {
            nodes[l]->parent = nodes[index]->parent;
            nodes[l]->bro = nodes[index]->bro;
            if (nodes[index]->parent != -1) {
                if (is_right(nodes[index]->parent, nodes[index]->val)) {
                    if (nodes[nodes[index]->parent]->left_son != -1)
                        nodes[nodes[nodes[index]->parent]->left_son]->bro = l;
                } else {
                    nodes[nodes[index]->parent]->left_son = l;
                }
            }
            deleting_node(index);
        } else if (l == -1) {
            nodes[r]->parent = nodes[index]->parent;
            nodes[r]->bro = nodes[index]->bro;
            if (nodes[index]->parent != -1) {
                if (is_right(nodes[index]->parent, nodes[index]->val)) {
                    if (nodes[nodes[index]->parent]->left_son != -1)
                        nodes[nodes[nodes[index]->parent]->left_son]->bro = r;
                } else {
                    nodes[nodes[index]->parent]->left_son = r;
                }
            }
            deleting_node(index);
        } else {
            nodes[index]->val = del_left(get_right_son(index));
        }
    }

    long long int del_left(long long index) {
        while (nodes[index]->left_son != -1)
            index = nodes[index]->left_son;
        long long int tmp = nodes[index]->val, r = get_right_son(index);
        if (r != -1) {
            nodes[r]->parent = nodes[index]->parent;
            if (!is_right(nodes[index]->parent, nodes[index]->val)) {
                nodes[nodes[index]->parent]->left_son = r;
            } else {
                long long int l = get_left_son(nodes[index]->parent);
                if (l != -1)
                    nodes[l]->bro = r;
            }
        } else {
            if (!is_right(nodes[index]->parent, nodes[index]->val)) {
                nodes[nodes[index]->parent]->left_son = -1;
            } else {
                long long int l = get_left_son(nodes[index]->parent);
                if (l != -1)
                    nodes[l]->bro = -1;
            }
        }
        deleting_node(index);
        return tmp;
    }

    void deleting_node(long long int index) {
        nodes.erase(nodes.begin() + index);
        for (auto& x : nodes) {
            if (x->parent > index)
                --x->parent;
            if (x->left_son > index)
                --x->left_son;
            if (x->bro > index)
                --x->bro;
        }
    }

    void symmetry_print(long long int index) {
        if (index == -1)
            return;
        symmetry_print(get_left_son(index));
        cout << nodes[index]->val << ' ';
        symmetry_print(get_right_son(index));
    }

    void obr_print(long long int index) {
        if (index == -1)
            return;
        obr_print(get_left_son(index));
        obr_print(get_right_son(index));
        cout << nodes[index]->val << ' ';
    }

    void rotate_right(long long int index)
    {
        long long int l = get_left_son(index);
        if (l == -1)
            return;
        set_as_left_son(index, get_right_son(l));
        nodes[l]->bro = nodes[index]->bro;
        nodes[index]->bro = -1;
        nodes[l]->parent = nodes[index]->parent;
        if (nodes[l]->parent != -1 && !is_right(nodes[l]->parent, nodes[index]->val))
            nodes[nodes[l]->parent]->left_son = l;
        set_as_right_son(l, index);
        nodes[l]->size = nodes[index]->size;
        fix_size(index);

    }

    void rotate_left(long long int index)
    {
        long long int r = get_right_son(index);
        if (r == -1)
            return;
        set_as_right_son(index, get_left_son(r));
        nodes[r]->bro = nodes[index]->bro;
        if (nodes[r]->left_son != -1)
            nodes[nodes[r]->left_son]->bro = -1;
        nodes[r]->parent = nodes[index]->parent;
        if (nodes[r]->parent != -1 && !is_right(nodes[r]->parent, nodes[index]->val))
            nodes[nodes[r]->parent]->left_son = r;
        set_as_left_son(r, index);
        nodes[r]->size = nodes[index]->size;
        fix_size(index);
    }

    void fix_size(long long int index) {
        long long int l = get_left_son(index), r = get_right_son(index);
        nodes[index]->size = 1 + (l == -1 ? 0 : nodes[l]->size) + (r == -1 ? 0 : nodes[r]->size);
    }

    void insert(long long int index, long long int parent, long long int val) {
        if (index == -1) {
            nodes.push_back(new Node(val, parent));
            check_node(nodes.size() - 1);
            return;
        }
        if (rand() % (nodes[index]->size + 1) == 0) {
            insert_root(index, parent, val);
        } else {
            if (val > nodes[index]->val) {
                insert(get_right_son(index), index, val);
            } else {
                insert(get_left_son(index), index, val);
            }
        }
    }

    void insert_root(long long int index, long long int parent, long long int val) {
        if (index == -1) {
            nodes.push_back(new Node(val, parent));
            check_node(nodes.size() - 1);
            return;
        }
        if (val < nodes[index]->val)
        {
            insert_root(get_left_son(index), index, val);
            rotate_right(index);
        }
        else
        {
            insert_root(get_right_son(index), index, val);
            rotate_left(index);
        }
    }

    long long int find(long long int index, long long int val) {
        if (index == -1)
            return -1;
        if (val == nodes[index]->val)
            return index;
        if (nodes[index]->val < val) {
            return find(get_right_son(index), val);
        }
        return find(get_left_son(index), val);
    }

    void check_node(long long int index) {
        long long int parent = nodes[index]->parent;
        if (parent != -1)
            if (is_right(parent, nodes[index]->val)) {
                if (nodes[parent]->left_son != -1)
                    nodes[nodes[parent]->left_son]->bro = index;
            } else {
                nodes[parent]->left_son = index;
                for (long long int i = 0; i < nodes.size(); ++i) {
                    if (i == index)
                        continue;
                    if (nodes[i]->parent == parent && is_right(parent, nodes[i]->val))
                        nodes[index]->bro = i;
                }
            }
    }

    long long int get_root() {
        long long int index = 0;
        while (nodes[index]->parent != -1)
            index = nodes[index]->parent;
        return index;
    }

    long long int get_left_son( long long int index) {
        return nodes[index]->left_son;
    }

    long long int get_right_son(long long int index) {
        for (long long int i = 0; i < nodes.size(); ++i) {
            if (nodes[i]->parent == index && is_right(index, nodes[i]->val))
                return i;
        }
        return -1;
    }

    void set_as_left_son(long long int parent, long long int index) {
        nodes[parent]->left_son = index;
        if (index != -1) {
            nodes[index]->parent = parent;
            nodes[index]->bro = get_right_son(parent);
        }
    }

    void set_as_right_son(long long int parent, long long int index) {
        if (nodes[parent]->left_son != -1)
            nodes[nodes[parent]->left_son]->bro = index;
        if (index != -1)
            nodes[index]->parent = parent;
    }

    bool is_right(long long int parent_index, long long int val) {
        return nodes[parent_index]->val < val;
    }
    vector<Node*> nodes;
};

int main() {
    int a;
    Tree A, B;
    cout << "Введите кол-во элементов дерева А: ";
    cin >> a;
    for (int i = 0; i < a; ++i) {
        int t;
        cout << "Введите элемент " << i + 1 << ": ";
        cin >> t;
        A.insert(t);
    }
    A.obr_print();
    cout << "Введите кол-во элементов дерева B: ";
    cin >> a;
    for (int i = 0; i < a; ++i) {
        int t;
        cout << "Введите элемент " << i + 1 << ": ";
        cin >> t;
        B.insert(t);
    }
    B.symmetry_print();
    A.delete_tree(B);
    cout << "Дерево А после операции:\n";
    A.obr_print();
}