Переполнение стека? Интересное поведение во время очень глубокой рекурсии

Question

Когда я делал свое назначение на BST, Linked Lists и AVL, я заметил ... на самом деле это как в заголовке.

Я считаю, что это как-то связано с переполнением стека, но не смог найти, почему это

Создание BST и связанного списка

Поиск всех элементов в связанном списке и BST

И, наверное, самое интересное ...

Сравнение высоты BST и AVL

(на основе массива уникальных случайных целых чисел)

На каждом графике что-то интересное начинается около 33 тыс. Элементов.

Оптимизация O2 в сообществе MS Visual Studio 2019.

Функция поиска связанного списка - не рекурсивный.

Память для каждой «ссылки» была выделена с помощью оператора «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

Пики во времени могут быть, и я почти уверен, что они есть, из-за использования некоторого кэша ЦП (например, L2). Некоторые оставшиеся данные были сохранены где-то в более медленной памяти.

Ответ - благодаря @ David_Schwartz

Пик высоты дерева BST на самом деле является моей собственной ошибкой. Для «массива уникальных случайных» целых чисел я использовал массив уже отсортированных уникальных элементов, а затем смешал их, меняя элементы с помощью функции rand(). Я полностью забыл, насколько разрушительными могут быть случайные большие числа.

Спасибо @rici за указание на это.