tree

#include <bits/stdc++.h>

using namespace std;

struct Node{

    long long int value;
    long long size;

    void fix_size() {
        size = 1;
        for (auto& x : sons)
            if (x != nullptr)
                size += x->size;
    }

    Node*& left_son() {
        return sons[0];
    }

    Node*& right_son() {
        return sons[1];
    }

    Node(long long value) : value(value), size(1), sons({nullptr, nullptr}) {}

private:

    vector<Node*> sons;

};

struct Tree {

    Tree() {
        srand(time(NULL));
        root = nullptr;
    }

    void insert(long long int value) {
        insert(root, value);
    }

    bool contains(long long int value) {
        return contains(root, value);
    }

    void add_tree(Tree& tree) {
        add_tree(tree.root);
    }

    string str_tree() {
        if (root == nullptr)
            return "tree is empty!";
        string s = "tree: ";
        str_tree(root, s);
        return s;
    }

    string sym_tree() {
        if (root == nullptr)
            return "tree is empty!";
        string s = "tree: ";
        sym_tree(root, s);
        return s;
    }

private:

    void add_tree(Node*& node) {
        if (node == nullptr)
            return;
        add_tree(node->left_son());
        add_tree(node->right_son());
        insert(root, node->value);
    }

    void str_tree(Node*& node, string& s) {
        if (node == nullptr)
            return;
        s += to_string(node->value) + " ";
        str_tree(node->left_son(), s);
        str_tree(node->right_son(), s);
    }

    void sym_tree(Node*& node, string& s) {
        if (node == nullptr)
            return;
        sym_tree(node->left_son(), s);
        s += to_string(node->value) + " ";
        sym_tree(node->right_son(), s);
    }

    bool contains(Node*& node, long long int value) {
        if (node == nullptr)
            return false;
        if (node->value == value)
            return true;
        return contains(node->left_son(), value) || contains(node->right_son(), value);
    }

    void insert(Node*& node, long long int value) {
        if (node == nullptr) {
            node = new Node(value);
            return;
        }
        if (rand() % (node->size + 1) == 0) {
            insert_root(node, value);
            node->fix_size();
        } else {
            if (value > node->value)
                insert(node->right_son(), value);
            else
                insert(node->left_son(), value);
            node->fix_size();
        }
    }

    void insert_root(Node*& p, long long int value) // вставка нового узла с ключом value в корень дерева p
    {
        if (p == nullptr) {
            p = new Node(value);
            return;
        }
        if (value < p->value)
        {
            insert_root(p->left_son(), value);
            rotate_right(p);
        }
        else
        {
            insert_root(p->right_son(), value);
            rotate_left(p);
        }
    }

    void rotate_right(Node*& p)
    {
        Node* q = p->left_son();
        if (q == nullptr) {
            delete p;
            p = nullptr;
            return;
        }
        p->left_son() = q->right_son();
        q->right_son() = p;
        q->size = p->size;
        p->fix_size();
        p = q;
    }

    void rotate_left(Node*& q)
    {
        Node* p = q->right_son();
        if (p == nullptr) {
            delete q;
            q = nullptr;
            return;
        }
        q->right_son() = p->left_son();
        p->left_son() = q;
        p->size = q->size;
        q->fix_size();
        q = p;
    }

    Node* root;

};

int main() {
    int a;
    cout << "Enter count of elements in A tree: ";
    cin >> a;
    Tree A, B;
    for (int i = 0; i < a; ++i) {
        int tmp;
        cout << "Enter element " << i + 1 << ": ";
        cin >> tmp;
        A.insert(tmp);
    }
    cout << "A " << A.str_tree() << '\n';
    cout << "Enter count of elements in B tree: ";
    cin >> a;
    for (int i = 0; i < a; ++i) {
        int tmp;
        cout << "Enter element " << i + 1 << ": ";
        cin >> tmp;
        B.insert(tmp);
    }
    cout << "B " << B.sym_tree() << '\n';
    A.add_tree(B);
    cout << "After operation\n";
    cout << "A " << A.str_tree() << '\n';
}