Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
Vorwort des Gutachters
1 Einstieg in C
2 Das erste Programm
3 Grundlagen
4 Formatierte Ein-/Ausgabe mit »scanf()« und »printf()«
5 Basisdatentypen
6 Operatoren
7 Typumwandlung
8 Kontrollstrukturen
9 Funktionen
10 Präprozessor-Direktiven
11 Arrays
12 Zeiger (Pointer)
13 Kommandozeilenargumente
14 Dynamische Speicherverwaltung
15 Strukturen
16 Ein-/Ausgabe-Funktionen
17 Attribute von Dateien und das Arbeiten mit Verzeichnissen (nicht ANSI C)
18 Arbeiten mit variabel langen Argumentlisten – <stdarg.h>
19 Zeitroutinen
20 Weitere Headerdateien und ihre Funktionen (ANSI C)
21 Dynamische Datenstrukturen
22 Algorithmen
23 CGI mit C
24 MySQL und C
25 Netzwerkprogrammierung und Cross–Plattform-Entwicklung
26 Paralleles Rechnen
27 Sicheres Programmieren
28 Wie geht’s jetzt weiter?
A Operatoren
B Die C-Standard-Bibliothek
Stichwort

Download:
- ZIP, ca. 10,6 MB
Buch bestellen
Ihre Meinung?

Spacer
<< zurück
C von A bis Z von Jürgen Wolf
Das umfassende Handbuch
Buch: C von A bis Z

C von A bis Z
3., aktualisierte und erweiterte Auflage, geb., mit CD und Referenzkarte
1.190 S., 39,90 Euro
Galileo Computing
ISBN 978-3-8362-1411-7
Pfeil 22 Algorithmen
Pfeil 22.1 Was sind Algorithmen?
Pfeil 22.2 Wie setze ich Algorithmen ein?
Pfeil 22.3 Sortieralgorithmen
Pfeil 22.3.1 »Selection Sort« – sortieren durch Auswählen
Pfeil 22.3.2 Insertion Sort
Pfeil 22.3.3 Bubble Sort
Pfeil 22.3.4 Shellsort
Pfeil 22.3.5 Quicksort
Pfeil 22.3.6 qsort()
Pfeil 22.3.7 Zusammenfassung der Sortieralgorithmen
Pfeil 22.4 Suchalgorithmen – Grundlage zur Suche
Pfeil 22.4.1 Lineare Suche
Pfeil 22.4.2 Binäre Suche
Pfeil 22.4.3 Binäre (Such-)Bäume
Pfeil 22.4.4 Elemente im binären Baum einordnen
Pfeil 22.4.5 Binäre Bäume traversieren
Pfeil 22.4.6 Löschen eines Elements im binären Baum
Pfeil 22.4.7 Ein binärer Suchbaum in der Praxis
Pfeil 22.4.8 Binäre Suchbäume mit Eltern-Zeiger und Threads
Pfeil 22.4.9 Ausgeglichene Binärbäume
Pfeil 22.4.10 Algorithmen für ausgeglichene Bäume – eine Übersicht
Pfeil 22.5 Hashing (Zerhacken)
Pfeil 22.5.1 Wann wird Hashing verwendet?
Pfeil 22.5.2 Was ist für das Hashing erforderlich?
Pfeil 22.5.3 Hash-Funktion
Pfeil 22.5.4 Hashing mit direkter Adressierung
Pfeil 22.5.5 Vergleich von Hashing mit binären Bäumen
Pfeil 22.6 String-Matching
Pfeil 22.6.1 Brute-Force-Algorithmus
Pfeil 22.6.2 Der Algorithmus von Knuth/Morris/Pratt (KMP)
Pfeil 22.6.3 Weitere String-Matching-Algorithmen
Pfeil 22.7 Pattern Matching (reguläre Ausdrücke)
Pfeil 22.8 Backtracking
Pfeil 22.8.1 Der Weg durch den Irrgarten
Pfeil 22.8.2 Das 8-Dame-Problem


Galileo Computing - Zum Seitenanfang

22.4 Suchalgorithmen – Grundlage zur Suche Zur nächsten ÜberschriftZur vorigen Überschrift

Eine weitere grundlegende Arbeit, die ein PC zu verrichten hat, ist die Suche nach Daten. Daten mit bestimmten Informationen müssen aus einer großen Menge gespeicherter Informationen gefunden werden. Ein gutes Beispiel für die Suche ist eine Suchmaschine wie beispielsweise google.de, die sich mittlerweile zu einer der schnellsten und besten Suchmaschinen gemausert hat, und zwar dank eines Top-Algorithmus.

Idealerweise verfügt jeder Datensatz unter anderem auch über einen bestimmten Schlüssel. Er wird bei der Suche nach einem Datensatz verwendet, beispielsweise so:

struct data {
   char ort[MAX];
   unsigned int postleitzahlen;
};

Dieses Beispiel stellt ein Verzeichnis für Postleitzahlen dar. Der Schlüssel ist in diesem Fall die Postleitzahl. Wird die Postleitzahl gefunden, gibt die Suche den zugehörigen Ort aus. Eine Voraussetzung der Suche ist natürlich ein vorangegangenes Sortieren. Schließlich werden Daten ja sortiert, um sich die Suche zu erleichtern.

Mithilfe der Suche lassen sich folgende Operationen durchführen:

  • Daten initialisieren
  • Daten einfügen
  • Daten löschen
  • Daten sortieren

Anhand dieser Operationen können Sie erkennen, dass ohne Suche kaum eine richtige Datenorganisation möglich ist.


Galileo Computing - Zum Seitenanfang

22.4.1 Lineare Suche Zur nächsten ÜberschriftZur vorigen Überschrift

Die einfachste und bequemste Form der Suche von Daten ist die lineare Suche (sequenzielle Suche). Bei der sequenziellen Suche werden die Daten vom Anfang bis zum Ende durchlaufen, bis ein Datensatz mit dem Suchergebnis übereinstimmt. Die lineare Suche hat folgende Vorteile:

  • einfachste Implementierung und Erstellung mit verketteten Listen oder Arrays
  • Es kann auch in nicht sortierten Daten gesucht werden.
  • Eine bereits sortierte Liste bleibt auch dann sortiert, wenn ein neues Element eingefügt wird.

Der Nachteil der linearen Suche ist klar – bei einem großen Datensatz dauert die Suche ein wenig länger – speziell dann, wenn sich das gesuchte Element am Ende der Liste befindet. Hier sehen Sie ein einfaches Beispiel für eine sequenzielle Suche:

/* simple_search.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 255

struct plz{
   char ort[MAX];
   unsigned int postleit;
};

struct plz postleitzahlen[100];
static int N;

/* initialisieren */
void init(void) {
   N = 0;
   postleitzahlen[N].postleit = 0;
   strcpy(postleitzahlen[N].ort, "init");
}

