I don’t know where stack-over-flow error occurs in C++

  c++, memory, overflow, stack

Here is the code which uses ‘Red-Black Tree(RBT)’ data structure,
and implements such a hospital problem.

User can use 4 methods

  • Inserting information of a patient.
  • Finding out information of a patient.
  • Adding additional information of a patient in the tree(RBT).
  • Calculate sum of patients who has epidemic.

The thing is,
when I insert patients(about 1 ~ 70 people), the stack-over-flow error doesn’t occur.
But about more 70 people, the error occurs and I don’t know which code-block makes that error.

I’ve been suspicious methods related in ‘insert’ which use recursion, but I can’t find out.

Thanks for help.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class node {
public:
    node* p = nullptr;
    node* l = nullptr;
    node* r = nullptr;
    char* color;

    int* id;
    string* name;
    string* num;
    int* add_x;
    int* add_y;
    vector<string> disease;
    int* pay;

    node(int id, string name, string num, int add_x, int add_y, string disease, int pay) {
        this->color = new char;
        *this->color = 'r';

        this->id = new int;
       *this->id = id;
       this->name = new string;
        *this->name = name;
        this->num = new string;
        *this->num = num;
        this->add_x = new int;
        *this->add_x = add_x;
        this->add_y = new int;
        *this->add_y = add_y;
        this->disease.push_back(disease);
        this->pay = new int;
        *this->pay = pay;
    }
};

class RBT {
public:
    vector<node*> nodelist;
    node* root = nullptr;

    // methods for insert a node. To make Red-Black Tree balanced, using "checkDoublered", "restructuring" and "recoloring" methods. 
    void insert(node* n);
    void insertForSearch(node* new_n, node* n, int* d);
    void checkDoublered(node* new_n, int* d);
    void restructuring(node* new_n, int* d);
    void recoloring(node* new_n);

    // method for find out a node.
    void search(int id, node* n, int* d);
 
    // method for add more info to a node.
    void addForSearch(int id, string DI, int C, node* n, int* d);

    // method for calculate sum of epidemic patients.
    void epiForSearch(string DI);

};

RBT* rbt = new RBT();

int main() {
   
    int n;
    cin >> n;

    char cmd;
    while (n--) {
        cin >> cmd;
        if (cmd == 'I') {
            int K;
            string N;
            string H;
            int Ax;
            int Ay;
            string DI;
            int C;

            cin >> K;
            cin >> N;
            cin >> H;
            cin >> Ax;
            cin >> Ay;
            cin >> DI;
            cin >> C;

            node* n = new node(K, N, H, Ax, Ay, DI, C);
            rbt->insert(n);
        }
        else if (cmd == 'F') {
            int K;

            cin >> K;

            if (rbt->nodelist.size() == 0) {
                cout << "Not found" << endl;
            }
            else {
                int d = 0;
                rbt->search(K, rbt->root, &d);
            }
        }
        else if (cmd == 'A') {
            int K;
            string DI;
            int C;

            cin >> K;
            cin >> DI;
            cin >> C;

            if (rbt->nodelist.size() == 0) {
                cout << "Not found" << endl;
            }
            else {
                int d = 0;
                rbt->addForSearch(K, DI, C, rbt->root, &d);
            }
        }
        else if (cmd == 'E') {
            string DI;

            cin >> DI;

            rbt->epiForSearch(DI);
        }   
    }
}

