Segmentation error when inserting more than 30,000 elements into a binary search tree

-2

I'm currently working on a program that should generate at least 100,000 URLs (www.google.com.my) and insert them into a binary search tree (BST) and hash tables. I got both of them right, but when I try to insert 100,000 URLs into the BST I get the following: Process returned -1073741571 (0xC00000FD) execution time: 21.358 s. And when I run the debugger I get the following: Program received signal SIGSEGV, Segmentation fault.In ?? () (). The debugger did not show which line the error was, so where is the problem and how do I fix it?

This is my code:

main.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <stdint.h>
#include <cstdlib>
#include <fstream>
#include <string>
#include <conio.h>
#include <stdexcept>
#include "HashTable.cpp"
#include "BinarySearch.h"

using namespace std;

HashTable<long long> ht(0);
treeNode *root = NULL;

vector<long long> dataList;
bool error_msg = false;
static long long nextIC = 1;
long long getNextIC()
{
    return ++nextIC;
}

.
.
.
.
ifstream file2(fileName);
        while (getline(file2, str))
        {
            root = insertNode(root, countData);
            countData++;
        }
        file2.close();

        end = clock();
        elapsed_secs = double(end - begin) / ( CLOCKS_PER_SEC / 1000);

BinarySearch.h

#include <iostream>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct treeNode
{
    long long data;
    treeNode *left;
    treeNode *right;
};

treeNode *insertNode(treeNode *node,long long data)
{
    if(node==NULL)
    {
        treeNode *temp = new treeNode();
        temp -> data = data;
        temp -> left = temp -> right = NULL;
        return temp;
    }
    if(data >(node->data))
    {
        node->right = insertNode(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = insertNode(node->left,data);
    }
    /* Else there is nothing to do as the data is already in the tree. */
    return node;
}

treeNode * searchNode(treeNode *node, long long data)
{
    if(node==NULL)
    {
        /* Element is not found */
        return NULL;
    }
    if(data > node->data)
    {
        /* Search in the right sub tree. */
        return searchNode(node->right,data);
    }
    else if(data < node->data)
    {
        /* Search in the left sub tree. */
        return searchNode(node->left,data);
    }
    else
    {
        /* Element Found */
        return node;
    }
}
void displayInorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    displayInorder(node->left);
    cout<<" " << node->data<<" ";
    displayInorder(node->right);
}
void displayPreorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    cout<<" " <<node->data<<" ";
    displayPreorder(node->left);
    displayPreorder(node->right);
}
void displayPostorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    displayPostorder(node->left);
    displayPostorder(node->right);
    cout<<" " <<node->data<<" ";
}
c++
data-structures
binary-search-tree
asked on Stack Overflow Feb 5, 2018 by Johan Chersev • edited Jul 9, 2019 by Cœur

1 Answer

1

Trees are limited in their maximum depth i.e. the distance from root to the furthest leaf. This limitation is imposed by the recursive nature of the tree algorithms because recursion depth itself is limited by the size of the stack memory. Recursion depth is limited by the stack space because each function call places a new call frame on the stack.

This maximum depth limitation is a problem for non-balanced BST because such tree can become unbalanced. In the worst case, when elements are inserted in sorted order (or reverse), the depth grows linearly.

To support large number of elements in any insertion order, you can use a balanced BST such as red-black tree or AVL tree. The depth limitation is much less of a problem for balanced trees because their maximum depth grows logarithmically.

answered on Stack Overflow Feb 5, 2018 by eerorika

User contributions licensed under CC BY-SA 3.0