Wie nennt man das?

[pillmuncher]

Wie nennt man das, wenn man alle überflüssigen Knoten aus einem Baum entfernt und so die Äste auf ein Minimum verkürzt?

Code: Alles auswählen

            o                  o
           / \                / \
          o   o      ->      o   C
         / \   \            / \
        o   B   C          A   B
       / 
      A   

Ich bilde mir ein, das schon mal gewusst zu haben, aber das Wort dafür fällt mir einfach nicht ein.

[__blackjack__]

Suchst Du eventuell das stutzen/beschneiden von Bäumen: https://de.wikipedia.org/wiki/Pruning ?

[pillmuncher]

@__blackjack__: Danke für die Antwort. Pruning ist eher das Abschneiden ganzer Äste um Suchräume zu begrenzen. Mir geht es bloß darum, verlinkte Listen aus dem Baum zu entfernen.

Kontext: Es geht wieder mal um Prolog. Während der Unifikation werden Variablen in einem Environment (dict) an Werte gebunden. Eine Struktur wie f(X), bei der X an g(Y), Y an Z und Z an [1, 2, 3] gebunden ist, soll als f(g([1, 2, 3])) ausgegeben werden. Dazu soll eine Kopie des Baums erzeugt werden, die Variablen also durch ihre Bindungen ersetzt werden:

Code: Alles auswählen

            f(X)          ->      f(g([1, 2, 3])
              |
             g(Y)
               |
               Z
               |
           [1, 2, 3]

Algorithmisch ist das ja einfach, ich weiß aber nicht wie ich die Funktion nennen soll. minimize()? compact()? condense()? recursively_replace_all_variables_with_their_bindings()? Momentan heißt sie shrink(): https://github.com/pillmuncher/yogic/bl ... ication.py (Zeile 38).

[nezzcarth]

Ich meine, ich hätte für allgemeinere Fälle dessen (d.h. für Graphen an sich, nicht nur fur Bäumen) irgendwo mal die Begriffe "edge lifting" oder einfach "smoothing" aufeschnappt. Ob das hier anwendbar ist, traue ich mich als Fachfremder jedoch nicht einzuschätzen.

[pillmuncher]

@nezzcarth: Danke! Graph Smoothing ist anscheinend ein gebräuchlicher Ausdrücke dafür:
https://en.wikipedia.org/wiki/Homeomorp ... _smoothing
https://mathworld.wolfram.com/GraphSmoothing.html