Search code examples
c++stack-overflow

Stack overflow? Interesting behaviour during very deep recursion

While I was making my assignment on BST, Linked Lists and AVL I noticed.. actually it is as in the title.

I believe it is somehow related to stack overflow, but could not find why it is happening.

Creation of the BST and Linked list

creation

Searching for all elements in Linked list and BST

search And probably most interesting...

Comparison of the height of BST and AVL

(based on array of unique random integers) avlbst

On every graph something interesting begins around 33k elements.

Optimization O2 in MS Visual Studio 2019 Community.

Search function of Linked list is not recursive.

Memory for each "link" was allocated with "new" operator.

X axis ends on 40k elements because when it is about 43k then stack overflow error happens.

Do you know why does it happen? Actually, I'm curious what is happening. Looking forward to your answers! Stay healthy.

Here is some related code although it is not exactly the same, I can assure it works the same and it could be said some code was based on it.

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 tree is a BST read inorder and then, array of the elements is inserted into tree object through bisection.

Solution

  • Spikes in time could be, and I am nearly sure they are, because of using up some cache of the CPU (L2 for example). Some leftover data was stored somewhere in slower memory.

    The answer is thanks to @David_Schwartz

    Spike in the height of the BST tree is actually my own fault. For the "array of unique random" integers I used array of already sorted unique items, then mixing them up by swapping elements with the rand() function. I have totally forgotten how devastating could it be if expected to random larger numbers.

    Thanks @rici for pointing it out.