Wirbeltraversierung bezeichnet in der Informatik einen speichereffizienten iterativen Algorithmus zur Untersuchung aller Knoten eines Binärbaumes.

Beschreibung

Der Algorithmus wurde unabhängig voneinander von Lindstrom und Dwyer publiziert. Er traversiert einen gegebenen Binärbaum. Durch den Einsatz von Zeiger-Inversion (link reversal, nach Schorr/Waite) kommt er ohne externen Kellerspeicher aus; er merkt sich den Weg zurück durch geschickte Modifikation der Baumzeiger.

Der Name "Wirbeltraversierung" kommt von der Vorstellung, jeder Knoten habe drei Zeiger (auf den Eltern-, den linken und den rechten Kindknoten) im Winkel von jeweils 120°, die bei jedem Besuch um 120° weitergedreht ("verwirbelt") werden, siehe Bilder. Der Algorithmus besucht jeden Knoten dreimal. Nach dem dritten Besuch ist der ursprüngliche Knotenzustand wiederhergestellt.

Tatsächlich im Baum gespeichert sind nur zwei Zeiger, die im Ausgangs- und im Endzustand auf das linke und rechte Kind zeigen (grün und blau im Bild). Der dritte (rot im Bild) existiert nur für den jeweils aktuellen Knoten und wird in lokalen Variablen (prv, cur) im Algorithmus (s. u.) gehalten.

Implementierung

Eine Implementierung in C kann wie folgt aussehen:

struct _node {
    int key;
    struct _node *left;
    struct _node *right;
};

extern void visit(struct _node *tree);

void rotate(struct _node **prv,struct _node **cur) {
    struct _node * const savedLeft = (*cur)->left;
    (*cur)->left  = (*cur)->right;
    (*cur)->right = *prv;
    if (savedLeft == NULL) {
        *prv = savedLeft;
    } else {
        *prv = *cur;
        *cur = savedLeft;
    }
}

void wTrav(struct _node *tree) {
    struct _node *prv;
    struct _node *cur = tree;
    if (tree == NULL)
        return;
    // traverse left subtree
    do {
        visit(cur);
        rotate(&prv,&cur);
    } while (cur != tree);
    // traverse right subtree
    do {
        visit(cur);
        rotate(&prv,&cur);
    } while (cur != tree);
    // final visit of root
    visit(cur);
    rotate(&prv,&cur);
}

Der letzte rotate-Aufruf kann den Effekt der visit-Aufrufe nicht mehr beeinflussen. Dennoch wird er benötigt, nämlich, um die Zeiger des Wurzelknotens wieder in ihre ursprüngliche Position zurückzurotieren.

Aufzählungsreihenfolgen und Besuchsaktionen

Der Algorithmus besucht jeden Knoten genau dreimal. In der oben gezeigten Form gibt es keine Möglichkeit, festzustellen, der wievielte Besuch beim aktuellen Knoten gerade stattfindet. Dadurch kann pre-, in- oder post-order-Traversierung nicht ohne weiteres implementiert werden; dies erfordert einen zusätzlichen 2 Bits breiten Besuchszähler in jedem Knoten.

Alternativ kann wenigstens pre-order-Traversierung durch Überschreiben der Knotendaten mit einem "ungültigen" Wert realisiert werden, sofern sie nach der Traversierung nicht mehr benötigt werden. Zum Beispiel mit der folgenden Implementierung von visit gibt der Traversierungsalgorithmus die Knotenwerte in pre-order aus (und zerstört sie dabei):

#define INVALID (-999999999) /* never used as key value */
void visit(struct _node *tree) {
    if (tree->key != INVALID) {
        printf(" %d",tree->key);
        tree->key = INVALID;
    }
}

Wenn die visit-Aktion idempotent ist, kann Wirbeltraversierung ohne weiteres eingesetzt werden; so z. B., um die Daten aller Knoten mit einem gegebenen Wert zu initialisieren. Bei großen Datenmengen pro Knoten muss allerdings bedacht werden, dass der Initialisierungsaufwand dreifach anfällt.

Lässt sich die gewünschte Aktion f als dreifach iterierte Funktion f = g∘g∘g darstellen, so kann eine Implementierung von g als visit eingesetzt werden. Um z. B. alle Knotenwerte eines Unterbaums zu inkrementieren, kann tree->key++ als Rumpf von visit verwendet werden, wenn später die Knotenwerte vor Verwendung durch 3 geteilt werden.

Literatur

  1. ↑ G. Lindstrom: Scanning list structures without stacks or tag bits. In: Information Processing Letters. Band 2, 1973, S. 47–51 (online).
  2. ↑ Barry Dwyer: Simple algorithms for traversing a tree without an auxiliary stack. In: Information Processing Letters. Band 2, Nr. 5, 1974, S. 143–145 (online).
  3. ↑ Herbert Schorr and William M. Waite: An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures. In: Communications of the ACM. Band 10, Nr. 8, August 1967, S. 501–506 (online [PDF]).
  4. 1 2 Prabhaker Mateti and Ravi Manghirmalani: Morris' tree traversal algorithm reconsidered. In: Science of Computer Programming. Band 11, Nr. 1, Oktober 1988, S. 29–43, Hier: S. 30 (online).
  5. ↑ Morris, Joseph M.: Traversing binary trees simply and cheaply. In: Information Processing Letters. Band 9, Nr. 5, Dezember 1979, S. 197–200, doi:10.1016/0020-0190(79)90068-1 (online [PDF]).
  6. ↑ Alexander Stepanov and Paul McJones: Elements of Programming. Semigroup Press, Palo Alto 2019, ISBN 978-0-578-22214-1, Hier: S. 143 (online [PDF]).
  7. ↑ Die "Untersuchungs"-Aktion findet nur beim ersten Besuch statt.
  8. ↑ nur beim zweiten
  9. ↑ Aktion nur beim dritten Besuch
  10. ↑ Ernst Schröder: Ueber iterirte Functionen. In: Mathematische Annalen. Band 3, Nr. 2, 1870, S. 296–322 (online). Siehe auch en:Iterated function.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.