espace Ram épuisé tout en créant un binaire Recherche Arbre de 60000 éléments

Question

Je suis en train de construire un énorme arbre de recherche binaire:

class Node 
{ 
public: 
    int value; 
    shared_ptr<Node> left; 
    Node* right; 

    Node(int v):value(v){} 
    void addLeft(){ 
     static int i; 
     shared_ptr<Node> node=make_shared<Node>(i); 
     left=node; 
     cout<<i++<<endl; 
     if(i<60000) 
     node->addLeft(); 
    } 
}; 



int main(){ 

    shared_ptr<Node>root=make_shared<Node>(9); 
    root->addLeft(); 
    return 0; 
} 

Je reçois une erreur de seg sur l'exécution de ce code, dans valgrind je le présent rapport: Un indice sur la façon de construire le BST sans déborder de l'espace de la RAM?

==17373== Stack overflow in thread #1: can't grow stack to 0xffe801000 

Toute aide est très appréciée

Answer 1

Dépasser la pile n'est pas la même chose que de dépasser votre RAM. Les appels de fonction s'accumulent sur la pile, le problème est que vous essayez de placer 60000 appels de fonction et variables sur la pile. Convertissez votre fonction en boucle et tout ira bien. Il va même se débarrasser de ce terrible static int i.

Voici une version de votre fonction utilisant une boucle for sans récursivité.

void addLeft() 
{ 
    left = std::make_shared<Node>(0); 

    // tail is the last element to have been added to the tree 
    std::shared_ptr<Node> tail = left; 
    std::cout << 0 << std::endl; 

    // Add nodes from 1 to 60000 inclusively 
    for (int i = 1; i <= 60000; ++i) 
    { 
     std::cout << i << std::endl; 
     tail->left = std::make_shared<Node>(i); 
     tail = tail->left; 
    } 
}