Ursprünglich sollte dieser Artikel über dynamische Datenstrukturen nur als Zweiteiler erscheinen. Es hat sich mittlerweile aber herausgestellt, daß es besser ist, ihn in weitere Teile zu splitten, da die Abschnitte sonst einfach zu lang werden. Wir bitten um Verständnis.
Die Vorteile der verketteten Liste sind damit auch schon genannt: sie ist dynamisch erweiterbar und leicht zu implementieren.
Zum Abschluß in der letzten Ausgabe stellte ich die Frage, was man mit einem zweiten Zeiger in derselben Datenstruktur anfangen könnte - die Antwort ist recht einfach: Man kann dadurch in zwei Richtungen (vorwärts und rückwärts) verketten.
typedef struct eintrag
{
int cd_nr; /* die CD-Nummer */
char titel[41], /* Der CD-Titel */
gruppe[41]; /* Die Gruppe */
struct eintrag *next; /* Zeiger auf den nächsten Eintrag */
struct eintrag *prev; /* Zeiger auf den vorigen Eintrag */
} Eintrag;
Was wir aber immer noch nicht erreichen können, ist, ein Element in unserer dynamischen Datentruktur wirklich schnell zu finden. Dies liegt daran, daß wir zum Suchen die Liste sequentiell durchlaufen müssen. Auch bei einem sortierten Einfügen brauchen wir auf diese Weise im Durchschnitt immer noch n/2 Vergleiche zum Auffinden des Elements.
Da die Äpfel in diesem Jahr wegen des schlechten Wetters noch nicht reif sind, haben wir keinen Geistesblitz zum Gravitationsgesetz, sondern uns fällt - natürlich viel genialer - die Struktur der Äste des über uns aufragenden Baums auf:
Das Nest stellt sozusagen unsere Daten dar, die wir wiederfinden wollen.
Man teilt also an jeder Astgabel die folgenden Astgabeln auf zwei Seiten auf. Denn diese sortiert sind, halbieren wir dadurch jedesmal die Anzahl der Astgabeln, die wir noch durchsuchen müssen.
Zum Sortieren könnten wir einfach sagen, daß alle Elemente, die lexikalisch kleiner sind als der aktuelle Eintrag, in den linken Teilbaum kommen. Dagegen kommen alle, die größer sind, in den rechten Teilbaum.
Unsere Struktur sieht also wie folgt aus:
typedef struct knoten
{
int cd_nr; /* die CD-Nummer */
char titel[41], /* Der CD-Titel */
gruppe[41]; /* Die Gruppe */
struct knoten *links; /* Zeiger auf den linken Teilbaum */
struct knoten *rechts; /* Zeiger auf den rechten Teilbaum */
} Knoten;
Da wir von jeder Astgabel aus jeweils zwei Möglichkeiten zur Verzweigung haben, nennt man diesen Typ von Baum (logischerweise) binären Baum.
Demnach heißt das erste Element ganz oben, an dem alle anderen Astgabeln hängen, Wurzel.
Die "Astgabel" nennt man normalerweise Knoten, was nicht ganz so abwegig klingt, wie es scheint. Bäume haben viel mit Graphen gemein: es gibt Verbindungen und Knotenpunkte.
Die Knoten, auf die die beiden Zeiger weisen, heißen Sohn/Tocher/Kind-Knoten; der Knoten, der auf einen Kind-Knoten zeigt, ist der Vater/Mutter/Eltern-Knoten des Kind-Knotens.
Allgemein betrachtet man die Bäume verkehrt herum. Ein Vaterknoten liegt also über seinem Kindknoten.
Letztendlich hat man es sich aber doch nicht nehmen lassen, ein einfaches "Durchlaufen eines Baumes" Traversieren zu nennen - irgendwo hat alle Volksverbundenheit ihr Ende.
Folgende Arbeitsschritte sind zum Einfügen der CD erforderlich:
Rekursion ist eine bemerkenswerte Geschichte, die wirklich Spaß macht beim Programmieren - vielleicht gerade deshalb, weil es nicht ganz leicht zu durchblicken ist.
Mir fällt bei rekursiven Funktionen immer wieder auf, daß sie sehr kompakt sind. Und das finde ich einfach schön.
Fakt ist jedoch, daß man jede rekursive Funktion auch normal (iterativ) schreiben kann. Wem also die hier vorgestellte rekursive Funktion nicht gefällt, ist es freigestellt, sich eine iterative Version zu basteln, die allerdings etwas länger ist (Schleifen).
Im Prinzip heißt Rekursion nur, daß sich eine Funktion selbst aufruft. Rekursion wird von allen moderneren Sprachen unterstützt, in der Tat kenne ich keine Hochsprache, die dies nicht erlaubt.
Es geht genau nach den Arbeitsschritten ab:
int einfuegen(Knoten *wurzel, Knoten *eintrag)
{
long erg;
erg = strcmp(wurzel->gruppe, eintrag->gruppe); /* Strings vergl. */
if (erg == 0) /* exakt gefunden? */
return(FALSE); /* dann nicht einfügen */
if (erg < 0) /* Eintrag ist kleiner */
{
if (wurzel->links == NULL) /* noch weitere Einträge*/
{
wurzel->links = eintrag; /* einfügen */
eintrag->links = NULL; /* zur Sicherheit ... */
eintrag->rechts = NULL; /* ... markieren */
return(TRUE); /* wurde eingefügt */
}
else
/* links einfügen */
return(einfuegen(wurzel->links, eintrag));
}
else
{
if (wurzel->rechts == NULL) /* noch weitere ... */
{ /* Einträge einthalten? */
wurzel->rechts = eintrag; /* einfügen */
eintrag->links = NULL; /* zur Sicherheit ... */
eintrag->rechts = NULL; /* ... markieren */
return(TRUE); /* wurde eingefügt */
}
else
/* rechts einfügen */
return(einfuegen(wurzel->rechts, eintrag));
}
}
Dieser Algorithmus zeigt zwar nicht die beste Lösung zum Einfügen, aber ich hoffe, daß er für jeden leicht nachvollziehbar ist. Der Eintrag muß vorher allokiert werden und wird dann so eingefügt. Die "wurzel" zum Baum darf nicht NULL sein, d.h. das erste Element muß selbst eingefügt werden.
Ein Beispiel:
Die CDs in diesem Baum sind nach Gruppennamen sortiert, zum Vergleichen benutzen wir die C-Funktion strcmp(s1, s2), die byteweise s1 und s2 vergleicht und bei ungleichen Strings einen negativen Wert zurückgibt, falls ein ASCII-Wert von s1 kleiner ist, als der von s2. Das Ergebnis ist 0, wenn beide Strings exakt gleich sind, und positiv, wenn ein ASCII-Wert von s1 größer ist als der von s2.
Nun waren wir gerade im CD-Laden um die Ecke und haben uns eine neue CD von "Loreena McKennitt" aufschwatzen lassen. Also wollen wir sie gleich in die Verwaltung einfügen und gehen dabei nach den Schritten vor:
Der Zeiger auf den linken Teilbaum ist nicht NULL, also muß der Eintrag weiter unten im Teilbaum eingefügt werden. Weil der linke Teilbaum ebenfalls ein binärer Baum ist, ist der Zeiger auf den linken Teilbaum auch eine Wurzel eines Baums.
Wir rufen also einfach unsere Einfüge-Funktion mit dem Zeiger auf "links" auf (Rekursion).
Wie ich bereits schrieb, halbiert sich bei jedem Teilbaum die Anzahl der verbleibenden Elemente im binären Baum, man teilt die Menge der Elemente in zwei Teile. Im Idealfall sind beide Teile genau gleich groß, dann halbieren wir tatsächlich die Anzahl erreichbaren Elemente mit jedem Teilbaum. D.h. also, daß wir (um mal etwas mit Formeln zu protzen) mit dem Logarithmus zur Basis 2 von der Anzahl der Elemente im binären Baum die Anzahl der Vergleiche errechnen können.
Das heißt also, daß wir z.B. in einem (ausgeglichenen) Baum mit 1024 Elementen nach (spätestens) 10 Vergleichen das gesuchte Element gefunden haben.
Wenn wir z.B. erst ACDC, dann Dio, Metallica und Tori Amos eingeben?
Wie das geht, verschiebe ich auf einen dritten Teil, in dem ich auch das Löschen in einem binären Baum vorstelle und eine weitere Art von binären Bäumen vorstellen werde, die dieses Ausgleichen etwas effizienter machen, als es normale binäre Bäume tun.