|
Wirbeltraversierung   Wirbeltraversierung bezeichnet in der Informatik einen speichereffizienten iterativen Algorithmus zur Untersuchung aller Knoten eines Binärbaumes.  BeschreibungDer Algorithmus wurde unabhängig voneinander von Lindstrom[1] und Dwyer[2] publiziert. Er traversiert einen gegebenen Binärbaum. Durch den Einsatz von Zeiger-Inversion (link reversal, nach Schorr/Waite)[3] 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[4][5] ("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 ( ImplementierungEine 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 Aufzählungsreihenfolgen und BesuchsaktionenDer 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-,[7] in-[8] oder post-order-Traversierung[9] nicht ohne weiteres implementiert werden; dies erfordert einen zusätzlichen 2 Bits breiten Besuchszähler in jedem Knoten.[4] 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 #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 Lässt sich die gewünschte Aktion f als dreifach iterierte Funktion[10] f = g∘g∘g darstellen, so kann eine Implementierung von g als Literatur
|