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