void einfuegen(unsigned int p, char *o) {
   postleitzahlen[++N].postleit = p;
   strcpy(postleitzahlen[N].ort, o);
}

void suche(unsigned int key) {
   int i;
   for(i=0; i<=N; i++)
   if(postleitzahlen[i].postleit == key) {
      printf("Der Ort zur Postleitzahl %d : %s\n",
         key,postleitzahlen[i].ort);
      return;
   }
   printf("Für den Wert %d konnte keine Postleitzahl "
          "gefunden werden!\n",key);
}

int main(void) {
   int wahl;
   unsigned int search, post;
   char new_ort[MAX];
   init();

   do {
      printf("-1- Postleitzahl suchen\n");
      printf("-2- Postleitzahl hinzufuegen\n");
      printf("-3- Ende\n\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);
      getchar();

      if(wahl == 1) {
         printf("Welche Postleitzahl suchen Sie : ");
         scanf("%5u",&search);
         suche(search);
      }
      else if(wahl == 2) {
         printf("Neue Postleitzahl : ");
         scanf("%5u",&post);
         getchar();
         printf("Ort für PLZ %d : ",post);
         fgets(new_ort, MAX, stdin);
         einfuegen(post, strtok(new_ort, "\n") );
      }
   } while(wahl!=3);
   return EXIT_SUCCESS;
}

Natürlich kann die Suche auch so verändert werden, dass zu einem Ort die Postleitzahl gesucht wird. Dazu muss nur die Suchfunktion ein wenig umgeschrieben werden:

void suche(char *o) {
   int n=N;
   int i;
   for(i=0; i<=N; i++)
      if(strcmp(postleitzahlen[i].ort,o) == 0) {
         printf("Der Ort zur Postleitzahl %d : %s\n",
            key,postleitzahlen[i].ort);
         return;
      }
   printf("Für den Wert %s konnte keine Postleitzahl "
          "gefunden werden!\n",o);
}

In den einfachsten Fällen – bei wenigen Daten – dürfte die lineare Suche völlig ausreichend sein.


Galileo Computing - Zum Seitenanfang

22.4.2 Binäre Suche Zur nächsten ÜberschriftZur vorigen Überschrift

Die binäre Suche eignet sich sehr gut bei etwas größeren Datensätzen. Sie arbeitet nach dem Prinzip »Teile und herrsche«. Der vollständige Datensatz wird (sortiert!) in zwei Teile zerlegt. Ist das aktuelle Element größer als das gesuchte, wird mit dem Element, das links vom aktuellen Element liegt, verglichen. Ist das aktuelle kleiner, wird mit dem Element rechts verglichen. Ist die Suche erfolglos, wird die Liste wieder in zwei Teile aufgeteilt – natürlich unter der Bedingung, dass das Element in der Mitte größer oder kleiner als das gesuchte ist. Im schlechtesten Fall wird das erste oder das letzte Element gesucht.

Diese Art der Suche scheint für reine Suchergebnisse optimal zu sein. Sollten Sie aber vorhaben, Elemente in den Datensatz einzufügen, ist das schnelle Suchergebnis wieder dahin. Beim Einfügen eines neuen Elements muss wieder dafür gesorgt sein, dass die Liste sortiert bleibt.

Hierzu folgt das Beispiel, das voraussetzt, dass die Liste bereits sortiert ist. Eine Sortierfunktion können Sie ja zur Übung selbst implementieren.

/* bin_search.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 255

struct plzn{
   char ort[MAX];
   unsigned int plz;
};

struct plzn postleitzahlen[100];
static int N;

/* initialisieren */
void init(void) {
   N = 0;
   postleitzahlen[N].plz = 0;
   strcpy(postleitzahlen[N].ort, "dummy");
}

void einfuegen(unsigned int p, char *o) {
   postleitzahlen[++N].plz = p;
   strcpy(postleitzahlen[N].ort, o);
}

int binaere_suche(unsigned int key) {
   int l=1;
   int r=N;
   int x;

   while(r >= l) {
      x=(l+r)/2;
      if(key < postleitzahlen[x].plz) /* kleiner? */
         r=x-1;  /* Rechte Seite ist nicht mehr so interessant. */
       else      /* dann halt größer */
         l=x+1;  /* Linke Seite ist nicht mehr so interessant. */
       if(key == postleitzahlen[x].plz)
          return x;     /* gefunden; x = Position */
   }
   return -1; /* nicht gefunden */
}

int main(void) {
   int wahl, ret;
   unsigned int search, post;
   char new_ort[MAX];

   init();
   do {
      printf("-1- Postleitzahl suchen\n");
      printf("-2- Postleitzahl hinzufuegen\n");
      printf("-3- Ende\n\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);
      getchar();
      if(wahl == 1) {
         printf("Welche Postleitzahl suchen Sie : ");
         scanf("%5u",&search);
         ret=binaere_suche(search);
         if(ret == -1)
            printf("Kein Ergebnis auf Ihre Anfrage!\n");
         else
            printf("Die Antwort auf %d : "
                   "%s\n",search,postleitzahlen[ret].ort);
      }
      else if(wahl == 2) {
         printf("Neue Postleitzahl : ");
         scanf("%5u",&post);
         getchar();
         printf("Ort für PLZ %d : ",post);
         fgets(new_ort, MAX, stdin);
         einfuegen(post, strtok(new_ort, "\n") );
      }
   } while(wahl!=3);
   return EXIT_SUCCESS;
}

Die binäre Suche eignet sich also für eine kleinere, bereits sortierte Datenmenge hervorragend.


Galileo Computing - Zum Seitenanfang

22.4.3 Binäre (Such-)Bäume Zur nächsten ÜberschriftZur vorigen Überschrift

Binäre Suchbäume dürfen wohl als die Methode der Informatik schlechthin angesehen werden. Binäre Bäume sind im Prinzip den verketteten Listen sehr ähnlich, allerdings mit dem Unterschied, dass binäre Bäume nicht linear angeordnet sind. Hierzu zwei Grafiken, die das verdeutlichen sollen:

Abbildung 22.16 Doppelt verkettete Liste

Abbildung 22.17 Binärer Baum

Welchen Vorteil bietet hierbei der binäre Baum? Am besten ist, Sie zählen die Schritte, die benötigt werden, um vom Anfang des Baums bis zum Wert 5 zu gelangen. Dasselbe machen Sie jetzt mit der verketteten Liste. Der Anfang (Wurzel) beim binären Baum ist hier die Ziffer 3. Mit binären Suchbäumen lassen sich also die Suchwege erheblich verkürzen. Bei solch kleinen Beispielen ist das nicht der Rede wert, aber je größer der Datenbestand wird, desto stärker wirkt sich dies auf die Performance aus.

Zudem ist bei der grafischen Darstellung des binären Baums auffällig, dass alle Werte, die sich auf der linken Seite befinden, kleiner sind, und dass sich die größeren Werte auf der rechten Seite befinden. Aber dazu gleich mehr.

Grundbegriffe von binären Bäumen

Der Begriff Baum (engl. Tree) wurde hier verwendet, da diese Struktur die Form eines Baums hat, der allerdings auf den Kopf gestellt ist. Auch die einzelnen Elemente heißen ähnlich wie die eines Baums. Bäume sind hierarchische Datenstrukturen, die folgendermaßen aufgeteilt werden:

Abbildung 22.18 Gliederung eines binären Baums

Ein Baum besteht aus folgenden Elementen:

  • Wurzel (engl. root) – Dieser Knoten ist der einzige, der keinen Vorgänger besitzt. Wie bei einem echten Baum können Sie sich das als Wurzel vorstellen – nur dass in der Informatik die Wurzel oben ist.
  • Ast, Kante (engl. edges) – Jeder Baum besteht aus einzelnen Knoten, die mit einem Ast verbunden sind.
  • Knoten (engl. node) – Knoten sind die eigentlichen Elemente, die über alle Informationen wie Daten und Zeiger zum rechten und linken Knoten verfügen. Ein Knoten ist die Struktur selbst. Beim binären Baum hat jeder Knoten nicht mehr als zwei Nachfolger (daher auch »bi« = zwei). Es gibt zwar auch Bäume mit mehreren Nachfolgern, allerdings handelt es sich dann nicht mehr um einen binären Baum.
  • Blatt (engl. leaf ) – Blätter sind Knoten, die keinen Nachfolger besitzen.
  • Teilbaum – Ein Knoten mit einem linken und einem rechten Nachfolger wird als Teilbaum bezeichnet.
  • Tiefe (engl. level) – Als Tiefe wird die Anzahl der Nachfolgeroperationen bezeichnet, die erforderlich sind, um von der Wurzel des Baums zu einem bestimmten Knoten zu gelangen. Die Tiefe n kann dann 2n –1 einzelne Knoten beinhalten.

Mit diesem Grundwissen können Sie beginnen, einen binären Baum zu programmieren. Zuerst wird die Struktur eines Knotens benötigt:

struct knoten {
   int wert;
   struct knoten *links;
   struct knoten *rechts;
};

Damit der Umfang des Beispiels nicht zu sehr anwächst, begnügen wir uns hier mit der Eingabe eines Werts (int wert) in die Struktur. Außer dem int-Wert besitzt die Struktur noch jeweils einen Zeiger auf den linken und einen auf den rechten Nachfolger des Knotens. Somit können Sie sich die Struktur vom Typ knoten so vorstellen:

Abbildung 22.19 Die Datenstruktur eines binären Baumes


Galileo Computing - Zum Seitenanfang

22.4.4 Elemente im binären Baum einordnen Zur nächsten ÜberschriftZur vorigen Überschrift

Als Erstes wird eine Funktion benötigt, mit der Werte in den binären Baum eingeordnet werden. Die kleineren Werte sollen dabei immer auf der linken Seite und die größeren Werte auf der rechten Seite eingeordnet werden. Hier folgt nochmals die Struktur. Es wurde außerdem mit typedef ein neuer Datentyp namens KNOTEN definiert:

struct knoten   {
   int wert;
   struct knoten *links;
   struct knoten *rechts;
};

typedef struct knoten KNOTEN;

KNOTEN *einordnen(KNOTEN *zeiger) {
   //---->Funktionen ...

Folgende drei Möglichkeiten können beim Einordnen in den binären Baum auftreten:

1. Es befindet sich noch kein Element (genauer: es fehlt noch die Wurzel – root) im Baum, und das eingefügte ist das erste Element und somit die Wurzel des Baums:
   if(zeiger==NULL) {
      zeiger=(KNOTEN*)malloc(sizeof(KNOTEN));
      zeiger->wert=zahl;
      zeiger->links=zeiger->rechts=NULL;
   }
2. Der neue Wert ist kleiner als die Wurzel bzw. bei weiterem Verlauf kleiner als der Knoten, und somit wird der neue Wert links von der Wurzel bzw. dem Knoten eingeordnet:
   else if(zeiger->wert >= zahl)
      zeiger->links=einordnen(zeiger->links);
Hier erfolgt der erste rekursive Aufruf. Der Zeiger zeiger, der nach links verweist, erhält die Adresse links vom aktuellen Knoten durch einen erneuten Funktionsaufruf mit einordnen(zeiger->links). Dieser erneute Funktionsaufruf muss natürlich noch nicht die Adresse zurückliefern. Der Baum wird so lange weiter nach unten abgesucht, bis ein passender Platz gefunden wurde.
3. Die dritte und letzte Möglichkeit: Der Wert des neuen Elements ist größer als die Wurzel bzw. der Knoten. Somit kommt dieses auf die rechte Seite der Wurzel bzw. des Knotens:
   else if(zeiger->wert < zahl)
      zeiger->rechts=einordnen(zeiger->rechts);
Trifft die zweite oder dritte Möglichkeit zu, wird der Baum so lange nach rechts oder links durchlaufen (durch weitere rekursive Aufrufe), bis keine der beiden Möglichkeiten mehr zutrifft. Dann wurde der Platz für das neue Element gefunden.

Hier sehen Sie die vollständige Funktion zum Einordnen eines neuen Elements in den binären Baum mitsamt der main()-Funktion:

/* btree1.c */
#include <stdio.h>
#include <stdlib.h>

struct knoten{
   int wert;
   struct knoten *links;
   struct knoten *rechts;
};
typedef struct knoten KNOTEN;

/* globale Variable */
int zahl;

KNOTEN *einordnen(KNOTEN *zeiger)  {
   if(zeiger == NULL) {
      zeiger = malloc(sizeof(KNOTEN));
      if(zeiger==NULL) {
         printf("Konnte keinen Speicherplatz reservieren!\n");
         exit (EXIT_FAILURE);
      }
      zeiger->wert=zahl;
      zeiger->links=zeiger->rechts=NULL;
   }
   else if(zeiger->wert >= zahl)
      zeiger->links=einordnen(zeiger->links);
   else if(zeiger->wert < zahl)
      zeiger->rechts=einordnen(zeiger->rechts);
   return (zeiger);
}

int main(void) {
   KNOTEN *wurzel=NULL;

   do {
      printf("Bitte Zahl eingeben : ");
      scanf("%d",&zahl);
      wurzel=einordnen(wurzel);
   } while(zahl != 0);
   return EXIT_SUCCESS;
}

Nun betrachten wir den theoretischen Ablauf des Programms: Das Programm wurde gestartet, und der erste Wert sei die 10. Jetzt wird mit wurzel=einordnen(wurzel) die Funktion aufgerufen. Bei der ersten Eingabe trifft gleich die erste if-Bedingung zu:

if(zeiger == NULL)

Womit die Zahl 10 das erste Element und gleichzeitig die Wurzel des Baums ist. Die beiden Zeiger links und rechts bekommen den NULL-Zeiger zugewiesen:

Abbildung 22.20 Die Wurzel des Baums

Als Nächstes sei die Zahl 8 gegeben. Wieder wird über die main()-Funktion die Funktion einordnen() aufgerufen. Dieses Mal ist es aber (zeiger==NULL) falsch, denn das erste Element bzw. die Wurzel des Baums ist die Zahl 10. Die nächste else if-Bedingung ist:

else if(zeiger->wert >= zahl)

Das trifft zu, denn zeiger->wert (10) ist größer als die eingegebene Zahl. Es folgt der erste Funktionsselbstaufruf:

zeiger->links=einordnen(zeiger->links);

Jetzt soll der Zeiger zeiger, der auf links verweist, die Adresse vom erneuten Funktionsaufruf einordnen(zeiger->links) zugewiesen bekommen. Alles beginnt wieder von vorn:

if(zeiger==NULL)

Und tatsächlich zeigt der Zeiger zeiger jetzt auf NULL, da er ja zuvor durch den erneuten Aufruf die Adresse von der linken Seite des ersten Elements (10) erhalten hat. Also wird erst Speicher alloziert und dann das neue Element eingefügt. Der linke und der rechte Zeiger des neuen Elements bekommen wieder jeweils den NULL-Zeiger zugewiesen:

Abbildung 22.21 Kleinere Elemente wie die Wurzel kommen auf die linke Seite.

Als Nächstes sei die Zahl 9 gegeben. Im ersten Durchlauf wird

else if(zeiger->wert >= zahl)
   zeiger->links=einordnen(zeiger->links);

wie schon zuvor ausgeführt. Jetzt verweist der Zeiger zeiger auf die Adresse mit dem Wert 8. Also ist zeiger==NULL nicht wahr, und die Bedingung

else if(zeiger->wert >= zahl)

ist auch nicht wahr, denn zeiger->wert (8) ist dieses Mal nicht größer oder gleich der aktuellen Zahl (9). Die nächste else if-Anweisung

else if(zeiger->wert < zahl)

ist jetzt wahr, denn (8 < 9) trifft zu. Dies ist der zweite rekursive Funktionsaufruf (einer liegt ja schon auf dem Stack):

zeiger->rechts=einordnen(zeiger->rechts);

Jetzt bekommt der Zeiger zeiger, der auf rechts verweist, die Adresse von einordnen(zeiger->rechts). Das ist übrigens auch der Grund, weshalb die Funktion einen Rückgabewert vom Typ KNOTEN * hat. Auf zum erneuten Durchlauf der Funktion: zeiger==NULL trifft jetzt zu, also wurde der Platz für das neue Element gefunden:

Abbildung 22.22 Das neue Element ist kleiner als die Wurzel, aber größer als der Nachfolgerknoten.

Als Nächstes sei die Zahl 20 gegeben. Hierzu soll eine Grafik genügen, die Sie als Übung selbst durchgehen können:

Abbildung 22.23 Elemente, die größer als die Wurzel sind, kommen auf die rechte Seite.


Galileo Computing - Zum Seitenanfang

22.4.5 Binäre Bäume traversieren Zur nächsten ÜberschriftZur vorigen Überschrift

Die einzelnen Knoten, die zuvor erzeugt wurden, werden nun besucht bzw. in diesem Fall ausgeben. Dies wird Traversieren der Bäume genannt. Es gibt zwei gängige Möglichkeiten, die Bäume zu traversieren. Zur Demonstration wird der eben erstellte binäre Baum verwendet:

1. Die erste Variante ist die Preorder-Traversierung. Gemäß der Preorder-Traversierung wird zuerst die Wurzel mit dem Wert 10 besucht, anschließend der Knoten mit dem Wert 8. Es folgt der Knoten mit dem Wert 9. Als Letztes wird der Knoten mit dem Wert 20 besucht. Diese Preorder-Taktik läuft wie folgt ab: »Besuche die Wurzel, dann besuche den linken Unterbaum, als Nächstes besuche den rechten Unterbaum.« Die Funktion, die das Verfahren realisiert, sieht so aus:
void zeige_baum(KNOTEN *zeiger) {
   if(zeiger != NULL) {
      printf("\n%d->",zeiger->wert);
      zeige_baum(zeiger->links);
      zeige_baum(zeiger->rechts);
   }
}
2. Die zweite Möglichkeit ist die sogenannte Inorder-Traversierung. Bei dieser Möglichkeit werden die Knoten in folgender Reihenfolge besucht:
8->9->10->20
im Gegensatz zum Preorder:
10->8->9->20
Daraus lässt sich folgende Inorder-Taktik konstatieren: »Besuche den linken Unterbaum, dann besuche die Wurzel, und besuche zuletzt den rechten Unterbaum.« Die Funktion der Inorder-Taktik sieht dann wie folgt aus:
void zeige_baum(KNOTEN *zeiger) {
   if(zeiger != NULL) {
      zeige_baum(zeiger->links);
      printf("\n%d->",zeiger->wert);
      zeige_baum(zeiger->rechts);
   }
}

Es ist kaum eine Änderung zur Preorder-Traversierung festzustellen, nur dass bei der Inorder-Traversierung zuerst mit dem am weitesten links unten liegenden Knoten oder Blatt angefangen wird und beim Preorder mit der Wurzel.

Es gibt noch eine dritte Möglichkeit: »Besuche den linken Unterbaum, besuche den rechten Unterbaum und dann besuche die Wurzel.« Diese Methode benötigen Sie eigentlich nur bei Postfix-Notationen.


Galileo Computing - Zum Seitenanfang

22.4.6 Löschen eines Elements im binären Baum Zur nächsten ÜberschriftZur vorigen Überschrift

Jetzt folgt ein etwas komplizierteres Problem: das Löschen eines Elements im Baum. Hierbei gibt es erneut drei Möglichkeiten:

1. Die einfachste Form ist die Entfernung eines Blatts, da dieses keinen Nachfolger mehr hat.
2. Die zweite Möglichkeit ist die Entfernung eines Knotens mit nur einem Nachfolger.
3. Die letzte Möglichkeit ist gleichzeitig auch die schwierigste. Es muss ein Knoten gelöscht werden, der zwei Nachfolger hat.

Zuerst benötigen Sie eine Funktion, die den zu löschenden Knoten sucht:

void loesche(KNOTEN **zeiger, int such) {
   if((*zeiger) == NULL)
      printf("Baum ist leer\n");
   else if((*zeiger)->wert == such) /* Gefunden! */
      loesche_knoten(zeiger);
   else if((*zeiger)->wert >= such)
      loesche(&((*zeiger)->links),such);
   else
      loesche(&((*zeiger)->rechts),such);
}

Der Funktion loesche() werden als Argumente die Wurzel (zeiger) und der zu suchende Wert (such) übergeben. Als Erstes wird überprüft, ob überhaupt eine Wurzel vorhanden ist (if((*zeiger) == NULL)). Danach wird getestet, ob der Wert schon gefunden wurde (else if((*zeiger)->wert == such)). Wurde der Wert gefunden, wird die Funktion loesche_knoten() mit dem zeiger auf den gefundenen Wert aufgerufen. Als Nächstes (falls der Knoten noch nicht gefunden wurde) wird überprüft, ob der Wert, auf den der Zeiger zeiger verweist, größer oder gleich dem gesuchten Wert such ist (else if((*zeiger)->wert >= such) ). Ist dies der Fall, ist der gesuchte Wert kleiner als der, auf den der Zeiger zeiger verweist, und muss sich somit auf der linken Seite der aktuellen Adresse zeiger befinden (loesche(&((*zeiger)–> links),such)). Hier erfolgt der erste rekursive Aufruf mit dem Adressoperator. Die letzte else-Anweisung ergibt sich dadurch, dass der gesuchte Wert größer als der ist, auf den der Zeiger zeiger gerade verweist. In diesem Fall wird auf der rechten Seite mit dem rekursiven Aufruf (loesche(&((*zeiger)-> rechts),such)) weiter gesucht.

Es wird jetzt davon ausgegangen, dass der Knoten gefunden wurde, und nun wird die Funktion loesche_knoten(zeiger) aufgerufen:

void loesche_knoten(KNOTEN **zeiger) {
   KNOTEN *temp;
   int tempwert;

   if(globale_wurzel == *zeiger) {
      printf("Kann die Wurzel nicht loeschen!!\n");
      return;
   }
   if((*zeiger)!=NULL) { /* Blatt! */
      if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL) {
         free(*zeiger);
         *zeiger=NULL;
      }
      else if((*zeiger)->links==NULL) {
         /* Nur rechter Nachfolger */
         temp = *zeiger;
         *zeiger=(*zeiger)->rechts;
         free(temp);
      }
      else if((*zeiger)->rechts==NULL) {
         /* Nur linker Nachfolger */
         temp = *zeiger;
         *zeiger=(*zeiger)->links;
         free(temp);
      }
      else { /* 2 Nachfolger, wir suchen Ersatzelement */
        suche_ersatz(&tempwert, &((*zeiger)->rechts));
        (*zeiger)->wert=tempwert;
      }
   }
}

Zunächst wird überprüft, ob der gefundene Wert die Wurzel ist. In diesem Fall wird kein Element gelöscht und die Funktion beendet (dazu unten mehr). Als Nächstes wird getestet, ob das zu löschende Element ein Blatt ist (ein Element ohne Nachfolger):

if((*zeiger)->links==NULL && (*zeiger)->rechts==NULL)

Falls es ein Blatt ist, wird es entfernt. Ansonsten wird mit den nächsten beiden else if-Bedingungen ermittelt, ob das zu löschende Element einen rechten oder linken Nachfolger hat. Die letzte und die schwierigste Möglichkeit ist, dass der zu löschende Knoten zwei Nachfolger besitzt. Dafür wird am besten eine spezielle Funktion geschrieben, die für den zu löschenden Knoten ein Ersatzelement sucht:

else { /* 2 Nachfolger, wir suchen Ersatzelement */
    suche_ersatz(&tempwert, &((*zeiger)->rechts));
    (*zeiger)->wert=tempwert;
}

Hier wird ein Ersatzelement auf der rechten Seite gesucht. Die Funktion suche_ersatz() sieht so aus:

void suche_ersatz(int *neuwert, KNOTEN **zeiger) {
   KNOTEN *temp;

   if(*zeiger != NULL) {
      if((*zeiger)->links==NULL) {
         neuwert=(*zeiger)->wert;
         temp=*zeiger;
         *zeiger=(*zeiger)->rechts;
         free(temp);
      }
      else
         suche_ersatz(neuwert, &((*zeiger)->links));
   }
}

Die Funktion suche_ersatz() läuft jetzt durch einen rekursiven Aufruf (suche_ersatz(neuwert, &((*zeiger)->links));) so lange die linke Seite des Baums hinab, bis die Bedingung (if((*zeiger)->links==NULL)) wahr ist. Dann wurde ein Ersatzelement gefunden, auf das gleich der Zeiger *neuwert verweist.


Tipp

Zum besseren Verständnis hilft es oft, sich den Vorgang mit einer Zeichnung auf einem Blatt Papier zu vergegenwärtigen.


Das vollständige Listing (btree2.c) – mit einigen zusätzlichen Funktionen – finden Sie natürlich wieder auf der Buch-CD.


Galileo Computing - Zum Seitenanfang

22.4.7 Ein binärer Suchbaum in der Praxis Zur nächsten ÜberschriftZur vorigen Überschrift

Jetzt soll der binäre Suchbaum mit dem Postleitzahlen-Programm verwendet werden. Zuerst wird die grundlegende Knotenstruktur für den binären Baum festgelegt:

struct binaer_knoten{
   char ort[255];
   unsigned int plz;
   struct binaer_knoten *links;
   struct binaer_knoten *rechts;
};

Jetzt schreiben wir eine spezielle Struktur für den Baum:

struct binaer_baum{
   struct binear_knoten *root;
   unsigned int counter;
};

Dank dieser Struktur werden die rekursiven Aufrufe des vorigen Beispiels aufgehoben. Dies ist möglich, weil beim ersten Aufruf der Funktion als Argument immer die Adresse der Wurzel des Baums mit übergeben wird.

Als Nächstes benötigen Sie eine Funktion, um den binären Baum zu initialisieren:

struct binaer_baum *init(void) {
   struct binaer_baum *baum =malloc(sizeof *baum);
   if(baum == NULL) {
      fprintf(stderr, "Speicherplatzmangel!!!\n");
      return NULL;
   }
   else { /* initialisieren */
      baum->root = NULL;
      baum->counter=0;
      return baum;
   }
}

Es folgt eine Funktion zum Einfügen einzelner Knoten in den binären Baum ohne einen rekursiven Funktionsaufruf:

int einfuegen(struct binaer_baum *baum, unsigned int p, char *o){
   struct binaer_knoten *knoten, **neu;

   neu =(struct binaer_knoten **) &baum->root;
   knoten= (struct binaer_knoten *) baum->root;
   for(;;) {
      if(knoten == NULL) {
         /* Haben wir einen freien Platz gefunden? */
         knoten = *neu = malloc(sizeof *knoten);
         if(knoten != NULL) {
            /* Daten einfügen */
            knoten->plz = p;
            strcpy(knoten->ort, o);
            knoten->links=knoten->rechts=NULL;
            baum->counter++;
            /* Beendet die Funktion erfolgreich. */
            return 1;
         }
         else {
            fprintf(stderr, "Speicherplatzmangel\n");
            return 0;
         }
      }
      /* Ist die aktuelle Postleitzahl größer? */
      else if(p > knoten->plz)  {
         /* Dann gehts rechts weiter im Baum. */
         neu = &knoten->rechts;
         knoten = knoten->rechts;
      }
      else { /* Der letzte Fall, die aktuelle PLZ ist kleiner, */
         /* dann eben nach links weiter im Baum. */
         neu = &knoten->links;
         knoten = knoten->links;
      }
   }
}

Das Thema binäre Bäume ist erheblich einfacher, wenn die Rekursion beseitigt wird. Wichtig ist bei dieser Funktion, dass sich die Endlosschleife auch irgendwann einmal beendet. In diesem Beispiel beendet sich die Funktion bei Erfolg mit dem Rückgabewert 1 (return 1), wenn das neue Element eingefügt wurde. Bei Mangel an Speicherplatz gibt diese Funktion 0 zurück. Das Einfügen eines neuen Elements berücksichtigt übrigens keine doppelten Einträge. Dies können Sie zur Übung gern selbst nachtragen.

Jetzt soll die Suchfunktion erstellt werden (um die es ja eigentlich in diesem Kapitel geht). Begonnen wird an der Wurzel (root) des Baums. Ist das gesuchte Element größer, geht die Suche auf der rechten Seite des Baums weiter. Ist das gesuchte Element kleiner, wird auf der linken Seite weitergesucht. Bei einem perfekt ausgeglichenen Baum führt dies zu optimalen Ergebnissen. Hier sehen Sie die Suchfunktion, die sich relativ einfach erstellen lässt:

void binaere_suche_plz(const struct binaer_baum *baum,
                       unsigned int p) {
   const struct binaer_knoten *knoten;

   /* zuerst an die Wurzel */
   knoten = (struct binaer_knoten *) baum->root;
   for(;;) {
      if(knoten == NULL) {
         printf("Keine erfolgreiche Suche!\n");
         return;
      }
      if(p == knoten->plz) {  /* Gefunden */

         printf("Ort zu Postleitzahl %d : %s\n",
            p,knoten->ort);
         return;
      }
      else if(p > knoten->plz)   /* Gesuchtes Element größer:  */
         knoten=knoten->rechts;  /* rechts am Baum weiter.     */
      else                       /* Gesuchtes Element kleiner: */
         knoten=knoten->links;   /* links am Baum weiter.      */
   }
}

Mit dieser Funktion haben Sie auch schon die Grundlage für das Löschen eines Elements im Baum geschaffen. Nur müssen Sie anstatt

      if(p == knoten->plz) {  /* Gefunden */
         printf("Ort zu Postleitzahl %d : %s\n",
            p,knoten->ort);
         return;
      }

break verwenden, um nach der for-Schleife weitere Operationen durchzuführen:

   if(p == knoten->plz) /* Gefunden */
      break;

Das Löschen eines Elements im binären Baum wurde ja schon einmal präsentiert. Da aber schon beim Einfügen eines Knotens auf weitere Funktionsaufrufe, insbesondere Rekursionen, verzichtet wurde, soll auch die Funktion zum Löschen eines Knotens entsprechend umgeschrieben werden, und zwar so, dass alle Operationen in dieser Funktion ausgeführt werden. Hier sehen Sie die Funktion:

int bin_delete(struct binaer_baum *baum, unsigned int p) {
   /* pointer_z ist das zu löschende Element */
   struct binaer_knoten **pointer_q, *pointer_z,
                         *pointer_y, *pointer_x;

   pointer_q = (struct binaer_knoten **)&baum->root;
   pointer_z =  (struct binaer_knoten *)baum->root;
   for(;;) {
      if(pointer_z == NULL)
         return 0;
      else if(p == pointer_z->plz)
         /* zu löschendes Element gefunden */
         break;
      else if(p > pointer_z->plz) {
         /* Das zu löschende Element ist größer. */
         pointer_q = &pointer_z->rechts;
         /* rechts weitersuchen */
         pointer_z = pointer_z->rechts;
      }
      else { /* Das zu löschende Element ist kleiner. */
         pointer_q = &pointer_z->links;
         /* links weitersuchen */
         pointer_z = pointer_z->links;
      }
   } /* Hierher kommen wir nur durch ein break. */

   /* Jetzt müssen wir das zu löschende Element untersuchen.
    * pointer_z hat rechts keinen Nachfolger, somit können wir
    * es austauschen gegen den linken Nachfolger ... */
   if(pointer_z->rechts == NULL)
      *pointer_q = pointer_z->links;
   else {
      /* pointer_z hat einen rechten Nachfolger, aber
       * keinen linken. */
      pointer_y = pointer_z->rechts;
      if(pointer_y->links == NULL) {
         /* pointer_z->rechts hat keinen linken Nachfolger ... */
         pointer_y->links = pointer_z->links;
         *pointer_q = pointer_y;
      }
      else {  /* Es gibt einen linken Nachfolger. */
         pointer_x = pointer_y->links;
         /* Jetzt suchen wir so lange, bis es keinen linken
          * Nachfolger mehr gibt */
         while(pointer_x->links != NULL) {
            pointer_y = pointer_x;
            pointer_x = pointer_y->links;
         }
         /* Jetzt haben wir alle Punkte zusammen und
          * können diese verknüpfen. */
         pointer_y->links = pointer_x->rechts;
         pointer_x->links = pointer_z->links;
         pointer_x->rechts = pointer_z->rechts;
         *pointer_q = pointer_x;
      }
   }
    /* Zu guter Letzt können wir pointer_z freigeben. */
   baum->counter--;
   free(pointer_z);
   return 1;
}

Zugegeben, auf den ersten Blick dürfte diese Funktion etwas abschreckend wirken. Aber zeichnen Sie sich einen binären Baum auf ein Blatt Papier, und gehen Sie dabei diese Funktion Schritt für Schritt durch: Sie werden sich wundern, wie einfach diese Funktion im Gegensatz zur rekursiven Variante ist.

Zum Schluss folgt hier noch der vollständige Quellcode zu diesem Abschnitt:

/* btree3.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 255

struct binaer_knoten{
   char ort[MAX];
   unsigned int plz;
   struct binaer_knoten *links;
   struct binaer_knoten *rechts;
};

struct binaer_baum{
   struct binear_knoten *root;
   unsigned int counter;
};

struct binaer_baum *init(void) {
   struct binaer_baum *baum =malloc(sizeof *baum);
   if(baum == NULL) {
      fprintf(stderr, "Speicherplatzmangel!!!\n");

      return NULL;
   }
   else { /*Initialisieren*/
      baum->root = NULL;
      baum->counter=0;
      return baum;
   }
}

