декартовое дерево 1

struct node
{
    int value_node  = NULL;
    int key         = NULL;
    node*   left    = nullptr;
    node*   right   = nullptr;
    node(int new_value)
    {
        value_node = new_value;
        key = rand();
    }

};

typedef pair<node*, node*> Pair;

node* merge(node* A, node* B) // соединение дерева
{
    if (!A) return B;
    if (!B) return A;

    if (A->key > B->key)
    {
        A->right = merge(A->right, B);
        return A;
    }
    else
    {
        B->left = merge(A,B->left);
        return B;
    }
}
Pair split(node* A,const int& x) // деление дерева
{
    if (!A) return { 0,0 };
    if (A->value_node < x)
    {
        Pair q = split(A->right, x);
        A->right = q.first;
        return { A, q.second };
    }
    else
    {

        Pair q = split(A->left, x);
        A->left = q.second;
        return { q.first, A };
    }
}
node* insert(node* A, int x) // вставка элементов
{
    node* new_node = new node(x);
    Pair q = split(A, x);
    A = merge(q.first, merge(new_node, q.second));
    return A;
}