void RBT::insert(node* n) {
    int d = 0;
    if (nodelist.size() == 0) {
        nodelist.push_back(n);
        this->root = n;
        *n->color = 'b';

        node* leaf_n1 = new node(-1, "", "", 0, 0, "", 0);
        node* leaf_n2 = new node(-1, "", "", 0, 0, "", 0);
        *leaf_n1->color = 'b';
        *leaf_n2->color = 'b';
        n->l = leaf_n1;
        n->r = leaf_n2;

        cout << d << " 1" << endl;
    }
    else {
        insertForSearch(n, root, &d);
    }
}
void RBT::insertForSearch(node* new_n, node* n, int* d) {

    if (*new_n->id == *n->id) {
        cout << *d << " 0" << endl;
    }
    else if (*new_n->id > * n->id) {
        if (*n->r->id == -1) {
            *d = *d + 1;
            new_n->p = n;
            n->r = new_n;
            nodelist.push_back(new_n);

            node* leaf_n1 = new node(-1, "", "", 0, 0, "", 0);
            node* leaf_n2 = new node(-1, "", "", 0, 0, "", 0);
            *leaf_n1->color = 'b';
            *leaf_n2->color = 'b';
            new_n->l = leaf_n1;
            new_n->r = leaf_n2;

            checkDoublered(new_n, d);

            cout << *d << " 1" << endl;
        }
        else {
            *d = *d + 1;
            insertForSearch(new_n, n->r, d);
        }
    }
    else {
        if (*n->l->id == -1) {
            *d = *d + 1;
            new_n->p = n;
            n->l = new_n;
            nodelist.push_back(new_n);

            node* leaf_n1 = new node(-1, "", "", 0, 0, "", 0);
            node* leaf_n2 = new node(-1, "", "", 0, 0, "", 0);
            *leaf_n1->color = 'b';
            *leaf_n2->color = 'b';
            new_n->l = leaf_n1;
            new_n->r = leaf_n2;

            checkDoublered(new_n, d);

            cout << *d << " 1" << endl;
        }
        else {
            *d = *d + 1;
            insertForSearch(new_n, n->l, d);
        }
    }
}
void RBT::checkDoublered(node* new_n, int* d) {
    if (*new_n->p->color == 'b') {
        return;
    }
    else {
        node* p = new_n->p;
        node* grand_p = p->p;
        if (p == grand_p->l) {
            if (*grand_p->r->color == 'b') {
                restructuring(new_n, d);
            }
            else {
                recoloring(new_n);
                checkDoublered(new_n->p->p, d);
            }
        }
        else {
            if (*grand_p->l->color == 'b') {
                restructuring(new_n, d);
            }
            else {
                recoloring(new_n);
                if (new_n->p->p == root) {
                    *root->color = 'b';
                    return;
                }
                checkDoublered(new_n->p->p, d);
            }

        }
    }
}
void RBT::restructuring(node* new_n, int* d) {
    node* n = new_n;
    node* p = n->p;
    node* grand_p = p->p;

    node* x = nullptr;
    node* y = nullptr;
    node* z = nullptr;

    node* new_p = nullptr;

    node* child_1 = nullptr;
    node* child_2 = nullptr;
    node* child_3 = nullptr;
    node* child_4 = nullptr;

    if (*n->id > * p->id) {
        if (*p->id > * grand_p->id) {
            x = grand_p;
            y = p;
            z = n;

            new_p = grand_p->p;

            child_1 = x->l;
            child_2 = y->l;
            child_3 = z->l;
            child_4 = z->r;

            *d = *d - 1;
        }
        else {
            x = p;
            y = n;
            z = grand_p;

            new_p = grand_p->p;

            child_1 = x->l;
            child_2 = y->l;
            child_3 = y->r;
            child_4 = z->r;

            *d = *d - 2;
        }
    }
    else {
        if (*p->id < *grand_p->id) {
            x = n;
            y = p;
            z = grand_p;

            new_p = grand_p->p;

            child_1 = x->l;
            child_2 = x->r;
            child_3 = y->r;
            child_4 = z->r;

            *d = *d - 1;
        }
        else {
            x = grand_p;
            y = n;
            z = p;

            new_p = grand_p->p;

            child_1 = x->l;
            child_2 = y->l;
            child_3 = y->r;
            child_4 = z->r;

            *d = *d - 2;
        }
    }

    y->l = x;
    y->r = z;

    x->l = child_1;
    x->r = child_2;
    x->p = y;

    z->l = child_3;
    z->r = child_4;
    z->p = y;

    *x->color = 'r';
    *z->color = 'r';
    *y->color = 'b';

    if (new_p == nullptr) {
        this->root = y;
    }
    else {
        if (new_p->l == grand_p) {
            new_p->l = y;
        }
        else {
            new_p->r = y;
        }
    }
}
void RBT::recoloring(node* new_n) {
    node* n = new_n;
    node* p = n->p;
    node* grand_p = p->p;

    *p->color = 'b';
    *grand_p->color = 'r';
    if (p == grand_p->r) {
        *grand_p->l->color = 'b';
    }
    else {
        *grand_p->r->color = 'b';
    }
}

void RBT::search(int id, node* n, int* d) {
    if (id == *n->id) {
        cout << *d << " " << *n->name << " " << *n->num << " " << *n->add_x << " " << *n->add_y << endl;
    }
    else if (id > * n->id) {
        if (*n->r->id == -1) {
            cout << "Not found" << endl;
        }
        else {
            *d = *d + 1;
            search(id, n->r, d);
        }
    }
    else {
        if (*n->l->id == -1) {
            cout << "Not found" << endl;
        }
        else {
            *d = *d + 1;
            search(id, n->l, d);
        }
    }
}

void RBT::addForSearch(int id, string DI, int C, node* n, int* d) {
    if (id == *n->id) {
        n->disease.push_back(DI);
        *n->pay += C;
        cout << *d << endl;
    }
    else if (id > * n->id) {
        if (*n->r->id == -1) {
            cout << "Not found" << endl;
        }
        else {
            *d = *d + 1;
            addForSearch(id, DI, C, n->r, d);
        }
    }
    else {
        if (*n->l->id == -1) {
            cout << "Not found" << endl;
        }
        else {
            *d = *d + 1;
            addForSearch(id, DI, C, n->l, d);
        }
    }
}

void RBT::epiForSearch(string DI) {
    int T = 0;
    for (unsigned int i = 0; i < nodelist.size(); i++) {
        if (nodelist[i]->disease[nodelist[i]->disease.size() - 1] == DI) {
            T++;
        }
    }
    cout << T << endl;
}

Source: Windows Questions C++

LEAVE A COMMENT