Binäre Bäume

Einführung
Implementierung in Perl

Einführung

Als Beispiel einer Anwendung komplexer Datenstrukturen soll hier ein sogenannter binärer Suchbaum dienen, der zum Sortieren von Daten benutzt wird. Dies kann dann sinnvoll sein, wenn so große Datensätze verwaltet und sortiert werden müssen, daß sie nicht mehr im Hauptspeicher des Rechners bearbeitet werden können.

Ein sortierter binärer Baum ist durch miteinander verknüpfte Datensätze (oft "Knoten" genannt) gekennzeichnet. Jeder dieser Knoten enthält im folgenden Beispiel eine Zahl sowie Referenzen auf bis zu zwei "Nachfolger". Hier soll der sogenannte "linke" eine Referenz auf einen Knoten sein, der eine kleinere Zahl beinhaltet, und der "rechte" eine größere Zahl (wir gehen hier der Einfachheit halber davon aus, daß keine Zahl mehrmals auftritt).

Ein solcher Baum läßt sich schrittweise von der "Wurzel" aus (hier: Nummer 9) aufbauen. Wie man sieht, befinden sich in den Teilbäumen, die an den Knoten jeweils links hängen, nur kleinere Zahlen als im betreffenden Knoten und im jeweils rechten Teilbaum nur größere. Diejenigen Knoten, die keine Nachfolger mehr besitzen (hier: 1, 3 und 14) werden "Blätter" genannt.

[Seitenanfang]

Implementierung in Perl

Als erstes definieren wir eine geeignete Datenstrukur für die einzelnen Knoten des Baumes. Hier bietet sich die Verwendung eines Hash an. Da der Zugriff schließlich über Referenzen erfolgt, benutzt man am besten gleich einen anonymen Hash (man beachte die geschweiften Klammern anstelle von runden):

$ref_hash = { 'zahl'   => $zahl,
              'links'  => $ref_links,
              'rechts' => $ref_rechts  };

Im fertigen Baum wird dann jeder einzelne Knoten durch eine Referenz auf einen solchen Hash dargestellt, wobei $zahl jeweils die (zu sortierende) Zahl enthält und $ref_links sowie $ref_rechts auf die beiden Nachfolger zeigen. Ist nur ein oder gar kein Nachfolger (wie in einem Blatt) vorhanden, so seien die entsprechenden Referenzen gleich "undef".

Um einen solchen Knoten mit einer entsprechenden Zahl zum Leben zu erwecken, definieren wir folgendes Unterprogramm:

sub knoten {
    return ( { 'zahl'   => $_[0],
               'links'  => undef,
               'rechts' => undef  } );
}

D.h., der Aufruf knoten(9) liefert eine Referenz auf einen Hash, dessen Schlüssel zahl den Wert 9 hat und dessen Werte von links und rechts nicht definiert sind.

Damit kann man schon die Wurzel des Baumes erzeugen:

#!/usr/local/bin/perl -w

use strict;

sub knoten {
    return ( { 'zahl'   => $_[0],
               'links'  => undef,
               'rechts' => undef  } );
}

my $ref_wurzel = knoten(9);

Um aus den restlichen Elementen einer zu sortierenden Liste den Suchbaum aufzubauen, beginnt man jeweils bei der Wurzel und vergleicht die neue Zahl mit der Zahl in der Wurzel. Ist das neue Element kleiner, so geht man zum linken Nachfolger und wiederholt den Vergleich, ansonsten geht man zum rechten Nachfolger. Dieses Verfahren wird so lange wiederholt, bis man auf eine undefinierte Referenz stößt. Dort wird dann das neue Element als Blatt an den Baum gehängt, indem in dem letzten Knoten die entsprechende Referenz links oder rechts mit Hilfe des knoten()-Unterprogramms definiert wird.

In Perl ließe sich dieser Algorithmus zum Beispiel wie folgt programmieren:

#!/usr/local/bin/perl -w

use strict;

my @liste = ( 9, 10, 7, 14, 2, 3, 1 );

sub knoten {
    return ( { 'zahl'   => $_[0],
               'links'  => undef,
               'rechts' => undef  } );
}

sub erstelle_baum {
    my $ref_liste = shift;

    my $zahl = shift(@$ref_liste);    ### Wurzel erstellen
    my $ref_wurzel = knoten($zahl);

    foreach $zahl (@$ref_liste) {
        my $ref = $ref_wurzel;      ### beginne bei Wurzel

        while(1) {                 ### (Endlosschleife)
            ### Vergleich der Zahlen
            if($zahl < $$ref{'zahl'}) {
                if(defined($$ref{'links'})) {
                    ### gehe nach links
                    $ref = $$ref{'links'};
                }
                else {    ### neues Blatt
                    $$ref{'links'} = knoten($zahl);
                    last;   ### verlasse while(1) { }
                }
            }
            else {
                if(defined($$ref{'rechts'})) {
                    ### gehe nach rechts
                    $ref = $$ref{'rechts'};
                }
                else {    ### neues Blatt
                    $$ref{'rechts'} = knoten($zahl);
                    last;   ### verlasse while(1) { }
                }
            }
        }
    }
    return($ref_wurzel);
}

my $ref_wurzel = erstelle_baum(\@liste);  ### Hauptprogramm

Durch den Rückgabewert der Subroutine (eine Referenz auf die Wurzel) kann später auf den Suchbaum zugegriffen werden.

Nun benötigen wir natürlich noch Programmcode, mit dessen Hilfe die im Suchbaum sortierten Daten ausgegeben werden können. Dabei geht man am besten nach folgender Methode vor: Beginnend bei der Wurzel betrachte man einen (aktuellen) Knoten. Besitzt dieser Knoten einen linken Teilbaum, mache den linken Nachfolger zum aktuellen Knoten und wiederhole die Abfrage. Falls kein linker Nachfolger vorhanden ist (links ist undef), gebe die Zahl des aktuellen Knotens aus. Anschließend teste, ob ein rechter Teilbaum vorhanden ist. Falls ja, wird der rechte Nachfolger zum aktuellen Knoten, sonst geht man zum letzten (darüberliegenden) Knoten zurück. Wie man zeigen kann, wird mit Hilfe dieses Verfahrens der gesamte Suchbaum durchlaufen und alle Elemente werden dabei (sortiert) ausgegeben.

Implementierung in Perl:

#!/usr/local/bin/perl -w

use strict;

my @liste = ( 9, 10, 7, 14, 2, 3, 1 );

sub knoten {
    return ( { 'zahl'   => $_[0],
               'links'  => undef,
               'rechts' => undef  } );
}

## 'sub erstelle_baum { ... }' wie im letzten Beispiel

my $ref_wurzel = erstelle_baum(\@liste);

sub ausgabe {
    ### 'my' hier wichtig wegen Rekursion !
    my $ref = shift;

    ### suche links (rekursiv)
    if(defined($$ref{'links'})) {
        ausgabe($$ref{'links'})
     }
    ### Ausgabe der Zahl
    print "$$ref{'zahl'}\n";
    ### suche rechts (rekursiv)
    if(defined($$ref{'rechts'})) {
        ausgabe($$ref{'rechts'})
    }
}

ausgabe($ref_wurzel);

[Seitenanfang]

Autor: Eike Grote

Version: 2.07 (27.10.2019)