ATOS - Around The Operating System Das ATOS-Magazin 5/96

# Datenstrukturen

Vorbemerkung:

> 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.

Im vorigen Teil erklärte ich, was dynamische Datenstrukturen sind, wie sie funktionieren und stellte eine "verkettete Liste" vor, ein einfacher Typus aus der Familie der dynamischen Datenstrukturen.

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;

Wir können die Liste nun also in beiden Richtungen durchlaufen und sehr schnell sowohl den Vorgänger als auch den Nachfolger des aktuellen Elementes ermitteln.

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.

### Der Apfel des Newton

Beim Überlegen, wie man diese verflixten verketteten Listen schneller machen kann, legen wir uns am besten an einem der beiden schönen Tage dieses Sommers unter einen Apfelbaum und grübeln etwas.

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:

Dort gibt es viele Astgabeln, die durch Äste aneinandergekettet sind. Die Äste zeigen also sozusagen auf die Astgabeln, sind also eine Art Zeiger. In eine Astgabel kann man, wenn man ein Vogel wäre, ein Nest bauen und etwas in das Nest ablegen (letzteres kann man auch als Humanoider).

So etwas kann man sehr leicht mit unseren Zeigern nachbilden, so daß jeder der beiden Zeiger auf einen anderen, darunter liegenden Teilbaum, zeigt, der wiederum eigene Äste und Astgabeln hat.

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;

### Terminologie - warum einfach, wenn es auch mit einem Fremdwort geht?

Die Fachwörter für Bäume sind ungewöhnlich einfach und verständlich. Vermutlich, weil man immer noch Worte wie "Rekursion" (eine Funktion ruft sich selbst auf) und "logarithmischer Aufwand" (dazu später) mit einstreuen kann.

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.

### Wie füge ich nun meine CD ein?

Die Idee beim binären (Such-)Baum ist nun, daß wir sortiert einfügen. Wir fangen also bei jedem Element, das wir einfügen wollen, bei der Wurzel an zu vergleichen. Ist das Element lexikalisch kleiner als die Wurzel, muß es im linken Teilbaum eingefügt werden. Ist es größer, dagegen in den rechten.

Folgende Arbeitsschritte sind zum Einfügen der CD erforderlich:

1. den CD-Titel mit der Wurzel vergleichen

2. ist der CD-Titel lexikalisch kleiner als die Wurzel, muß er im linken Teilbaum eingefügt werden, ist er größer, in den rechten.

3. ist der Zeiger auf denjenigen Teilbaum, in den die CD eingefügt werden soll, leer, d.h. NULL bzw. NIL, so wird die CD dort eingefügt.

4. den CD-Titel mit dem linken bzw. rechten Tochterknoten vergleichen und wieder in den linken bzw. rechten Teilbaum des Tochterknotens einfügen...

### Rekursion

Für den üblichen Algorithmus zum Einfügen von Elementen in einen binären Baum wird Rekursion verwendet.

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.

### Einfügen von CDs...

So, nun aber endlich zu dem Quelltext, mit dem wir eine CD in unseren binären Baum einfügen können.

Es geht genau nach den Arbeitsschritten ab:

1. Die Funktion bekommt den Zeiger auf den Teilbaum, in den die CD eingefügt werden soll.

2. Der CD-Titel wird mit dem Titel des aktuellen Knotens verglichen. Ist er lexikalisch kleiner, wird nachgeschaut, ob der Zeiger auf den linken Sohn NULL bzw. NIL ist. Ist der Zeiger NULL/NIL, so wird die CD dort eingehängt, ansonsten wird die Einfüge-Funktion für den linken Teilbaum aufgerufen (da die CD dann dort eingefügt werden muß). Ist der Titel lexikalisch größer, passiert das gleiche mit dem Zeiger auf den rechten Sohn.

Der Algorithmus in C sieht wie folgt aus:

    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.

In diesem Baum sind bereits einige CDs eingetragen.

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:

Schritt 1:
  Wir beginnen erst einmal an der Wurzel, um herauszufinden, ob der neue Eintrag in den linken oder in den rechten Teilbaum eingefügt werden muß. Da L (erster Buchstabe der Zeichenkette "Loreena McKennitt") lexikalisch kleiner als M ist, muß es im linken Teilbaum eingefügt werden. Wir nehmen also den "links"-Zeiger von der Wurzel für die weitere Suche nach dem Platz des neuen Eintrags.

  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).

Schritt 2:
  Wir betrachten jetzt den Knoten mit der Gruppe "Dio", hier ist der Gruppenname unseres neuen Eintrags größer als der des Knotens. Wir fügen also unseren Eintrag im rechten Teilbaum ein.

Schritt 3:
  Wieder vergleichen wir die Gruppen und wir stellen fest: unser Eintrag muß im rechten Teilbaum eingefügt werden.

Schritt 4:
  Da der rechte Teilbaum jetzt allerdings leer ist (Zeiger auf NULL/NIL), sind keine weiteren Verzweigungen notwendig und der Eintrag muß jetzt hier eingefügt werden.

### logarithmischer Aufwand

Wir haben gerade ein Element in einen binären Baum mit 9 Einträgen eingefügt. Dafür benötigten wir 3 Vergleiche.

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.

### Schon wieder Probleme

Was passiert aber, wenn wir schon sortiert einfügen?

Wenn wir z.B. erst ACDC, dann Dio, Metallica und Tori Amos eingeben?

Unser schöner Baum sieht ziemlich erbärmlich aus. Er ist zu einer sequentiellen Liste entartet und das ruiniert unsere Effizienz, weil die Suche nun doch wieder sequentiell abläuft. Wir müssen uns also etwas überlegen, wie wir die Elemente in unserem Baum so umsetzen, daß unser Baum schön gleichmäßig (dh. ausgeglichen) ist.

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.

HW

### darunter liegen

Merkwürdiger Weise wachsen bei den Leuten, die sich die ganzen Bäume als erste ausgedacht haben, die Bäume mit der Wurzel nach oben. Möglicherweise, liege ich also mit der Apfelbaum-Theorie gar nicht so falsch ...