int einfuegen(struct binaer_baum *baum, unsigned int p, char *o){
   struct binaer_knoten *knoten, **neu;

   neu =(struct binaer_knoten **) &baum->root;
   knoten= (struct binaer_knoten *) baum->root;
   for(;;) {
      if(knoten == NULL) {
         /* Haben wir einen freien Platz gefunden? */
         knoten = *neu =malloc(sizeof *knoten);
         if(knoten != NULL) {
            /* Daten einfuegen */
            knoten->plz = p;
            strcpy(knoten->ort, o);
            knoten->links=knoten->rechts=NULL;
            baum->counter++;
            /* Beendet die Funktion erfolgreich. */
            return 1;
         }
         else {
            fprintf(stderr, "Speicherplatzmangel\n");
            return 0;
         }
      }
      /* Ist die aktuelle Postleitzahl größer? */
      else if(p > knoten->plz)  {
         /* Dann gehts rechts weiter im Baum. */
         neu = &knoten->rechts;
         knoten = knoten->rechts;
      }
      else { /* Der letzte Fall, die aktuelle PLZ ist kleiner, */
         /* dann eben nach links weiter im Baum. */
         neu = &knoten->links;
         knoten = knoten->links;
      }
   }
}

void binaere_suche_plz(const struct binaer_baum *baum,
                       unsigned int p) {
   const struct binaer_knoten *knoten;

   /* zuerst an die Wurzel */
   knoten = (struct binaer_knoten *) baum->root;
   for(;;) {
      if(knoten == NULL) {
         printf("Keine erfolgreiche Suche!\n");
         return;
      }
      if(p == knoten->plz) {  /* Gefunden */
         printf("Ort zu Postleitzahl %d : %s\n",
            p,knoten->ort);
         return;
      }
      else if(p > knoten->plz)   /* Gesuchtes Element größer:  */
         knoten=knoten->rechts;  /* rechts am Baum weiter.     */
      else                       /* Gesuchtes Element kleiner: */
         knoten=knoten->links;   /* links am Baum weiter.      */
   }
}

