问：

所以我使用了与 geeksforgeeks 相同的 splaytree 并做了一些实验：

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

版本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);

第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);

输出：

对于版本。1：插入时间为vers。2：插入时间为cpp insertion time: 0.779000insertion time: 0.156000

我知道 Splay 树每次插入时都会“张开”，所以考虑到有时可能会产生相同的输出，为什么当 splay 树需要 1000000 个不同的输入时，它的运行速度要快得多？这对我来说没有任何意义。（我是一名学生，是的，我的英语不好，很抱歉）。rand

编辑：

我将 vers.2 修改为：

    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);

修改后的 Vers.2 输出：

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

仍然比 vers 快。1