Wirbeltraversierung

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

Noch unbesucht

Einmal besucht

Zweimal besucht

Wirbeltraversierung Beispiel

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.