Binary Search Tree, Speicher wieder freiegeben

knivil

Warum nicht einfach rekursiv Loeschen. Per Tiefen-"Suche" zu den Blattknoten und beim rekursiven Aufstieg freigeben. Destruktoren zerstoeren, deiner baut aber erstmal einen Stack auf ... dabei kann eine Exception fliegen. Schlecht.

Mit Effektiv meine ich, ist es der gewoehnliche Ansatz einen Stack zu benutzen im den Speicher wieder freizugeben

Nein.

Columbo

Warum nicht einfach rekursiv Loeschen.

Nun, besonders effizient ist das nicht, soweit ich mich erinnere.

Allerdings würde ein unique_ptr auch nur rekursiv löschen - er ruft (implizit) den Destruktor des Knotens auf. Dieser Destruktor zerstört aber auch die Member, unter denen sich wiederum zwei unique_ptrs befinden, deren Destruktor aufgerufen wird.

Das Problem ist, dass man irgendwie "zurückkehren" muss, zum Elternteil, um zum zweiten Knoten zu kommen, und dann wiederum muss man zurück zum Elternknoten dieses Knotens....

Den Elternteil muss man sich also merken.
Also entweder ein Array, um sich alle höheren Verwandten zu merken, oder Rekursion (da werden die Zeiger automatisch 'zwischengespeichert'.
Oder etwa nicht?

knivil

Nun, besonders effizient ist das nicht, soweit ich mich erinnere.

Ja wo du das gerade so erwaehnst, da haette ich jetzt auch selbst drauf kommen koennen.

... Den Elternteil muss man sich also merken

Ja und so. Rekursion halt. Je nach Kenntnisstand hilft ein Buch ueber Algorithmen weiter.

MichelRT

Ein Baum ist eine rekursive Datenstruktur

Wieso also zwanghaft die Rekursion vermeiden.
Die Suche im Baum läuft doch auch rekursiv

volkard

Arcoth schrieb:

Warum nicht einfach rekursiv Loeschen.

Nun, besonders effizient ist das nicht, soweit ich mich erinnere.

Doch.

Arcoth schrieb:

Allerdings würde ein unique_ptr auch nur rekursiv löschen - er ruft (implizit) den Destruktor des Knotens auf. Dieser Destruktor zerstört aber auch die Member, unter denen sich wiederum zwei unique_ptrs befinden, deren Destruktor aufgerufen wird.

Das Problem ist, dass man irgendwie "zurückkehren" muss, zum Elternteil, um zum zweiten Knoten zu kommen, und dann wiederum muss man zurück zum Elternknoten dieses Knotens....

Den Elternteil muss man sich also merken.
Also entweder ein Array, um sich alle höheren Verwandten zu merken, oder Rekursion (da werden die Zeiger automatisch 'zwischengespeichert'.
Oder etwa nicht?

Oder links und rechts merken. Oder nur links und rechts zur Schleife machen. Keine Ahnung, weshalb Du aufwärts gehen magst.

Rekursion halte ich hier für angemessen, wenn der Baum ausreichend balanciert ist, daß es nicht zum Stacküberlauf kommen kann. Dem Hardwarestack traue ich hier mehr Speed zu als einem Softwarestack.

MigMig schrieb:

~bstree()
    {
 
        if(root!=0)
        {
            std::stack<Node*>s;
            if(root->left!=0)s.push(root->left);
            if(root->right!=0)s.push(root->right);
           
 
            while(!s.empty())
            {
                Node *t = s.top();
                s.pop();
                if(t->left!=0)s.push(t->left);
                if(t->right!=0)s.push(t->right);
                std::cout << "Delete: " << t->data << std::endl;
                delete t;
 
            };
   
        }

Da haste eine komische Sonderbehandlung der root.

~bstree()
    {
        if(root!=0)
        {
            std::stack<Node*>s;
            s.push(root);//reicht doch und root wird sogar auch gelöscht

            while(!s.empty())
            {
                Node *t = s.top();
                s.pop();
                if(t->left!=0)s.push(t->left);
                if(t->right!=0)s.push(t->right);
                std::cout << "Delete: " << t->data << '\n';//kein endl
                delete t;
             }
        }

volkard

knivil schrieb:

Warum nicht einfach rekursiv Loeschen. Per Tiefen-"Suche" zu den Blattknoten und beim rekursiven Aufstieg freigeben. Destruktoren zerstoeren, deiner baut aber erstmal einen Stack auf ... dabei kann eine Exception fliegen. Schlecht.

Hmm.
Genug Speicher ist eigentlich da…

~bstree()
{
    if(!root) return;

    Node* rightmost=root;
    while(rightmost->right)
        rightmost=rightmost->right;

    while(root){
        Node* toDie=root;
        rightmost->right=root->left;
        while(rightmost->right)
            rightmost=rightmost->right;
        root=root->right;
        delete toDie;
    }
}
//ungetestet

Columbo

Doch.

Doch?
Aber nicht so gut wie eine smarte Schleife, nicht wahr?

Oder links und rechts merken. Oder nur links und rechts zur Schleife machen. Keine Ahnung, weshalb Du aufwärts gehen magst.

Ich kam nicht direkt darauf, wie man es mit einer richtig hübschen Schleife mit O(1) Speicher, wie du es tust, lösen kann.

volkard

Arcoth schrieb:

Doch.

Doch?
Aber nicht so gut wie eine smarte Schleife, nicht wahr?

Das nervt.

Columbo

Das nervt.

Was nervt?

Auch wenn Rekursion schnell ist, ist es schließlich doch nicht optimal. Und wieso etwas Suboptimales wählen?

volkard

Arcoth schrieb:

Doch.

Doch?
Aber nicht so gut wie eine smarte Schleife, nicht wahr?

Was willste damit aussagen? Falls es das ist, was ich fürchte, haste die Speicherverwaltung nicht mitgerechnet? Es geht nicht darum, eine Zählschleife mit einer rekursion zu vergleichen, sondern es geht auch ums Zwischenspeichern.

knivil

Auch wenn Rekursion schnell ist, ist es schließlich doch nicht optimal. Und wieso etwas Suboptimales wählen?

Deine Behauptungen entbehren jeder Tatsache und sind schlicht falsch. Mit Rekursion wird jeder Knoten besucht, du musst alle Knoten besuchen deswegen kann es keinen schnelleren Algorithmus geben. Troll doch woanders.

camper

volkard schrieb:

Genug Speicher ist eigentlich da…

~bstree()
{
    if(!root) return;
    
    Node* rightmost=root;
    while(rightmost->right)
        rightmost=rightmost->right;
    
    while(root){
        Node* toDie=root;
        rightmost->right=root->left;
        while(rightmost->right)
            rightmost=rightmost->right;
        root=root->right;
        delete toDie;
    }
}
//ungetestet

Daran hatte ich auch gedacht und dann verworfen, in der Annahme, dass es zu quadratischer worst-case-Komplexität führt. Aufgeschrieben ist aber klar zu erkenn, dass die Blattsuche niemals zweimal über den gleichen Knoten führt, ist also doch schön linear.

knivil

Der Algorithmus hat glaube einen Bug. Oder vielleicht nicht, ich muss nochmal schauen.

volkard

camper schrieb:

Was mich wundert, ist, daß ich von diesem Trick noch nie auch nur andeutungsweise gelesen habe. Für praktisch eingesetzte Bäume, deren Tiefe man nicht garantieren kann, wie z.B. Spreizbäume, wäre das doch vielleicht eine Idee, zum Standardverfahren zu werden. Tragfähig ist das auf jeden Fall. Die Cache-Lokalität ist ein wenig doof.

hustbaer

Nur ein kleiner Tip:
Wenn man den Baum einfach nur aufbaut und dann verwendet, dazwischen aber keine Änderungen macht, dann kann man schön nen std::vector<Node> verwenden.
Statt Zeiger hat man dann Vektor-Indizes.
Damit sollte nicht nur das Freigeben sehr schnell gehen sondern auch das Aufbauen.
Lookups werden ein wenig leiden, wegen der geringfügig aufwändigeren Adressierung der Nodes.

Bzw. wenn man keine stabilen Node-Iteratoren braucht kann man damit vermutlich sogar einen änderbaren Baum schön hinbekommen.

Ethon

Du hast vor x mal operator delete aufzurufen und verdächtigst die rekursiven Aufrufe zu imperformant zu sein?
Schau doch mal bitte erstmal nach wie lange ein delete braucht.

Wenn es wirklich performant sein soll dann muss man sowieso nen Pool für die Nodes verwenden und fickt nicht mit new/delete rum. Ein Pool bringt immerhin sauschnelle Allokation, optimale Cache-Lokalität und je nach Inhalt der Nodes auch sauschnelle Deallokation.

volkard

Habs lokaler gekriegt (normalerweise).

~bstree()
{
    if(!root) return;//einfach gut, weil doch viele 
        //Destruktor-Aufrufe auf einem leeren bstree geschehen. 
    Node* r=root;
    while(r){
        if(!r.left){//weg
            Node* toDie=r;
            r=r->right;
            delete toDie;
        }
        else if(!r.right){//weg
            Node* toDie=r;
            r=r->left;
            delete toDie;
        }
        else{//rotieren an der root! Die wird nämlich als nächstes bearbeitet. 
//Ist jetzt ein Stack statt einer Queue für die vertagten Jobs. 
//Gute Vermutung, daß Löschungen relativ nah nach Rotierungen kommen, 
//also der Mist noch im Cache ist. Perfekt für Bäume, die "quasi" ballanciert 
//sind, in normalen Anwendungsfällen "quasi" immer, aber man kann's 
//nicht garantieren. 
            Node* e=r->left->right;
            Node* newR=r->left;
            newR->right=r;
            r->left=e;
            r=newR;
        }
    }
}
//ungetestet

Ethon

if(!root) return;//einfach gut, weil doch viele
        //Destruktor-Aufrufe auf einem leeren bstree geschehen.

Aber dir ist doch sicher klar dass die logisch komplett äquivalente Abfrage 2 Zeilen darunter sowieso durchgeführt wird und das Ganze keinen Takt langsamer ist?

volkard

Ethon schrieb:

if(!root) return;//einfach gut, weil doch viele
        //Destruktor-Aufrufe auf einem leeren bstree geschehen.
Aber dir ist doch sicher klar dass die logisch komplett äquivalente Abfrage 2 Zeilen darunter sowieso durchgeführt wird und das Ganze keinen Takt langsamer ist?

Uups!!!

Wie offensichtlich!!!
*lach*

Habe mich ums Rotieren gequält. Bäume sind nicht mein Ding eigentlich. Fast immer gibt es bessere Alternativen. War heldenfroh, es gepackt zu haben. Habe zwar sofort gesehen, daß es so möglich ist, Algos mögen mich irgendwie, aber die Reihenfolge der elemetaren Zuweisungen, nööö, da habe ich keine Intuition. Eher eine Drecksintuition. Hätte an der Hochschule bleiben müssen, damit Doktoranden für mich den lästigen Quark ausarbeiten. *hihi*

Produktivcode wäre das nicht bei mir geworden. Ich schaue mir immer was funktionierendes nochmal später an. Wobei ich dem gcc sogar zutraue, daß er das auch packt, der ist ein Monster.

camper

volkard schrieb:

Wobei ich dem gcc sogar zutraue, daß er das auch packt, der ist ein Monster.

Für den rb-tree jedenfalls nicht, da arbeitet der Algorithmus rekursiv (in-oder mit ausgeschriebener Tail-Rekursion). Da der Baum immer ausbalanciert ist, kann man hier Stacküberläufe ausschliessen. Wie es mit internen Datenstrukturen des Compilers aussieht, weiss ich nicht.

aus /usr/lib/gcc/x86_64-pc-linux-gnu/4.8.1/include/g++-v4/bits/stl_tree.h

template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_erase(_Link_type __x)
    {
      // Erase without rebalancing.
      while (__x != 0)
        {
          _M_erase(_S_right(__x));
          _Link_type __y = _S_left(__x);
          _M_destroy_node(__x);
          __x = __y;
        }
    }