Binary Search Tree, Speicher wieder freiegeben

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;
        }
    }

volkard

camper schrieb:

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. Da der Baum immer ausbalanciert ist, kann man hier Stacküberläufe ausschliessen. Wie es mit internen Datenstrukturen des Compilers aussieht, weiss ich nicht.

Ich meinte, das dumme if wegzuoptimieren. Aus dem rekursiven Löschen soll er gar keine andere Version bauen.

camper

~~Man kann das if auch funktional machen.~~ Wobei ich bezweifle, dass diese Optimierung irgendeinen messbaren Einfluss hat. wie üblich ungetestet.

~bstree()
{
    auto die = [](Node* p, Node* next) { delete p; return next; };
    Node* r=root;
    while(r){
        if(!r->left) {
_:          die( r, r->right );
            continue;
        }
        if(!r->right) {
            die( r, r->left );
            continue;
        }
        do {
            Node* e=r->left->right;
            Node* newR=r->left;
            newR->right=r;
            r->left=e;
            r=newR;
        } while ( r->left );
        goto _;
    }
}

Edit: nochmal überarbeitet. Jetzt ist der Anfangstest doch nicht nötig.

Columbo

Laesst sich das nicht vereinfachen zu

Node* r=root;
    while(r){
        if( !r->left || !r->right ) {
_:          delete r;
            continue;
        }
\\ ...

Oder uebersehe ich etwas?

volkard

camper schrieb:

~~Man kann das if auch funktional machen.~~ Wobei ich bezweifle, dass diese Optimierung irgendeinen messbaren Einfluss hat. wie üblich ungetestet.
~bstree()
{
    auto die = [](Node* p, Node* next) { delete p; return next; };
    Node* r=root;
    while(r){
        if(!r->left) {
_:          die( r, r->right );
            continue;
        }
        if(!r->right) {
            die( r, r->left );
            continue;
        }
        do {
            Node* e=r->left->right;
            Node* newR=r->left;
            newR->right=r;
            r->left=e;
            r=newR;
        } while ( r->left );
        goto _;
    }
}
Edit: nochmal überarbeitet. Jetzt ist der Anfangstest doch nicht nötig.

Hab zweimal r= zugefügt.

~bstree()
{
    auto die = [](Node* p, Node* next) { delete p; return next; };
    Node* r=root;
    while(r){
        if(!r->left) {
_:          r=die( r, r->right );
            continue;
        }
        if(!r->right) {
            r=die( r, r->left );
            continue;
        }
        do {
            Node* e=r->left->right;
            Node* newR=r->left;
            newR->right=r;
            r->left=e;
            r=newR;
        } while ( r->left );
        goto _;
    }
}

camper

Arcoth schrieb:

Laesst sich das nicht vereinfachen zu
...

Je nachdem, welcher Kindknoten nicht existiert, ändert sich, in welche Richtung weiterzulaufen ist.

volkard schrieb:

Hab zweimal r= zugefügt.

danke, so war es gemeint. und das goto ist auch unnötig.

~bstree()
{
    auto die = [](Node* p, Node* next) { delete p; return next; };
    Node* r = root;
    while ( r ) {
        if ( !r->right ) {
            r = die( r, r->left );
        }
        else {
            while ( r->left ) {
                Node* e = r->left->right;
                Node* newR = r->left;
                newR->right = r;
                r->left = e;
                r = newR;
            }
            r = die( r, r->right );
        }
    }
}