Декартово дерево по неявному ключу

#include <bits/stdc++.h>
 
using namespace std;
 
struct node{
    node *left, *right;
    int inf, size;
    unsigned int priority;
    node(int INF)
    {
        inf = INF;
        size = 1;
        priority = (rand() << 15) + rand();
        left = right = nullptr;
    }
};
 
int getsize(node *tree){
    if(tree == nullptr)
        return 0;
    return tree->size;
}
 
void update(node *&tree){
    if(tree == nullptr)
        return;
    tree->size = getsize(tree->left) + getsize(tree->right) + 1;
}
 
pair <node*, node*> split(node *tree, int key){
    if(tree == nullptr)
        return {nullptr, nullptr};
    if(getsize(tree) <= key)
        return {tree, nullptr};
    if(key == 0)
        return {nullptr, tree};
    int tree_key = getsize(tree->left);
    if(tree_key >= key){
        pair <node*, node*> splitted = split(tree->left, key);
        tree->left = splitted.second;
        update(tree);
        return {splitted.first, tree};
    }
    else{
        pair <node*, node*> splitted = split(tree->right, key - tree_key - 1);
        tree->right = splitted.first;
        update(tree);
        return {tree, splitted.second};
    }
}
 
node * merge(node *left, node *right){
    if(left == nullptr)
        return right;
    if(right == nullptr)
        return left;
    if(left->priority < right->priority){
        left->right = merge(left->right, right);
        update(left);
        return left;
    }
    else{
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
 
}
 
int get_value(node *tree, int key){
    pair <node*, node*> splitted = split(tree, key);//этот сплит разрезает дерево неправильно
    pair <node*, node*> splitted1 = split(splitted.first, key - 1);
    return splitted1.second->inf;
}
 
void insert(node *&tree, int key, int inf){
    pair <node*, node*> splitted = split(tree, key);
    tree = merge(merge(splitted.first, new node(inf)), splitted.second);
}
 
int main()
{
    node *tree = nullptr;
    for(int i = 0; i < 10; i++){
        insert(tree, i, rand());
    }
    for(int i = 1; i <= 5; i++)
        cout << get_value(tree, i) << " ";
    return 0;
}