[Erledigt] Speicherfreigabe im binärem Baum - Wie StackOverFlow vermeiden?

[cocacola88]

Hallo ihr C++-Freunde,
ich hab mal eine Frage an die Fachkundigen Leute hier.

Im Rahmen einer Semesterarbeit muss ich eine Datenstruktur erstellen, die Elemente sequenziell anordnet und dabei sowohl Speicher- als auch Laufzeit- effizient in Bezug auf die Konkatenation arbeitet. Der Name dieser Datenstruktur soll "Sequence" sein

Um das zu realisieren wurde intern mit einem Baum gearbeitet,
der ähnlich einem binären Baum arbeitet.

Der Aufbau usw. ist alles in Ordnung und funktioniert soweit einwandfrei. Allerdings gibt es ein Problem im Destruktor bzw. bei der Speicherfreigabe.
Der Baum besteht aus Elementen der Klasse "SequenceNode" die sich wiederum einen Referenzzähler merken um feststellen zu können ob es noch Verweise auf dieses Objekt gibt bzw. ob das Objekt gelöscht werden kann. Stirbt jetzt einer dieser Knoten muss er seinem rechten und linken Nachfolger natürlich mitteilen, dass es eine Referenz weniger gibt, die auf sie zeigt.

Wenn wir uns folgenden Code ansehen

{
Sequence<unsigned> s1; 

for(unsigned ui = 1; ui <= 10000000; ++ui) 
    s1 = s1 + ui
std::cout << "ende" << std::endl;
}

Es wird eine Sequenz mit 10Mio Einträgen erstellt. Danach wird "ende" auf dem Bildschirm ausgegeben und am Ende des Blockes wird die Sequenz gelöscht.
Es wird also der Destruktor von "Sequence" aufgerufen.

~Sequence()
{ 
    if(m_Root != 0) 
       m_Root->addRefCount(-1); 
}

Die Sequenz verwaltet einen Pointer auf ein Wurzelelement des internen Baums.
Diesem Wurzelelement muss nun mitgeteilt werden, dass es eine Referenz weniger gibt.

Die Methode addRefCount befindet sich in der Klasse SequenceNode

void addRefCount(int value)
        {
            m_RefCount += value;
            if(m_RefCount < 1)
                delete this;
        }

Sobald hier also der Referenzzähler < 1 wird, wir das Objekt gelöscht und ruft den eigenen Destruktor auf.

~SequenceNode()
        {
            if(m_Left != 0)
                m_Left->addRefCount(-1);
            if(m_Right != 0)
                m_Right->addRefCount(-1);
        }

Dabei kommt es bei 10 Mio Elementen zu einer tiefen Rekursion,
da jeder sterbende Knoten seinem rechten und linken Nachfolger mitteilen muss das es eine Referenz weniger gibt, und die ggf. dann ihren Nachfolgern usw.

Frage ist jetzt, wie man die Destruktoren so umschreiben kann,
das es zu keinem StackOverflow mehr kommt, aber der Speicherplatz korrekt freigegeben wird.

Hat jemand eine Idee/ Tipp für mich,
wie man das Problem hier in den Griff bekommen kann ?

Vielen Dank

[DocShoe]

Mittels eines Stacks lässt sich Rekursion linearisieren, inwiefern das der Aufgabenstellung jetzt entgegenkommt weiss ich nicht.

Hier der Pseudo Code

void delete_node( SequenceNode* node )
{
   assert( node );

   // Referenzzähler verringern     
   node->RefCount--;
   if( Node->RefCount == 0 )
   { 
      // Referenzzähler ist 0, Knoten muss gelöscht werden
      stack NodeStack;
      NodeStack.push( node );

      while( !NodeStack.empty() )
      {
         // oberstes Element vom Stack holen 
         SequenceNode* n = NodeStack.pop();

         if( n->Left ) 
         {
            // Referenzzähler des linken Child Node verringern und ggf. auf Stack legen
            n->Left->RefCount--;
            if( n->Left->RefCount == 0 ) NodeStack.push( n->Left );
         }
         if( n->Right )
         {
            // Referenzzähler des rechten Child Node verringern und ggf. auf Stack legen
            n->Right->RefCount--;
            if( n->Right->RefCount == 0 ) NodeStack.push( n->Right );
         }
         // Knoten löschen 
         delete n;
      }
   }
}

Edit: Statt eines stacks geht auch irgendein anderer Container, dessen Laufzeitverhalten vielleicht besser ist Die Reihenfolge des Löschens spielt ja keine Rolle, da ginge auch eine einfach verkettete Liste

[cocacola88]

Vielen Dank für deine schnelle Antwort.
Durch das Beispiel konnte ich mein Problem relativ schnell lösen
und hab jetzt keinen StackOverFlow mehr und damit hat sich mein Problem dann erledigt.

Für alle die es interessiert

~Sequence()
       {
            abcd(m_Root);
       }

void abcd(SequenceNode<Type>* seqNode)
        {
            seqNode->addRefCount(-1);
            if(seqNode->getRefCount() == 0)
            {
                stack< SequenceNode<Type>* > NodeStack;
                NodeStack.push(seqNode);

                while(!NodeStack.empty())
                {
                    SequenceNode<Type>* node = NodeStack.top();
                    NodeStack.pop();

                    if(node->getLeft())
                    {
                        node->getLeft()->addRefCount(-1);
                        if(node->getLeft()->getRefCount() == 0)
                            NodeStack.push(node->getLeft());
                    }

                    if(node->getRight())
                    {
                        node->getRight()->addRefCount(-1);
                        if(node->getRight()->getRefCount() == 0)
                            NodeStack.push(node->getRight());
                    }

                    delete node;
                }
            }
        }

Und in SequenceNode ist der Destruktor nun leer und

void addRefCount(int value)
        {
            m_RefCount += value;
        }