Diskussion:Wirbeltraversierung
So ist das unverständlich, ich hab auch nen Baum im Garten und den kann ich sooft besuchen wie ich will ohne irgendwelche Konten zu terrasieren. --tox 23:42, 19. Feb 2006 (CET)
ich hab ja leider nicht so viel ahnung davon und würde mich halt freuen, wenn jemand noch mehr dazu schreiben könnte --Master-2000 23:44, 19. Feb 2006 (CET)
- Man soll aber nur von etwas schreiben von dem man eine Ahnung hat. Für Artikelwünsche gibt es Wikipedia:Artikelwünsche.--tox 23:53, 19. Feb 2006 (CET)
ich dachte, ein anfang wäre besser als gar nichts!! --Master-2000 23:56, 19. Feb 2006 (CET)
Ein paar Fragen zur Version vom 11.03.2020
[Quelltext bearbeiten]- Ich nehme an, doppelt verkettet bedeutet: es gibt einen parent Pointer. (Das ist stärker als ein Stack (Kellerspeicher), in den meisten praktischen Fällen gleichwertig.)
- Das mit dem modulo 3 verstehe ich nicht ganz. Bedeutet das, dass ein Knoten nach 3 Besuchen wieder unbesucht ist?
- Für mich kommt in
wTravnicht heraus, auf welche Weise die iterative Traversierung effektiv bewerkstelligt wird. - Deshalb kann ich auch nicht erkennen, wie bspw. bei einem Blatt, das bei einer Traversierung eigentlich nur einmal besucht wird, auf 3 gezählt wird.
Vielleicht ist der Algorithmus im Ergebnis ganz ähnlich wie der untenstehende meinige namens iterativePreInPostOrder, bei dem die Traversierung
- iterativ voll ausprogrammiert ist,
- jede der Positionen pre-, in- resp. post-order "vom Algorithmus automatisch" erkannt wird,
- überhaupt kein zusätzlicher Speicher benötigt wird. Statt parent könnte auch hier ein Stack mit h Elementen genommen werden.
The following code example shows an iteratively programmed traversal which supports all three sequentialisations in a single orbit. On its right half there is a trace of the visits of nodes in a traversal of the tree in figure Depth-first traversal im Artikel en:User:Nomen4Omen/sandbox. Thereby, a visit consists of an arrow (essentially down or up) followed by the current name (key) of the node N. This is optionally followed by the letters L, R or P which describes the relationship of the node next to the current node N, such that e. g. P means: next is parent of N. A horizontal arrow → is immediately followed by a print statement for the in-order position.
typedef struct mynode mynode;
struct mynode
{
mynode* L; // -> left child
mynode* R; // -> right child
mynode* P; // -> parent node
int value; // user data
};
void iterativePreInPostOrder(mynode* N)
// N shall be the root of the subtree to be traversed.
{
(mynode*) next, anchor;
if ((next = N) == NULL) return;
anchor = N->P; // assuming that no other node has (N->P == anchor)
DL:
/* Try to loop down some left spine, i.e.
all available left (grand)children until there is none. */
N = next; // ↓0↓-3↓-4↓-5↓-1↓-2↓+3↓+1↓+2↓+4↓+5
printf("pre-order: [%d] ", N->value); // N is in pre-order position
if ((next = N->L) != NULL)
/* N has a left child */ // ↓0L-3↓-3L-4↓-4L-5↓-1L-2↓+3L+1
goto DL;
/* N has no left child. */ // →-5→-2→+1→+2→+4→+5
printf("in-order: [%d] ", N->value); // N is in in-order position
if ((next = N->R) != NULL)
/* N has (no left, but) a right child. */ // ↓+1R+2↓+4R+5
goto DL;
/* N has no child at all. */ // ↑-5↑-2↑+2↑+5
goto UD;
DU: /* N is left child of next. */ // ↑-5P-4↑-4P-3↑-2P-1↑-3P0↑+1P+3
N = next; /* N has a left child. */ // →-4→-3→-1→0→+3
printf("in-order: [%d] ", N->value); // N is in in-order position
if ((next = N->R) != NULL)
/* N has (a left and) a right child. */ // ↘-3R-1↘0R+3↘+3R+4↘+4R+5
goto DL;
/* N has a left child, but no right child. */ // ↑-4↑-1
UD /* N has no child at all. */ /*+ ↑-5↑-2↑+2↑+5 */ :
: /* N has no right child. */ // ↑-5↑-4↑-2↑-1↑+2↑+5
printf("post-order: [%d] ", N->value); // N is in post-order position
next = N->P; // ↗-5P-4↗-4P-3↗-2P-1↗-1P-3↗+2P+1↗+5P+4
UL /* Non-root N has a right child. */ /*+ ↗-3P0↗+1P+3↗+4P+3↗+3P0 */ :
: // ↗-5P-4↗-4P-3↗-2P-1↗-1P-3↗-3P0↗+2P+1↗+1P+3↗+5P+4↗+4P+3↗+3P0
/* Try to loop up some right spine, i.e.
all available left (grand)parents until there is none. */
if (N == next->L)
/* N is the left child of next. */ // ↑-5P-4↑-4P-3↑-2P-1↑-3P0↑+1P+3
goto DU;
/* N is the right child of next. */
N = next; /* N has a right child. */ // ↑-3↑+1↑+4↑+3↑0
printf("post-order: [%d] ", N->value); // N is in post-order position
if ((next = N->P) // ↗-3P0↗+1P+3↗+4P+3↗+3P0↗0P–
!= anchor) /* N is not the root. */ // ↗-3P0↗+1P+3↗+4P+3↗+3P0
goto UL;
/* N is the root. */ // ↗0P–
return;
}
Zugegeben, der Algorithmus ist am kürzesten, wenn er goto enthält, und muss sehr sorgfältig durchgelesen werden. Ich habe ihn per einmaligem Traversieren des Baums in der figure "bewiesen". In ihm kommen alle charakteristischen Konstellationen vor.
Im Hauptartikel bin ich auch weiter gekommen. Ich habe für pre-, in-, post-order traversal bei Pfaff etwas gefunden, was man als eine Art Definition auffassen kann. Im Effekt würde das bedeuten, dass nicht jede Traversierung mit einem der 3 Stempel versehen werden kann. Z.B. wäre die Dupliziertraversierung zwar eine Traversierung, könnte aber nicht als eine der 3 aufgefasst werden. Du hast ja sowas schon mal ausgesprochen. Mein volles iterativePreInPostOrder gehört sicherlich auch nicht da rein, obwohl man, wenn man kein in-order und kein post-order printf macht, es ein reines pre-order traversal ist. Gleiches scheint mir für wTrav zuzutreffen.
Erwarte Deine Antwort. Gruß und bis bald. --Nomen4Omen (Diskussion) 20:44, 11. Mär. 2020 (CET)
- Ja, der Algorithmus braucht den parent Pointer.
- Ja, nach dem dritten Besuch ist die Traversierung fuer den Knoten und den Unterbaum darunter abgeschlossen.
- Die "herkoemmlichen" Algorithmen verfolgen nach dem ersten Besuch den Left-Zeiger, nach dem zweiten den Right-Zeiger und gehen nach dem dritten Besuch zurueck zum Parent-Knoten (meist mit Stack; hier ginge aber eben auch Verfolgen des Parent-Zeigers). Wirbeltraversierung rotiert die drei Zeiger nach jedem Besuch um 120 Grad gegen den Uhrzeigersinn (vgl. Bilder) und verfolgt dann stets den Parent-Zeiger. Im C-Programm werden die Zeiger nicht wirklich im Array
ptrumkopiert; stattdessen wird die Rotation uebercntrealisiert. - Bei einem Blatt wird zweimal
nxt==NULLfestgestellt, so dasscurzweimal unveraendert bleibt. Dadurch wird es dreimal besucht, je einmal mitcnt=0,1,2. Danach wird der parent-Zeiger verfolgt (der natuerlich nicht NULL ist).
visit wird uebrigens fuer jeden Knoten dreimal aufgerufen, je einmal mit cnt=0,1,2, entsprechend der pre-/in-/post-order-Operation.
Den Hauptartikel koennen wir gerne weiter wie bisher auf meiner Diskussionsseite besprechen; ich wollte dort den Fluss nicht mit Wirbeltraversierung unterbrechen.
Deinen Algorithmus verstehe ich nicht ganz. Anscheinend merkst Du Dir beim Betreten eines Knotens, von wo Du gekommen bist, und bestimmst daraus, wohin Du als naechstes gehen musst. Aber wenn Du von unten kommst, weisst Du doch nicht, ob vom linken oder vom rechten Unterbaum, und muesstest also die Adresse des zuvor besuchten Knotens vergleichen mit ->L und ->R; das habe ich im Code aber nicht wiedergefunden. - Wenn Dein Algorithmus tatsaechlich funktioniert und wenn ich den Wirbelalgorithmus tatsaechlich aus dem Gedaechtnis richtig rekonstruiert habe, ist es kein Wunder, dass letzterer von der Bildflaeche verschwunden ist. - Jochen Burghardt (Diskussion) 22:06, 11. Mär. 2020 (CET)
- Zu 1: Na ja, in den allermeisten Fällen kann man den parent Pointer durch einen Stack ersetzen. Das sieht man vllt, wenn
wTravwirklich ausprogrammiert ist. Könntest Du das mal machen? - Zu 2: Wahrscheinlich hast Du Recht. Trotzdem bedeutet "unbesucht" natürlich nicht dasselbe wie "3 mal besucht".
- Zu 3: In diesem Sinn ist
iterativePreInPostOrderübrigens herkömmlich. Siehe dazu ganz unten. - Zu 4: Ich sehe! Das ist dann ganz ähnlich wie in
iterativePreInPostOrder.
Ich bin einverstanden mit der Trennung Hauptartikel vs. Wirbeltraversierung.
Nein, der Algorithmus iterativePreInPostOrder merkt sich nichts. Er weiß von woher er kommt. Und ob von linken oder rechten Teilbaum, ist eine ganz einfache Abfrage if (N == next->L). Ich habe den Eindruck, dass es sein könnte wie bei Dir (wobei mir die echte Ausführung von wTrav allerdings fehlt). Der Algorithmus geht immer nur vorwärts:
- Knoten wird als Kind (egal, ob L oder R) absteigend zum ersten Mal betreten. ==> pre-order
- Hat er ein linkes Kind, dann wird dieses besucht - in der Gewissheit dass wir wiederkommen, dann aber von unten von einem linken Kind. (Das ist die Abfrage
if (N == next->L)mit dem Ergebnis TRUE.) - Danach folgt die in-order Position, die sofort gekommen wäre, wenn es das linke Kind nicht gibt. ==> in-order
- Dann wird nach dem rechten Kind gefragt. Gibt es dieses, dann wird es besucht - in der Gewissheit dass wir wiederkommen, dann aber von unten von einem rechten Kind. (Das ist die Abfrage
if (N == next->L)mit dem Ergebnis FALSE.) - Danach folgt die post-order Position, die sofort gekommen wäre, wenn es das rechte Kind nicht gibt. ==> post-order
Wenn Du wTrav mal ausprogrammiert hast, sieht man vllt, dass sich dort genau dasselbe abspielt, – und dass auch Du den cnt nicht wirklich brauchst. Besten Gruß, --Nomen4Omen (Diskussion) 23:02, 11. Mär. 2020 (CET)
Ich hab es ausprogrammiert und laufen lassen, bevor ich den Code auf der Seite gezeigt hab. Was fuer ein komplettes C-Programm noch fehlt, steht hier:
#include <stdio.h>
void visit(struct _node *tree) {
const char * const name[3] = { "pre ", "in ", "post" };
printf("visit %s %d\n",name[tree->cnt],tree->key);
}
struct _node m[10] = {
/* par lft rgt */
/*0*/ { 0, 0, {NULL , NULL , NULL } },
/*1*/ { 0, 1, {NULL , &m[2], &m[3]} },
/*2*/ { 0, 2, {&m[1], &m[4], &m[5]} },
/*3*/ { 0, 3, {&m[1], &m[6], NULL } },
/*4*/ { 0, 4, {&m[2], NULL , NULL } },
/*5*/ { 0, 5, {&m[2], NULL , &m[7]} },
/*6*/ { 0, 6, {&m[3], &m[8], &m[9]} },
/*7*/ { 0, 7, {&m[5], NULL , NULL } },
/*8*/ { 0, 8, {&m[6], NULL , NULL } },
/*9*/ { 0, 9, {&m[6], NULL , NULL } },
};
int main(void) {
wTrav(&m[1]);
return 0;
}
Das Ergebnis eines Laufs sieht bei mir so aus:
visit pre 1 visit pre 2 visit pre 4 visit in 4 visit post 4 visit in 2 visit pre 5 visit in 5 visit pre 7 visit in 7 visit post 7 visit post 5 visit post 2 visit in 1 visit pre 3 visit pre 6 visit pre 8 visit in 8 visit post 8 visit in 6 visit pre 9 visit in 9 visit post 9 visit post 6 visit in 3 visit post 3 visit post 1
Der Baum in m[] sieht so aus:
1
/ \
/ \
2 3
/ \ /
4 5 6
\ / \
7 8 9
Bei der Invariante bzgl. cnt hab ich mich schlampig ausgedrueckt. cnt enthaelt genau genommen nicht die Anzahl der Besuche, sonderen diese Anzahl mod 3. Fuer den Algorithmus genuegt das. Ich habe, wie gesagt, den Algorithmus aus dem Gedaechnis rekonstruiert (es hat einige Tests und Modifikationen gebraucht, bis er den richtigen Output erzeugt hat). Sicher bin ich nur, den Namen "Wirbeltraversierung" mal gelesen und dazu in etwas die Bilder auf der Seite gesehen zu haben, mit den verwirbelten Zeigern. Bei Google findet man unter "Wirbeltraversierung" nur diese Seite. Immerhin scheint sich Master-2000 auch an den Namen erinnert zu haben.
In Deinem Algorithmus hatte ich die Abfrage if (N == next->L) uebersehen bzw. an den falschen Stellen gesucht. Dank Deiner Erklaerung verstehe ich ihn jetzt so ungefaehr. Er hat gegenueber der Wirbeltraversierung tatsaechlich nur Vorteile. Du hast ihn Dir doch nicht etwa selbst ausgedacht? Falls doch, publiziere ihn schnell (z.B. als Technical Report bei ArXiv)! In jedem Fall sollte er letztendlich auf en:tree traversal erscheinen (als ich mich gegen iterative Algorithmen dort ausgesprochen habe, habe ich nicht bedacht, dass es welche geben koennte, die ohne Stack auskommen). Uebrigens koennte ich mir vorstellen, dass er auf die parent-Zeiger auch noch verzichten kann: wenn er den Zeiger, den er nach unten verfolgt, in einer lokalen Variable speichert und das Zeigerfeld im Knoten auf den parent setzt (den er aus einer anderen lokalen Variablen entnimmt). - Gruss Jochen Burghardt (Diskussion) 12:35, 12. Mär. 2020 (CET)
@Jochen Burghardt:
Deinen Algorithmus verstehe ich jetzt auch besser. Er steuert aktiv über die Kind-pointer auf den Rest des Baums zu. Wenn nicht Modulo gearbeitet würde, müsste der Nachweis erbracht werden, dass ein Knoten mit cnt == 3 nicht (nochmal) angefasst wird. Und das ist natürlich so: (wie Du schon sagtest): "Fuer den Algorithmus genuegt das."
Das ist bei mir im Grund dasselbe. Wobei bei mir die Schleife sehr anders aufgedröselt ist und die Nähe zur rekursiven Version fast nicht mehr erkennbar. Ja, er ist von mir. Ich bin auf ihn gekommen, weil bei anderen Leuten die iterativen pre-, in-, post-order Algorithmen so außerordentlich verschieden ausfallen, wo doch der rekursive problemlos alle 3 nebeneinander enthält. Natürlich weiß ich nicht, ob's ihn in der weiten Welt sonstwo noch gibt. Ich habe auch einen Fehler gefunden: Wenn die Wurzel nur ein linkes Kind hat, dann findet er das Ende nicht. Es ist nicht schwer, das zu verbessern. Dabei fiel mir auch auf, dass ich das zweifache Vorkommen von printf in-order sowie von printf post-order jeweils in ein einfaches zusammenführen kann. Das mit dem ancestor stack sehe ich nicht dramatisch: Er enthält höchstens so viele Elemente wie Knoten, und in den "guten", balancierten Fällen nur logarithmisch viele. Nicht ganz unwichtig finde ich auch, dass der Stack lokal im Traversierprogramm bleiben kann (und nicht nach unten oder außen weitergegeben werden muss.) Daran, dass man den parent in dieser Schleife lokal speichern kann, glaube ich nicht so recht, denn die lokalen Variablen werden durch die Schleife völlig aus ihrem Kontext herausgerissen. Auch Folgendes geht nicht: den parent am Platz des Kindes, zu dem man hinabzusteigen im Begriff ist, ablegen. Und nachher, wenn man von diesem Kind aufsteigt (zurückkommt), ihn dort abgreifen und sofort den Kind-Zeiger restaurieren. Denn wie soll dann die Abfrage if (N == next->L) funktionieren? Aber ein Bit würde helfen, in dem festgehalten wird, ob ein Knoten linkes oder rechtes Kind ist (chirality bit).
Ich muss die korrigierte Version noch überprüfen. Dann stelle ich sie hier rein. Das mit ArXiv habe ich noch nie gemacht. Würde ich gerne, denn auch ich bin dafür, dass er in en:tree traversal reinkommt. Ohne ArXiv müsste ich behaupten, dass er zB bei Pfaff vorkommt – nur halt ein bisschen umgebastelt ist. - Viele Grüße, Nomen4Omen (Diskussion) 17:06, 12. Mär. 2020 (CET)
Literatur
[Quelltext bearbeiten]Auf der Suche nach einschlaegiger Literatur bin ich auf folgendes gestossen:
- W.A. Burkhard: Nonrecursive traversals of trees. In: The Computer Journal. Band 18, Nr. 3, 1975, S. 227–230 (online).
- 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).
- T.I. Fenner and G. Loizou: Loop-free algorithms for traversing binary trees. In: BIT Numerical Mathematics. Band 24, 33–44, 1984.
- Dan S. Hirschberg and S.S. Seiden: A Bounded-Space Tree Traversal Algorithm. In: Information Processing Letters. Band 47, Nr. 4, September 1993, S. 215–219 (online [PDF]).
- G. Lindstrom: Scanning list structures without stacks or tag bits. In: Info. Process. Lett. Band 2, 1973, S. 47–51.
- Prabhaker Mateti and Ravi Manghirmalani: Morris' tree traversal algorithm reconsidered. In: Science of Computer Programming. Band 11, Nr. 1, Oktober 1988, S. 29–43 (online).
- Morris, Joseph H.: 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.
- S. Soule: A note on the nonrecursive traversal of binary trees. In: The Computer Journal. Band 20, Nr. 4, 1977, S. 350–352 (online).
Insbesondere Hirschberg.Seiden.1993 scheint eine Konkurrenz zu Deinem Algorithmus. - Jochen Burghardt (Diskussion) 16:19, 12. Mär. 2020 (CET)
@Jochen Burghardt: So isses! Hirschberg.Seiden.1993 ist eine Konkurrenz zu meinem Algorithmus. Er geht sogar darüber hinaus, indem er sowohl Stack spart. Das von mir oben erwähnte chirality bit machen sie mit adress-mäßigem Umordnen von linkem und rechtem Kind, so dass sie beim Hochkommen erkennen können, ob von links oder rechts. (Da ist mir ein chirality bit allerdings lieber.) Was sie auch haben: alle 3 Standard-Sorten (pre, in, post) können ein einem einzigen traversal gefahren werden. Sehr gut! --Nomen4Omen (Diskussion) 17:42, 12. Mär. 2020 (CET)
@Nomen4Omen: Meine Hochachtung zu Deinem eigenen Algorithmus - und mein Beileid zur besseren Konkurrenz. Ist mir auch schon passiert. Manchmal laesst sich noch was retten; z.B. wenn Du einen Anwendungsbereich finden koenntest, in dem Dein Algorithmus eben doch besser als Hirschberg.Seiden.1993 ist (nur wenige verschiedene Knotenlabel, stark unbalancierte Baeume, ... - das sind Phantasiebeipiele, denn ich kenne Hirschberg.Seiden.1993 im Detail noch gar nicht und Deinen Algorithmus nicht restlos genau). Wie man ein Dokument in LaTeX bei ArXiv einreicht, damit hab ich Erfahrung. - Jochen Burghardt (Diskussion) 20:34, 12. Mär. 2020 (CET)
@Jochen Burghardt: Vielen Dank für die Blumen! Aber mir ist schon klar, dass die "Erfindungshöhe" meines Algorithmus nicht so umwerfend ist. Ich meine auch beim Überfliegen von Hirschberg.Seiden.1993 gesehen zu haben, dass sie sich schon auf andere stützen. M.a.W. so einmalig großartig ist das nicht. NB: Das mit dem adress-mäßigen Umordnen gefällt mir überhaupt nicht, denn damit wird ernsthaft in die Benutzerdaten eingegriffen, die Generizität also aufgegeben. Bspw. geht das gar nicht, wenn die Knoten unterschiedlich viel Platz brauchen. Aber das ist eigentlich ein Nebenkriegsschauplatz. Was könnten die Reize meines Algorithmus sein?
- iterativ.
- sehr flexibel einsetzbar: man kann pre-, in- oder post-order daraus machen oder auch Kombinationen davon.
- wenn parent-Zeiger nicht sowieso schon da sind, dann 1 zusätzliches Bit pro Knoten; oder ein Stack mit im günstigen Fall logarithmischer Größe.
Ich mach aber diesen Sack noch zu. Danke auch für die gute Literatur-Recherche. -Nomen4Omen (Diskussion) 22:04, 12. Mär. 2020 (CET)
@Nomen4Omen: Habe inzwischen auch den Hirschberg ueberflogen und finde ihn nicht mehr so toll. Weitere Nachteile (ausser den von Dir genannten) sind: Zeiger von ausserhalb des Baumes in ihn hinein (gespeicherte Suchergebnisse etwa) verlieren ihre Gueltigkeit; bei grossen (d.h. viel Speicherplatz benoetigenden) Keys kopiert sich der Algorithmus zu Tode. Dann doch lieber irgendwo noch ein Chirality-Bit abknapsen!
Ich hab jetzt auch endlich Referenzen zur Wirbeltraversieung gefunden, naemlich Dwyer.1974 und Lindstrom.1973. Sie sind selbst nicht kostenlos zugaenglich, werden aber zitiert in Mcjones.Stepanov.2019 S.143 und Manghirmalani.Mateti.1988 S.30. Letztere erwaehnen die Zeigerrotation wie in den Bildern, erstere zeigen C++ Source Code. Anders als ich dachte, brauchen sie keine parent-Zeiger, sondern setzen "link reversal" ein. Auch mein cnt-Feld brauchen sie nicht unbedingt, sondern nur dann, wenn sie bei jedem Besuch wissen wollen, der wievielte es gerade ist. Ich werde den Artikel demnaechst entsprechend abaendern. Der nach C uebersetzte und (aus Faulheit an meiner alten Datenstruktur,
aber ohne Verwendung der parent-Felder in m[]) ausprobierte Code sieht so aus:
#define LF 1
#define RG 2
static inline void swRot(struct _node **cur,struct _node **prv) { /* tree_rotate */
struct _node * const tmp = (*cur)->ptr[LF];
(*cur)->ptr[LF] = (*cur)->ptr[RG];
(*cur)->ptr[RG] = *prv;
if (tmp == NULL) {
*prv = tmp;
} else {
*prv = *cur;
*cur = tmp;
}
}
static inline void swTrav(struct _node *tree) { /* traverse_rotating */
struct _node *cur;
struct _node *prv;
if (tree == NULL)
return;
cur = tree;
do {
visit(cur);
swRot(&cur,&prv);
} while (cur != tree);
do {
visit(cur);
swRot(&cur,&prv);
} while (cur != tree);
visit(cur);
swRot(&cur,&prv);
}
int main(void) {
swTrav(&m[1]);
return 0;
}
Die erste do-Schleife traversiert den linken Unterbaum der Wurzel, sie stoppt, wenn die Wurzel in in-order-Position besucht wird.
Die zweite Schleife traversiert dann den analog rechten Unterbaum. Der letzte visit-Aufruf ist die post-order-Position fuer die Wurzel.
Meine Bildchen will ich neu zeichnen, sobald ich ganz verstanden habe, wie der bisherige parent-Zeiger durch das Paar cur/prv realisiert wird. - Jochen Burghardt (Diskussion) 15:21, 13. Mär. 2020 (CET)
@Jochen Burghardt: Bevor ich die neue Version von meinem Alg. bringe, vorab die folgenden Bemerkungen, die Dir vllt von Hilfe sein können. Für die Traversierung, die der von Dir vorgeschlagenen Ameise ("Ameisenweg") folgt, sind im Knoten für den Abstieg zu den Blättern die 2 Kind-Zeiger erforderlich (und wohl auch immer vorhanden). Für den Wiederaufstieg (in der Gegenrichtung der Kante (edge)) ist der Zeiger zum Elter und die Chiralität (ob ein Knoten linkes oder rechtes Kind ist) erforderlich. Die beiden können aus irgendwelchen Gründen schon vorhanden sein. Man kann sie sich aber auch beim Abstieg in einem Stapelspeicher (Stack) merken. Hat man den Elterzeiger (egal, ob im Knoten oder im Stack), dann hat man auch die Chiralität (durch den bekannten Vergleich der Zeiger beim Aufstieg). Hat man ihn nicht und will man sich auch keinen Stack dafür leisten, dann kann man sich den Elterzeiger im Abstieg an der Stelle desjenigen Kindzeigers, zu dem man absteigt, merken. Allerdings verliert man dann die Chiralität, weil der bekannte Vergleichs nicht mehr geht. Für die Chiralität gibt es dann m.E. die folgenden 3 Möglichkeiten (die Restauration des Kindzeigers gelingt beim Wiederaufstieg mithilfe der Chiralität!):
- Stack (1 Bit pro Level), also zus. space = O(h), zus time = O(n) [time war vorher schon O(n)]. Das ist m.E. äquivalent zu Deinem
cnt, der ja auch sowohl im Knoten wie in einem Stack gehalten werden kann. - Adress-"Inversion" (link reversal?) von Hirschberg.Seiden.1993 mit zus. space = O(1); aber zus time = O(n) [war vorher schon O(n)].
- Nochmal Vergleichen des key (von Kind und Elter) mit zus. space = O(1); zus time = O(n) [war vorher schon O(n)]. Das erfordert aber, dass der Baum ein Suchbaum ist und dass es keine Duplikate in ihm gibt.
Alle diese 3 Möglichkeiten sind in der Zeitkomplexität gleich. Der Rest des Algorithmus, der "Ameisenweg" ist im Prinzip davon unberührt. Viele Grüße - Nomen4Omen (Diskussion) 12:09, 14. Mär. 2020 (CET)
Ein paar Fragen zur Version vom 20. Mär. 2020
[Quelltext bearbeiten]Ich habe den Code zur Wirbeltraversierung (endlich!) ein bisschen näher angeschaut. (Ist auch nicht so super einfach zu verstehen.)
In der Funktion rotate fände ich eine Kennung der **-Variablennamen ganz gut, also entweder Pcur statt nur cur oder gar pCur vs. Cur in wTrav.
Zweitens meine ich beobachten zu können, dass ein globaler Zähler in wTrav zu jedem Knoten modulo 3 genau 3 verschiedene Werte auswirft, s. die untenstehende Tabelle, wo die 4. Spalte diesen Zähler und die 5. (gruppiert nach Knoten) den 3-er-Rest zeigt.
visit pre 1 1 1 visit pre 2 2 2 visit pre 4 3 0 visit in 4 4 1 visit post 4 5 2 visit in 2 6 0 visit pre 5 7 1 visit in 5 8 2 visit pre 7 9 0 visit in 7 10 1 visit post 7 11 2 visit post 5 12 0 visit post 2 13 1 visit in 1 14 2 visit pre 3 15 0 visit pre 6 16 1 visit pre 8 17 2 visit in 8 18 0 visit post 8 19 1 visit in 6 20 2 visit pre 9 21 0 visit in 9 22 1 visit post 9 23 2 visit post 6 24 0 visit in 3 25 1 visit post 3 26 2 visit post 1 27 0
Dieses Gesetz müsste man erstmal beweisen, was vielleicht nicht so schwer ist, weil man jeden Knoten, zu dem man abgestiegen ist, beim Wiederaufstieg genau 3 mal besucht hat.
Wenn man nun pro Knoten 2 Bits spendiert, die initial auf 3 gesetzt sind, könnte man beim ersten Besuch den Rest mod 3 (∈ [0,2]) des globalen Zählers reinschreiben und nachfolgende Besuche abhängig von (globalem Zähler abzüglich diesen Rest (wenn ≠ 3)) als in-order- resp. post-order-Besuch erkennen. Ob da vllt noch mehr rauszuholen ist? (Allerdings sollte man annehmen, dass Lindstrom und die vielen Asse solche Überlegungen auch schon angestellt haben.)
Ich habe auch eine neue Version in die Sandbox.
Beste Grüße - Nomen4Omen (Diskussion) 10:58, 25. Mär. 2020 (CET)
@Jochen Burghardt:
(1) Übrigens lässt sich nach meinen Beobachtungen wTrav wie folgt vereinfachen:
void wTrav(struct _node *tree) {
struct _node *prv = NULL; // stopper
struct _node *cur = tree;
if (tree == NULL)
return;
// traverse the whole tree
do {
visit(cur);
rotate(&prv,&cur);
} while (cur != NULL);
}
(2) Die in meinem Edit vom 25.03. vorgeschlagenen 2 Bits müssten sich, da man durch sie ja weiß, ob man aufsteigt oder absteigt, durch einen Stack ersetzen lassen. Allerdings ist die von Knuth initiierte Challenge ganz eindeutig auf das Auskommen OHNE jeden zusätzlichen Speicher ausgerichtet.
(3) Hast Du Zugriff auf die (vollständigen) Originalarbeiten?
Ich komme über https://www.sciencedirect.com/ nur bis zur ersten Seite. Danach kostet's.
Beste Grüße - Nomen4Omen (Diskussion) 11:27, 29. Mär. 2020 (CEST)
@Nomen4Omen: Ich war >1 Woche offline (technische Stoerung) und arbeite jetzt nach und nach die aufgelaufenen Mails etc. ab. Ich melde mich demnaechst wieder hier. Gruss - Jochen Burghardt (Diskussion) 15:24, 31. Mär. 2020 (CEST)
- Ueber die Variablennamen will ich nicht streiten. Meinen Geschmack trifft das "p" nicht; als Extremfall habe ich schon Programmierkonventionen gesehen, wo jede Variable mit dem Projektnamen und dem Typnamen beginnen musste, was Programmierfehler (wohl entgegen der Intention) nicht verhindert sondern (durch die unuebersichtlich langen Zeilen) eher beguenstigt hat.
- Deine Beobachtung mit dem globalen Zaehler finde ich interessant. Ich glaube, Deine Beweisidee ist die richtige (mit Induktion ueber die Baumhoehe). Mit 2-Extrabits kann man sich aber sowieso merken, wie oft man bei einem Knoten schon gewesen ist (mit 0 initialisieren und bei jedem Besuch hochzaehlen, groesser als 3 wird er ja nicht) und entsprechen die pre- (0), in- (1) oder postorder-Aktion (2) ausfuehren. Das nur aus dem globalen Zaehler alleine rauszukriegen, waere toll, aber vermutlich geht's nicht, auch wenn man die Information ueber den vorigen Knoten noch zur Verfuegung hat, oder? Vielleicht kann man Dank des Zaehlers irgendwie mit nur einem Extrabit auskommen?
- Ich hab den
wTravnur abgeschrieben (von C++ nach C uebersetzt). Deine Vereinfachung sieht ueberzeugend aus, ich lasse sie morgen mal durch meine Tests laufen. - Du meinst, die 2 Bits jeweils auf dem Stack speichern? Das spart gegenueber 2 Bits pro Knoten doch eine ganze Menge; Zusatzspeicher O(log n) statt O(n) im Mittel. Vielleicht gibt es Big-Data-Anwendungen, in denen das wichtig ist. Und das jetzt zusammen mit dem globalen Zaehler, kann man da nicht noch was rausquetschen?
- Zur Zeit komme ich bestimmt nicht an die Originalarbeiten. Wenn die Bibliotheken wieder aufmachen, kann ich es an der Uni versuchen. Was bei JSTOR angeboten wird, bekomme ich dort auf jeden Fall. Wenn ich was frei im Netz gefunden habe, hab ich den Link schon immer dazugeschrieben. - Jochen Burghardt (Diskussion) 23:47, 31. Mär. 2020 (CEST)
@Nomen4Omen: Die ACM Digital Library (https://dl.acm.org) ist wegen Corona generell freigeschaltet. Alle Artikel von dort koennen z.Zt. kostenlos runtergeladen werden. Dein vereinfachter Wirbeltraversierungsalgorithmus muss noch irgendeinen Bug haben: so, wie er da steht, liefert er einen Segmentation fault (NULL-Pointer-Dereferenzierung). Wenn ich die entsprechende Zeile in rotate(&cur,&prv) aendere, besucht er die Wurzel ein viertes Mal (evtl. auch oefter; ich breche beim 4.Mal ab). Vielleicht siehst Du sofort, wie Du das korrigieren kannst? Gruss - Jochen Burghardt (Diskussion) 20:20, 4. Apr. 2020 (CEST)
@Jochen Burghardt:
Erstens: Ich hätte gerne die Implementierung in
- "Traversing binary trees simply and cheaply" von Joseph M. Morris, 1979 in Information Processing Letters
angeschaut. In der ACM Digital Library scheint das nicht zu sein, und bei Elsevier würde das mich 17.02 € kosten.
Zweitens: Den Fehler in meinem rotate kann ich nicht finden: Ich habe es allerdings nicht mit C oder C++ getestet, sondern mit dem MuPAD-Interpreter. Dein Baum könnte dort wie folgt aussehen:
21
/ \
/ \
/ \
/ \
/ \
22 23
/ \ /
24 25 26
\ / \
27 28 29
In MuPAD Sprechweise bspw.:
- nil:=-1:
- tree:=array(21..29,21=[22,23],22=[24,25],23=[26,nil],24=[nil,nil],25=[nil,27],26=[28,29],27=[nil,nil],28=[nil,nil],29=[nil,nil]):
Dabei ist jeder Knoten charakterisiert durch einen Index (hier von 21 bis 29) und enthält genau 2 Zahlen (eingeschlossen in []), und eine Zahl ist entweder wieder ein Index von 21 bis 29 oder nil(<0). Die Wurzel 21 hat bspw. das linke Kind 22 und als rechtes 23. Mein rotate sieht so aus:
rotate := proc(LeRi) begin
sav := tree[LeRi[1]][1]:
tree[LeRi[1]][1] := tree[LeRi[1]][2]:
tree[LeRi[1]][2] := LeRi[2]:
if sav = nil then LeRi[2] := nil: // iff
else LeRi[2] := LeRi[1]: LeRi[1] := sav: end_if:
return(LeRi):
end_proc:
Das ist Deinem rotate so genau wie möglich nachempfunden: Das Argument LeRi[1] entspricht *cur und LeRi[2] *prv. Im Unterschied zu C kann man mehrteilige Objekte zurückgeben, also hier wieder LeRi[1] und LeRi[2]. Das Setzen des Anfangsknotens ist bspw.
LeRi := [21,-3]: // für die Wurzel, oder für den kleinen Test LeRi := [25,-3]:
Damit läuft die Wirbeltraversierung:
s := 0: while LeRi[1] >= 0 do: s := s+1: print(s,LeRi): LeRi := rotate(LeRi): end_while: // mit der Ausgabe beim kleinen Test: 1, [25, -3] 2, [25, -1] 3, [27, 25] 4, [27, -1] 5, [27, -1] 6, [25, 27]
Für den ganzen Baum
LeRi:=[21,-3]: s:=0:
erhalte ich die Ausgabe:
1, [21, -3] 2, [22, 21] 3, [24, 22] 4, [24, -1] 5, [24, -1] 6, [22, 24] 7, [25, 22] 8, [25, -1] 9, [27, 25] 10, [27, -1] 11, [27, -1] 12, [25, 27] 13, [22, 25] 14, [21, 22] 15, [23, 21] 16, [26, 23] 17, [28, 26] 18, [28, -1] 19, [28, -1] 20, [26, 28] 21, [29, 26] 22, [29, -1] 23, [29, -1] 24, [26, 29] 25, [23, 26] 26, [23, -1]
Ein Fehler, wie du ihn beschreibst, müsste nach meiner Deutung einem Knotenindex ≥0, aber außerhalb [21,29] entsprechen.
Ich hoffe, Du kannst das unschwer nachvollziehen und grüße Dich - Nomen4Omen (Diskussion) 15:25, 6. Apr. 2020 (CEST)
@Nomen4Omen: Die Information Processing Letters gibt's an der FU Berlin online. Man muss sich aber entweder an einen FU-Rechner einloggen oder einen VPN-Tunnel dorthin verwenden. Letzteres geht nur fuer FU-Angehoerige, worunter ich nicht falle. Sobald die FU wieder offen hat, kann ich den ersten Weg (wie schon oefters) verwenden.
Der Baum, bei dem hier der Fehler auftritt, hat nur einen Knoten, also bei Dir vielleicht 27. Ich hab auch die do-while-Schleife in wTrav in eine while-do-Schleife umgewandelt, aber ohne Erfolg. Wenn ich zu Beginn der Schleife die Werte von cur und prv ausgebe, sehe ich in jedem Durchlauf dasselbe: cur zeigt auf die Wurzel und prv ist NULL. Fuer diese Konstellation bringt rotate keine Aenderung, das kann ich auch manuell am C-Code nachvollziehen (anschaulich: wenn alle 3 Zeiger NULL sind, aendert sich nichts, wenn ich sie rotiere). Wie sieht denn Deine Ausgabe fuer diesen Baum aus? Vermutlich unterscheidet sich die Semantik des C- und des MuPAD-rotate in irgendeiner Nuance? Gruss - Jochen Burghardt (Diskussion) 19:38, 6. Apr. 2020 (CEST)
Tatsächlich gab's bei mir manchmal auch Probleme. Wenn ich's recht beurteile, scheint es eher mit der nicht so großen Resilienz der Wirbeltraversierung zu tun zu haben. Und das noch Einfachere ist oft das noch Bessere. Wie sieht's mit Folgendem aus ?
void wTrav(struct _node* cur) {
struct _node* prv = NULL; // stopper
// traverse the whole tree
while (cur != NULL) do {
visit(cur);
rotate(&prv,&cur);
};
}
Beste Grüße - Nomen4Omen (Diskussion) 16:48, 7. Apr. 2020 (CEST)
@Nomen4Omen: Das macht bei mir genau dieselben Probleme. In der Originalform (das "do" muss entfernt werden, damit dioe Syntax ok ist) gibt's einen Segmentation Fault in rotate; wenn ich dessen Argumente vertausche, laeuft wTrave beim Ein-Knoten-Baum in die Endlosschleife. Aber mit einem nicht-NULL-Stopper funktioniert's:
void wTrav(struct mynode* cur) {
if (cur == NULL)
return;
struct mynode stopper = { NULL, NULL, -99999999, -99999999 };
struct mynode* prv = &stopper;
// traverse the whole tree
while (cur != &stopper) {
visit(cur->key);
rotate(&cur,&prv);
}
}
Die allererste Abfrage ist haesslich, aber anscheinend nicht vermeidbar. - Jochen Burghardt (Diskussion) 19:32, 7. Apr. 2020 (CEST)
Es ist schon sehr erstaunlich für mich, wie empfindlich die Sache ist. Ich kann für die Anfangssituation keinen großen Unterschied zwischen Deinem swTrav und meinem wTrav erkennen. (Die Abbruchbedingungen sind natürlich verschieden.) - Nomen4Omen (Diskussion) 11:37, 8. Apr. 2020 (CEST)