Binäre Suchbäume

Binäre Suchbäume dienen der effizienten Implementierung von sogenannten DICTIONARIES, das sind Datentypen zur Darstellung von Mengen, welche die Operationen INSERT, DELETE und MEMBER, also Einfügen eines Elementes, Löschen eines Elementes und den Test auf "Enthaltensein" eines Elementes zu Verfügung stellen.

Alle drei Algorithmen für INSERT, DELETE und MEMBER folgen jeweils einem einzigen Pfad im Baum von der Wurzel zu einem Blatt oder zu einem inneren Knoten. Der Aufwand ist proportional zu der Länge dieses Pfades. Bekannterweise ist die maximale Pfadlänge in einem balancierten Baum O(log n) und O(n) in einem degenerierten Baum, wobei n hier die Anzahl der Knoten des Baumes ist. Ein degenererierter Baum entsteht z.B. wenn die Folge der einzufügenden Knoten bereits sortiert vorliegt.

Im folgenden Script wurden die drei Operationen in perl implementiert. 

#!/usr/bin/perl

use strict;
use warnings;
use Data::Dumper;;

# search for $x in tree $t. If $x is found,
# returns 1, otherwise returns 0

sub member {

    my ($t,$x) = @_;

    if (!defined($t)) { return 0;}
    elsif ($x eq $t->{key}) { return 1;}
    elsif ($x le $t->{key}) { return &member($t->{left},$x) }
    else { return &member($t->{right},$x) } # $x > $t->{key} 

}

# search for $x in tree $t. If $x is found, returns node
# containing $x1, otherwise returns undef

sub find {

    my ($t,$x) = @_;
    if (!defined($t)) { return undef;}
    elsif ($x eq $t->{key}) { return $t;}
    elsif ($x le $t->{key}) { return &member($t->{left},$x) }
    else { return &member($t->{right},$x) } # $x > $t->{key} 
}

# insert $element $x in tree $t

sub insert {
    
    my $t = \$_[0];
    my $x = \$_[1];

    if (!defined($$t)) {

        # empty tree, create node andinsert $x in it

        $$t = {};
        $$t->{key} = $$x;
        $$t->{left} = undef;
        $$t->{right} = undef;

    } else {

        # if element not already in tree

        if ($$t->{key} ne $$x) {

            # insert element in the correct subtree

            if ($$t->{key} gt $$x) {
                &insert($$t->{left},$$x);
            } else {
                &insert($$t->{right},$$x);
            }
        }
    }

}

# create a file suitable for "dot"

sub traverse {

    my ($t) = @_;
    if (!defined($t)) { return undef;}
    if (defined $t->{left}) {
        print $t->{key}." -> ".$t->{left}->{key}."\n";
        &traverse($t->{left});
    }
    if (defined $t->{right}) {
        print $t->{key}." -> ".$t->{right}->{key}."\n";
        &traverse($t->{right}); 
    }
}

sub print_graph {

    print EOT;
digraph hierarchy {
//nodesep=1.0 // increases the separation between nodes
node [color=black,fontcolor=black]
edge [color=black] //setup options
EOT
    &traverse($_[0]);

    print EOT;
}
EOT

}

# main program

my $tree = undef;

#srand (time ^ $$);
#foreach (1 .. 12) {&insert($tree, int(rand 100))}

foreach (
    qw(Binaere Suchbaeume dienen der
    Implementierung von DICTIONARIES)) {
    &insert($tree,lc $_);
}

&print_graph($tree);
Im obenstehenden Script wird ein kleiner Beispieltext Wort für Wort in einen binären Suchbaum eingefügt. Das Bild links zeigt den dadurch erzeugten Baum.

Die Subroutine print_graph gibt den Baum dann im dot-Format aus. Damit kann beispielsweise eine graphische Darstellung des Baumes wie die nebenstehende im gif-oder PostScript-Format erzeugt werden.

Alle Touren

Schneebergwege

Raxsteige

Geführte Touren

Perl

Literatur

Musik