TREAP implementation in Java

[ebon orbit]

Hi everyone, i implemented a TREAP in Java and testing the time of insertion of the tree with 4 different sets, where all of them have 10^6 keys i noticed that i get too many rotations.

Set A: keys in ascending order, with 10% repeats.
Set B: keys in descending order, with 10% repeats.
Set C: keys in random order, with 10% repeats.
Set D: keys in random order, with 90 per cent repeats.

Results:
Insertion time [TREAP Tree, Set A]: 70 ms
Rotations [TREAP Tree, Set A]: 899988
Insertion time [TREAP Tree, Set B]: 77 ms
Rotations [TREAP Tree, Set B]: 899988
Insertion time [TREAP Tree, Set C]: 716 ms
Rotations [TREAP Tree, Set C]: 1799229
Insertion time [TREAP Tree, Set D]: 119 ms
Rotations [TREAP Tree, Set D]: 199427

For example, in the set C i got 1.7x the number of keys in rotations, should i worry about that? I set the priority in each new node (i dont allow repetitions in the tree) from 0.0 to 1.0. Here it is how i define that:

public boolean insert(Integer value, double priority) {
        if (value == null) {
            throw new IllegalArgumentException("TreapTree does not allow null values");
        }

        if(!contains(root, value)) {
            root = insert(this.root, value, priority);
            nodeCount++;
            return true;
        }
        return false;
    }

    public boolean insert(Integer value) {
        return insert(value, random.nextDouble());
    } ```

[hidden hazel]

<@&987246399047479336> please have a look, thanks.

[ebon orbit]

Besides that, here is how i created the method for generating the sets: ```java
private static ArrayList<Integer> generateSet(int order, int repetitions, int numberKeys) {

    if (repetitions > 100 || repetitions < 0) throw new IllegalArgumentException("repetitions must be between 0 and 100%");
    if (order > 2 || order < 0) throw new IllegalArgumentException("order must be between 0 and 2");
    if (numberKeys <= 0) throw new IllegalArgumentException("numberKeys must be greater than 0");

    ArrayList<Integer> set = new ArrayList<>();
    int numOfKeysRepetitions = Math.round(numberKeys * ((float) repetitions /100)) - 1;

    int randomIndex = (int) (Math.random() * ((numberKeys) + 1));
    while (randomIndex > (numberKeys - numOfKeysRepetitions) - 1) {
        randomIndex = (int) (Math.random() * ((numberKeys) + 1));
    }

    for (int i = 0; i < numberKeys; i++) {
        set.add(i);
        if (i == randomIndex && repetitions != 0) {
            for (int j = 0; j < numOfKeysRepetitions; j++) {
                set.add(i);
            }
        }

        if (set.size() == numberKeys && repetitions != 0) {
            break;
        }
    }

    if (order == 1) { //Descending
        Collections.reverse(set);
        return set;
    } else if (order == 2) { //Random
        Collections.shuffle(set);
        return set;
    }

    //Ascending
    return set;
}```

Thanks for any help!