c++ - 堆栈溢出？深度递归过程中的有趣行为

Question

当我在BST，链接列表和AVL上进行作业时，我注意到..实际上它与标题中的一样。

我相信它与堆栈溢出有某种联系，但是找不到原因。

创建BST和链接列表



在链接列表和BST中搜索所有元素


可能是最有趣的...

BST和AVL的高度比较

(基于唯一随机整数数组)


在每张图上，围绕33k元素开始出现一些有趣的事情。

MS Visual Studio 2019社区中的优化O2。

链接列表的搜索功能是，而不是递归。

每个“链接”的内存已分配给"new"运算符。

X轴在40k个元素上结束，因为当它大约为43k时，就会发生堆栈溢出错误。

你知道为什么会这样吗？实际上，我很好奇发生了什么。期待您的回答!保持健康。

这是一些相关的代码，尽管它们并不完全相同，但我可以保证它的工作原理相同，并且可以说某些代码是基于它的。

struct tree {
        tree() {
        info = NULL;
        left = NULL;
        right = NULL;
        }
        int info;
    struct tree *left;
    struct tree *right;
};

struct tree *insert(struct tree*& root, int x) {
    if(!root) {
        root= new tree;
        root->info = x;
        root->left = NULL;
        root->right = NULL;
        return(root);
    }
    if(root->info > x)
         root->left = insert(root->left,x); else {
        if(root->info < x)
            root->right = insert(root->right,x);
    }
    return(root);
}

struct tree *search(struct tree*& root, int x) {
    struct tree *ptr;
    ptr=root;
    while(ptr) {
        if(x>ptr->info)
             ptr=ptr->right; else if(x<ptr->info)
             ptr=ptr->left; else
             return ptr;
    }

int bstHeight(tree*& tr) {
    if (tr == NULL) {
        return -1;
    }
    int lefth = bstHeight(tr->left);
    int righth = bstHeight(tr->right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

AVL树是按BST顺序读取的，然后将元素数组通过二等分插入到树对象中。

Answer 1

由于使用了CPU的某些高速缓存(例如L2)，时间可能会很快增加，我几乎可以肯定的是。一些剩余的数据存储在较慢的内存中的某个位置。

答案是由于@David_Schwartz

BST树的高度峰值实际上是我自己的错。对于“唯一随机数组”整数，我使用已经排序的唯一项数组，然后通过与rand()函数交换元素来混合它们。我完全忘记了如果期望随机产生更大的数字会是多么的毁灭。

感谢@rici指出。