Folge 19:

Bäume

19.1 Binärbäume - Allgemeines

Unter Bäumen versteht man in der Informatik Datenstrukturen, bei denen jedes Element mindestens zwei Nachfolger hat. Bereits in der Folge 17 haben wir ähnliche Datenstrukturen kennen gelernt, nämlich die doppelt verketteten Listen. Eine solche doppelt verkettete Liste besteht aus Elementen oder Knoten, die a) den eigentlichen Inhalt (zum Beispiel eine int-Zahl, einen String oder ein Objekt) und b) die Adresse des vorhergehenden und des nachfolgenden Elements (Knotens) speichern. Die Abbildung 19-1 zeigt im oberen Teil eine solche doppelt verkettete Liste.

Kommen wir jetzt zur formalen Definition des Begriffs "Binärbaum".

Binärbaum

Ein Binärbaum ist

- entweder leer

- oder besteht aus einer Wurzel mit einem rechten und einem linken Binärbaum.

    Diese Definition ist höchst interessant, es handelt sich nämlich um eine rekursive Definition.

    Das Ganze wird etwas klarer, wenn man sich einen solchen Binärbaum mal im Bild anschaut.

    1 Ein Binärbaum mit 10 Elementen

    Die Elemente eines Binärbaums werden auch als Knoten bezeichnet. Es gibt drei Typen von Knoten:

    Die Wurzel ist der Ursprung des Baumes. Sie hat zwar zwei Nachfolger, aber keinen Vorgänger.

    Ein innerer Knoten hat einen Vorgänger und zwei Nachfolger. Einer der Nachfolger kann leer sein. Somit gibt es zwei verschiedene Typen von inneren Knoten.

    Ein Blatt hat einen Vorgänger und zwei leere Nachfolger.

    1. Binärbäume - Allgemeines
    2. Binäre Suchbäume
    3. Das Einfügen von Elementen
    4. Das Anzeigen von Elementen
    5. Das rekursive Einfügen von Elementen
    6. Das Löschen von Elementen
    7. Implementierung mit Hilfe von Arrays
    8. AVL-Bäume
    9. B-Bäume

     

    19.2 Binäre Suchbäume

    Ein Binärbaum, wie er in der Abbildung 1 dargestellt ist, sieht zwar ganz nett aus und kann auch zum Speichern von Daten verwendet werden, habe aber so gut wie keinen praktischen Nutzen. Um zum Beispiel das Element mit dem Wert 320 wiederzufinden, muss man fast alle Elemente des Baumes untersuchen. Dann hätte man die Daten auch gleich in einer linearen Liste, einer sortierten Liste oder auch in einem Array speichern können. Vorteile bieten nur die binären Suchbäume, eine spezielle Unterklasse der Binärbäume.

    Binärer Suchbaum

    Ein binärer Suchbaum ist ein Binärbaum, bei dem für alle Unterbäume gilt:

    - der linke Unterbaum eines Knotens enthält nur Elemente, deren Wert kleiner als der Wert des Knotens ist.

    - der rechte Unterbaum eines Knotens enthält nur Elemente, deren Wert größer oder genauso groß wie der Wert des Knoten ist.

    Auch hier hilft es viel, wenn man sich einen solchen binären Suchbaum mal im Bild anschaut:

    2 Ein binärer Suchbaum

    Schauen wir uns mal den Wert der Wurzel an: 100. Alle Knoten des linken Unterbaums (rosa) haben einen Wert, der kleiner ist als 100. Alle Knoten des rechten Unterbaums (grün) haben einen Wert, der gleich oder größer als der Wert der Wurzel ist.

    3 Der linke Unterbaum der Wurzel

    In der Abbildung 3 ist der linke Unterbaum der Wurzel farbig hervorgehoben. Innerhalb dieses Unterbaums ist die 50 (gelb) jetzt die Wurzel. Der linke Unterbaum (des linken Unterbaums) besteht aus einem Knoten, nämlich der 30. Der rechte Unterbaum (des linken Unterbaums) besteht aus drei Knoten. Die Werte dieser drei Knoten sind alle größer als der Wert der Wurzel des Unterbaums (50).

    Kommen wir nun zu den Vorteilen solcher binären Suchbäume. Wir wollen einmal die Zahl 88 suchen. In einer sortierten Liste hätten wir dazu 5 Vergleiche benötigt, wie die folgende Abbildung zeigt.

    4 Suchen in einer sortierten Liste

    Bei der Suche im Binärbaum benötigen wie dagegen nur vier Vergleiche. Wir müssen mit der 100 vergleichen. Dabei stellen wir fest, dass 88 kleiner ist als 100. Also suchen wir im linken Teilbaum weiter. Jetzt vergleichen wir die 88 mit der Wurzel des linken Teilbaums, mit der 50 also. Da 88 > 50, müssen wir im rechten Teilbaum (70, 60, 88) weitersuchen. Der Vergleich mit dessen Wurzel 70 (dritter Vergleich) führt dazu, dass wir im rechten Teilbaum weitersuchen. Der Vergleich mit dessen Wurzel (88) führt zum gewünschten Ergebnis.

    Zugegeben, besonders viel günstiger war das Suchen der Zahl 88 im Baum nicht im Vergleich zur Liste. Aber suchen wir einmal nach allen Zahlen und protokollieren wir die Zahl der Vergleiche für die Liste und für den Binärbaum in einer Tabelle:

    Zahl Vergleiche in der Liste Vergleiche im Baum
    30 1 3
    50 2 2
    60 3 4
    70 4 3
    88 5 4
    100 6 1
    150 7 3
    210 8 2
    250 9 4
    300 10 3
    Durchschnitt 5,5 2,9

    5 Vergleich der Suchzeiten

    Man sieht sofort, dass das Suchen in dem Binärbaum im Durchschnitt viel schneller geht als in einer einfachen sortierten Liste. Würde man die sortierte Liste allerdings auch hinten beginnend durchsuchen können, so würde das Ergebnis nicht mehr so eindeutig für den Baum sprechen, da sich die durchschnittliche Suchzeit in der Liste halbieren würde. Bei diesen 10 Zahlen wäre eine solche Liste sogar noch günstiger als der Binärbaum. Aber man kann leicht nachrechnen, dass ein Binärbaum bei größeren Mengen an Elementen günstiger ist als jede Liste.

    Stellen wir uns einmal vor, wir müssten 1000 Zahlen in einer Liste unterbringen und könnten diese Liste von vorne und von hinten durchsuchen. Die durchschnitte Zahl der Vergleiche wäre ca. 250 (500, wenn man nur in einer Richtung durchsuchen dürfte).

    Aus wievielen Ebenen (Schichten von Knoten) besteht ein Binärbaum mit 1000 Zahlen? Machen wir uns das wieder mit Hilfe einer Tabelle klar:

    Zahl der Ebenen Kapazität der Ebenen Kapazität des Baumes
    1 1 1
    2 1+2 3
    3 1+2+4 7
    4 1+2+4+8 15
    5 1+2+4+8+16 31
    6 31+32 63
    7 63+64 127
    8 127+128 255
    9 255+256 511
    10 511+512 1023

    6 Exponentielles Anwachsen der Baumkapazität mit der Zahl der Ebenen

    Um die 1000 Zahlen unterzubringen, benötigen wir nur 10 Ebenen, wenn die Zahlen einigermaßen gleichmäßig verteilt sind. Wenn wir Pech haben, sind die Zahlen ungünstig verteilt, und wir brauchen 12, 14 oder sogar 20 Ebenen. Gehen wir einmal vom üngünstigen Fall aus, dass zum Speichern der 1000 Zahlen 20 Ebenen benötigt werden. Das heißt doch, dass zum Finden einer beliebigen Zahl maximal 20 Vergleiche benötigt werden. Durch durchschnittliche Zahl dürfte bei 18 oder weniger liegen. Zur Erinnerung: Bei der sortierten Liste mussten wir durchschnittlich 250 mal vergleichen, um eine Zahl zu finden. Der Binärbaum ist also mehr als 10 mal günstiger als die sortierte Liste. Bei noch größeren Zahlenmengen würde dieses Verhältnis noch günstiger für den Binärbaum ausfallen.

    Abiturienten NRW

    Gehen Sie bitte auch auf die "offizielle" OrderedTree-Seite!

    Übung 19.1 (3 Punkte)

    Analysieren Sie die Tabelle in Abbildung 6 und stellen Sie eine mathematische Formel auf, die Ihnen die Kapazität des Baumes in Abhängigkeit von der Zahl der Ebenen berechnet.


    Übung 19.2 (3 Punkte)

    Programmieren Sie eine Java-Funktion, welche Ihnen die Zahl der benötigten Ebenen ausrechnet, wenn Sie der Funktion die Zahl der unterzubringenden Elemente angeben. Beispiel (Tabelle in Abb. 6): Wenn wir 100 Elemente unterbringen wollen, benötigen wir 7 Ebenen.


    Übung 19.3 (3 Punkte)

    Zeichnen Sie auf ein Blatt Papier den binären Suchbaum, der sich ergibt, wenn man die folgenden Zahlen in genau dieser Reihenfolge eingibt:

    300 - 200 - 100 - 50 - 120 - 70 - 130 - 400 - 500 - 600 - 187 - 34 - 100 - 50

    Kommen Sie bitte nach vorn und zeigen Sie Ihrem Lehrer den gezeichnet Baum. Ihr Lehrer wird Ihnen eine weitere Zahl nennen, und Sie erklären dann bitte, wo Sie diese Zahl einfügen müssen.

    Lösungshinweise zu allen Übungen der Buchversion finden Sie in dem Lehrerband, den Sie von mir gegen einen kleinen Unkostenbeitrag erhalten können.

    Die Übungen der Buchversion unterscheiden sich teils erheblich von den hier veröffentlichen Übungen. Das liegt daran, dass ich die Folge 19 für die Buchversion völlig überarbeitet habe. Sehr schwere Aufgaben sind ganz herausgenommen worden, einige Aufgaben sind umformuliert worden, bei einigen Aufgaben wurde das Bewertungsschema angepasst, weil ich nämlich beim Lösen erst selbst gemerkt habe, wie schwer manche Aufgaben in Wirklichkeit sind, und einige Aufgaben sind auch ganz neu dazugekommen.

    Diese Webseite über Bäume wird nicht weiter entwickelt. Statt dessen können Sie die Buchversion des Skriptes gegen gleichwertiges Tauschmaterial oder einen kleinen Unkostenbeitrag Ivon mir erhalten. Schreiben Sie mir eine E-Mail, wenn Sie Interesse haben.

    Den ersten Teil der Folge 19 können Sie hier kostenlos als PDF-Datei herunterladen.

    und weiter mit Folge 19 - Binärbäume, Teil 2

    Diese HTML-Seite wurde erstellt von Ulrich Helmich am 14. April 2006





    IMPRESSUM