int bin_delete(struct binaer_baum *baum, unsigned int p) {
   /* pointer_z ist das zu löschende Element. */
   struct binaer_knoten **pointer_q, *pointer_z,
                         *pointer_y, *pointer_x;

   pointer_q = (struct binaer_knoten **)&baum->root;
   pointer_z =  (struct binaer_knoten *)baum->root;
   for(;;) {
      if(pointer_z == NULL)
         return 0;
      else if(p == pointer_z->plz)
         /* zu löschendes Element gefunden */
         break;
      else if(p > pointer_z->plz) {
         /* Das zu löschende Element ist größer. */
         pointer_q = &pointer_z->rechts;
         /* rechts weitersuchen */
         pointer_z = pointer_z->rechts;
      }
      else { /* Das zu löschende Element ist kleiner. */
         pointer_q = &pointer_z->links;
         /* links weitersuchen */
         pointer_z = pointer_z->links;
      }
   } /* Hierher kommen wir nur durch ein break. */

   /* Jetzt müssen wir das zu löschende Element untersuchen.
    * pointer_z hat rechts keinen Nachfolger, somit können wir
    * es austauschen gegen den linken Nachfolger ... */
   if(pointer_z->rechts == NULL)
      *pointer_q = pointer_z->links;
   else {
      /* pointer_z hat einen rechten Nachfolger, aber
       * keinen linken. */
      pointer_y = pointer_z->rechts;
      if(pointer_y->links == NULL) {
         /* pointer_z->rechts hat keinen linken Nachfolger ... */
         pointer_y->links = pointer_z->links;
         *pointer_q = pointer_y;
      }
      else {  /* Es gibt einen linken Nachfolger. */
         pointer_x = pointer_y->links;
         /* Jetzt suchen wir so lange, bis es keinen linken
          * Nachfolger mehr gibt. */
         while(pointer_x->links != NULL) {
            pointer_y = pointer_x;
            pointer_x = pointer_y->links;
         }
         /* Jetzt haben wir alle Punkte zusammen und
          * können diese verknüpfen. */
         pointer_y->links = pointer_x->rechts;
         pointer_x->links = pointer_z->links;
         pointer_x->rechts = pointer_z->rechts;
         *pointer_q = pointer_x;
      }
   }
    /* Zu guter Letzt können wir pointer_z freigeben. */
   baum->counter--;
   free(pointer_z);
   return 1;
}

