Binäre Bäume
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).
9
/ \
7 10
/ \
2 14
/ \
1 3
|
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]