Splay Tree insertion time efficiency with different input cases

77 Views Asked by At

So I used the same splaytree used in geeksforgeeks and did some experiment with it:

code: https://www.geeksforgeeks.org/insertion-in-splay-tree/?ref=rp

vers.1

    #include <ctime>
    // the code for splaytree is too long so I just put the link here: https://www.geeksforgeeks.org/insertion-in-splay-tree/?ref=rp
    double t1=clock();
    for(int i = 0; i < 1000000; i++)
    {
        x = rand()%max_x;
        root = insert(root, x);
    }

    double t2=clock();
    double result = (t2-t1)/CLOCKS_PER_SEC;
    printf("insertion time: %f\n", result);

vers.2

    int x;
    double t1=clock();
    for(int i = 0; i < 1000000; i++)
    {
        x = rand()%max_x;
        root = insert(root, i);
    }

    double t2=clock();
    double result = (t2-t1)/CLOCKS_PER_SEC;
    printf("insertion time: %f\n", result);

OUTPUT:

for vers. 1: the insertion time is cpp insertion time: 0.779000 for vers. 2: the insertion time is insertion time: 0.156000

I know Splay tree "splays" every time it does insertion, so consider that rand may generates same outputs sometimes, why splay tree works much faster when it takes 1000000 distinct inputs? That doesn't make any sense to me. (I am a student and yea my English is bad sorry about it).

EDIT:

I modified vers.2 to:

    int x;
    double t1 = clock();
    for(int i = 0; i < 1000000; i++)
    {
        x = rand()%max_x;
        printf("%d",x);
        root = insert(root, i);
    }

    double t2=clock();
    double result = (t2-t1)/CLOCKS_PER_SEC;
    printf("insertion time: %f\n", result);

modified vers.2 output:

 ....a bunch of numbers...time: 0.569000

still faster than vers. 1

0

There are 0 best solutions below