int main(void) {
   struct binaer_baum *re;
   char o[MAX];
   unsigned int p;
   int wahl, r;

   re = init();
   if(re == NULL) {
      printf("Konnte keinen neuen binaeren Baum erzeugen!\n");
      return EXIT_FAILURE;
   }
   else
      printf("Binaerbaum wurde erfolgreich initialisiert\n");

   do {
      printf("\n-1- Neue PLZ hinzufuegen\n");
      printf("-2- PLZ suchen\n");
      printf("-3- PLZ loeschen\n");
      printf("-4- Ende\n\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);

      if(wahl == 1) {
         printf("Bitte geben Sie eine neue PLZ ein : ");
         do{ scanf("%5u",&p); }while( (getchar()) != '\n' );
         printf("Der Ort dazu : ");
         fgets(o, MAX, stdin);
         r=einfuegen(re, p, strtok(o, "\n") );
         if(r == 0)
            return EXIT_FAILURE;
       }
       else if(wahl == 2) {
          printf("Für welche PLZ suchen Sie einen Ort : ");
          scanf("%5u",&p);
          binaere_suche_plz(re, p);
       }
       else if(wahl == 3) {
          printf("Welche PLZ wollen Sie loeschen : ");
          scanf("%5d",&p);
          bin_delete(re, p);
       }
    } while(wahl != 4);
   return EXIT_SUCCESS;
}

Galileo Computing - Zum Seitenanfang

22.4.8 Binäre Suchbäume mit Eltern-Zeiger und Threads Zur nächsten ÜberschriftZur vorigen Überschrift

Es gibt noch mehrere andere Wege, binäre Bäume zu implementieren, um sich z. B. das Traversieren des Baums zu erleichtern. Bereits gesehen haben Sie das Durchlaufen der Bäume mittels Preorder- und Inorder-Traversierung. Wenn Sie aber das Durchlaufen (Traversieren) eines Baums iterativ und nicht mehr rekursiv vornehmen wollen, können Sie die Struktur um einen Zeiger zum Elternknoten erweitern:

struct binaer_knoten{
   char ort[255];
   unsigned int plz;
   struct binaer_knoten *links;
   struct binaer_knoten *rechts;
   struct binaer_knoten *eltern;
};

Jetzt kann jeder Knoten sein Umfeld kontrollieren. Dieser Eltern-Zeiger vereinfacht das Traversieren des Baums, doch der Schreibaufwand für das Programm steigt. Außerdem wird auch das Einfügen und Löschen eines Elements verlangsamt, da ein Zeiger mehr verwaltet werden muss. Dem Eltern-Zeiger der Wurzel übergeben Sie hingegen den NULL-Zeiger.

Mit Threads (Threading) haben Sie die Möglichkeit, einen Baum noch schneller zu traversieren. Denn anstatt zu überprüfen, ob der linke oder rechte Teil eines Knotens leer (NULL) ist, was zu einer schlechteren Laufzeit führen könnte, müssen Sie nur zwei Extra-Bits (Bit-Felder) in die Struktur einfügen:

struct binaer_knoten{
   char ort[255];
   unsigned int plz;
   struct binaer_knoten *links;
   struct binaer_knoten *rechts;
   unsigned linker_thread:1;
   unsigned rechter_thread:1;
};

Wenn sich z. B. auf der linken Seite eines Knotens ein weiterer Knoten befindet, steht das Bit linker_tread auf 1. Falls sich dort noch kein Knoten befindet, steht es auf 0. Natürlich lässt sich auf diese Weise nicht generell eine bessere Laufzeit garantieren, da diese davon abhängt, wie der Compiler Bit-Felder optimiert. Aber eine Erleichterung dürfte es auf jeden Fall darstellen.


Galileo Computing - Zum Seitenanfang

22.4.9 Ausgeglichene Binärbäume Zur nächsten ÜberschriftZur vorigen Überschrift

Es gibt leider einen negativen Aspekt bei den binären Bäumen, die Sie eben kennengelernt haben. Betrachten Sie bitte den Binärbaum aus Abbildung 22.24.

Abbildung 22.24 Entarteter Binärbaum

Bei diesem Beispiel handelt es sich tatsächlich um einen binären Baum und nicht, wie Sie vielleicht vermuten würden, um einen verkettete Liste. Der Baum hat die Tiefe 4 und könnte normalerweise 15 Elemente aufnehmen (24–1). Es handelt sich dabei um einen entarteten Baum. So etwas kann passieren, wenn ein relativ kleiner oder großer Wert als Wurzel des Baums verwendet wird. Zugegeben, dieses Beispiel ist ein ungünstiger Fall, aber es könnte dazu kommen.

Es gibt, um entartete Binärbäume auszugleichen, Algorithmen, die allerdings nicht einfach zu verstehen sind. Aber was heißt perfekt ausbalanciert (ausgeglichen) im Sinne von Binärbäumen? Ein Binärbaum ist perfekt ausgeglichen, wenn sich die Höhen (oder auch Tiefen) der linken und rechten Teilbäume höchstens um den Wert 1 unterscheiden. Solche Bäume werden AVL-Bäume genannt.

Um also Probleme zu vermeiden, müssen Sie den Baum immer ausgeglichen halten. Dies ist allerdings auch mit einem erhöhten Speicheraufwand verbunden. Denn wenn ein neues Element eingefügt oder ein Element gelöscht wird, kann es sein, dass der komplette Baum wieder neu organisiert werden muss. Diesen Aufwand sollten Sie jedoch nur betreiben, wenn es denn tatsächlich auf ein schnelleres Suchergebnis ankommt. Ein solches schnelleres Suchergebnis wird durch die Verkürzung der Pfadlänge erreicht.


Galileo Computing - Zum Seitenanfang

22.4.10 Algorithmen für ausgeglichene Bäume – eine Übersicht topZur vorigen Überschrift

Zu diesem Thema könnte man ganze Bücher schreiben. Einige weiterführende Hinweise sollen zu den binären Bäumen dennoch gegeben werden.

AVL-Bäume

Ein AVL-Baum (AVL nach seinen Erfindern Adelson-Velsky und Landis) ist ein Suchbaum, dessen Knoten sich in der Höhe (Tiefe) von derjenigen der Teilbäume um höchstens 1 unterscheidet, also ein perfekt ausbalancierter Baum. Wird diese Bedingung verletzt, muss eine Ausgleichsfunktion ausgeführt werden. Folgende drei Bedingungen können dabei auftreten (auch Balance-Grad genannt):

  • balance > 0 – Der rechte Teilbaum besitzt eine größere Höhe als der linke.
  • balance < 0 – Der linke Teilbaum besitzt eine größere Höhe als der rechte.
  • balance = 0 – Die Teilbäume haben die gleiche Höhe und sind optimal ausbalanciert. Dieser Zustand wird angestrebt.

Um gegen diese Verletzung vorzugehen, werden sogenannte Rotationen vorgenommen. Dabei müssen Sie zwischen rechtsseitiger Rotation (betrifft die rechte Seite des Teilbaums eines Knotens) und linksseitiger Rotation (betrifft die linke Seite des Teilbaums eines Knotens) unterscheiden. Außerdem gibt es noch einfache und doppelte Rotationen. Dass all diese Operationen sehr rechenintensiv sind, lässt sich wohl leicht erschließen.

B-Bäume (Bayerbäume)

Wenn Sie sich für die Programmierung einer eigenen Datenbank interessieren, dann sollten Sie sich mit diesem Baum befassen. Der B-Baum wird durch eine variable Anzahl von Elementen (Blättern) pro Knoten an die Blockgröße des Dateisystems angepasst. Dadurch ist eine effektive und optimale Geschwindigkeitsausnutzung auf verschiedenen Systemen möglich. Die einzelnen Knoten eines B-Baums sind nicht immer belegt und variieren zwischen dem Kleinst- und dem Höchstwert. Somit ist immer Platz für Änderungen von Strukturen bei Manipulationen (Einfügen, Löschen, Ändern …) an der Datenbank vorhanden.

Dies waren lange noch nicht alle Algorithmen, mit denen Sie ausgeglichene Bäume erstellen können. Zu erwähnen sind hier noch die Top-Down 2-3-4-Bäume und die Rot-Schwarz-Bäume.



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.






<< zurück
  
  Zum Katalog
Zum Katalog: C von A bis Z

 C von A bis Z
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchtipps
Zum Katalog: Einstieg in C++






 Einstieg in C++


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


Zum Katalog: C/C++






 C/C++


Zum Katalog: Shell-Programmierung






 Shell-Programmierung


Zum Katalog: Linux-UNIX-Programmierung






 Linux-UNIX-
 Programmierung


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


Zum Katalog: Ubuntu GNU/Linux






 Ubuntu GNU/Linux


Zum Katalog: Coding for Fun







 Coding for Fun 


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Galileo Press 2009
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de