Definition Suchbäume

Suchbäume sind binäre Bäume, deren Knoten mit Werten beschriftet sind. Darüber hinaus zeichnen sich Suchbäume dadurch aus, dass sie sortiert sind: Für jeden Knoten gilt, dass alle Werte im rechten Teilbaum größer und alle Werte im linken Teilbaum kleiner sind als sein Wert.

Hierbei ist es wichtig, dass dies für jeden Knoten im Suchbaum gilt.

Wir gehen zunächst davon aus, dass jeder Wert nur einmal im Suchbaum vorkommt, im Gegensatz zu den Listen, die wir sortiert haben und bei denen Werte mehrfach vorkommen durften.

Beispiele zu Suchbäumen

Suchbaum

Suchbaum

kein Suchbaum

Der Binärbaum in Abbildung 30.3 ist kein Suchbaum, obwohl für jeden Knoten im Suchbaum gilt, dass sein linkes Kind kleiner und sein rechtes Kind größer als der Knoten ist. Der Fehler ist, dass die 3 im rechten Teilbaum der Wurzel vorkommt, aber kleiner als der Wert der Wurzel (8) ist. Korrigieren könnte man dies z.B. dadurch, dass man die 3 als rechten Kindknoten der 1 einfügt.

Suchen

Ein Suchbaum ist eine direkte Repräsentation für das Prinzip der binären Suche.

Jede Suche beginnt beim Wurzelknoten. Durch einen Größer/Kleiner/Gleich-Vergleich wird entschieden, ob es danach im rechten oder im linken Teilbaum weitergeht, oder ob der Wert bereits gefunden wurde.

Beispiel:

Im Suchbaum aus Beispiel 30.1 soll die 5 gesucht werden:

  1. Die 5 ist kleiner als die 8, also wird der linke Teilbaum gewählt.
  2. Die 5 ist größer als die 3, also wird der rechte Teilbaum gewählt.
  3. Die 5 ist gleich der 5, also wurde die 5 gefunden.

Das Suchen im Suchbaum funktioniert also genau wie die binäre Suche in einer Liste, mit dem Vorteil, dass der Index des nächsten Wertes nicht ausgerechnet werden muss, sondern direkt der nächste Kindknoten verwendet wird. Dabei ist es für die Laufzeit wichtig, dass der Baum einigermaßen ausgeglichen ist, also dass sich links und rechts ungefähr gleich viele Knoten befinden. Der folgende Baum zum Beispiel erfüllt alle Eigenschaften eines Suchbaums, eignet sich aber nicht zum schnellen Suchen:

Entarteter Suchbaum

Wir gehen zunächst für die Laufzeitbetrachtungen davon aus, dass Suchbäume relativ ausgeglichen sind, ein solcher Fall also nicht auftritt. Tatsächlich kann man Suchbäume nach Einfüge- und Lösch-Operationen immer wieder geschickt umbalancieren, so dass sie ausgeglichen bleiben. Dies werden wir im nächsten Kapitel betrachten. Zunächst werden wir aber Prozeduren entwickeln, die das Suchen, Hinzufügen und Löschen eines Wertes in einem Suchbaum im Fall eines ausgeglichenen Suchbaums mit der Laufzeit \(\O(\log n)\) realisieren.

Einfügen

Zum Einfügen eines Wertes in einen Suchbaum muss zunächst mit der binären Suche die richtige Stelle gefunden werden. Sobald die Suche ins Leere läuft, kann der Wert genau an dieser Stelle als neues Blatt des Baumes eingefügt werden.

Beispiel:

Im Suchbaum aus Beispiel 30.1 soll die 30 eingefügt werden:

  1. Die 30 ist größer als die 8, also wird der rechte Teilbaum gewählt.
  2. Die 30 ist kleiner als die 42, also wird der linke Teilbaum gewählt.
  3. Die 30 ist größer als die 10, also wird der rechte Teilbaum gewählt.
  4. Der rechte Teilbaum ist leer, also kann die 30 hier eingefügt werden.

Einfügen

Jeder Knoten, der hinzugefügt wird, bietet durch die Binärstruktur des Baumes genau zwei neue Positionen, an denen wieder Blätter angehängt werden können. So ist sichergestellt, dass jeder beliebige Wert genau einen Platz hat, an dem er eingefügt werden kann. Genau wie bei einer Liste existieren immer \(n+1\) Positionen, an denen neue Werte eingefügt werden können, wobei \(n\) die Anzahl der schon vorhandenen Werte ist.

Man kann dies auch anders ausdrücken: Jeder Binärbaum mit \(n\) Knoten hat \(n+1\) nicht vorhandene Kindknoten.

Löschen

Soll ein Knoten aus dem Suchbaum gelöscht werden, so müssen wir sicherstellen, dass nach dem Löschen der Baum weiterhin zusammenhängend ist, d.h. es darf außer dem Wurzelknoten keinen Knoten ohne Elternknoten geben. Außerdem muss die Sortierung erhalten bleiben. Wir können unterschiedliche Fälle unterscheiden:

  1. Blätter (also Knoten ohne Kindknoten) können einfach gelöscht werden.

  2. Bei Knoten, die nur einen Kindknoten haben, kann dieser Kindknoten mit seinem kompletten nachfolgenden Teilbaum an die Stelle des zu löschenden Knotens gesetzt werden.

    Löschen von Blättern

  3. Zum Löschen von Knoten mit zwei Kindknoten gibt es im wesentlichen zwei Varianten:

    • Der Knoten mit dem größten Wert aus dem linken Teilbaum kann an die Stelle des gelöschten Knoten wandern, da er größer ist als alle Werte im linken Teilbaum und gleichzeitig kleiner als alle Werte im rechten Teilbaum. Dasselbe gilt natürlich auch für den Knoten mit dem kleinsten Wert des rechten Teilbaums.

      Löschen innerer Knoten

      Beachte hierbei, dass der Knoten mit dem größten Wert im linken Teilbaum selber noch einen linken Teilbaum haben kann. Wenn man diesen also löscht, muss man Fall 2 für einen Knoten mit einem Kindknoten anwenden.

    • Eine andere Möglichkeit ist, den kompletten rechten Teilbaum als rechten Unterbaum an den rechtesten Knoten des linken Teilbaums zu hängen. Dann hat der zu löschende Knoten nur noch einen Kindknoten und kann wie in Fall 2 gelöscht werden.

Verschieben des nächst kleineren

Einfügen rechter in linken Teilbaum

Implementierungen

Im Suchbaum hat eineinfügen in linken Teilbaum Knoten bis zu zwei Kindknoten. Dies stellt man in der Regel im Speicher etwas anders dar. Man unterscheidet zwei Arten von Knoten:

  • innere Knoten, welche eine Beschriftung v und exakt zwei Kindknoten l und r haben: node(l,v,r)
  • Blätter, welche weder Beschriftung noch Kindknoten haben: empty()

Einen Suchbaum mit den Werten 3 und 5 können wir dann wie folgt repräsentieren:

node(empty(),3,node(empty(),5,empty())

Konkret können wir die beiden Knoten repräsentieren als:

  • verschachtelte Liste:

    Jeder Knoten wird durch eine Liste mit den drei Einträgen Wert, linkes Kind und rechtes Kind dargestellt. Die Einträge linkes Kind und rechtes Kind sind dann wieder dreielementige oder leere Listen. Diese Implementierung werden wir als nächstes realisieren.

  • verschachteltes Dictionary:

    Jeder Knoten wird durch ein Dictionary mit den drei Einträgen Wert, linkes Kind und rechtes Kind dargestellt. Die Einträge linkes Kind und rechtes Kind sind dann wieder solche oder leere Dictionaries. Zur vollständigen Implementierung siehe Übung.

  • Klasse:

    Jeder Knoten wird durch ein Objekt repräsentiert. Es enthält drei Attribute, zwei für die beiden Teilbäume und eins für den Wert.

Suchbäume als verschachtelte Listen

Suchbäume können in Python als verschachtelte Listen dargestellt werden. Alternativ kann man sehr ähnlich auch Tupel verwenden, was wir hier aber zunächst nicht weiter betrachten.

In unserer Implementierung stellen wir jeden Knoten, welcher einen Wert enthält, als Liste der Länge drei dar. Also auch die Blätter in unseren Suchbäumen, die eigentlich keine Kindknoten haben. Die Blätter in unserer Implementierung sind also vielmehr leere Listen, welche noch unterhalb der Blätter des Baumes verwendet werden. Hierdurch hat tatsächlich jeder Knoten im Binärbaum entweder zwei oder kein Kind.

Als Beispiel betrachten wir den folgenden Suchbaum:

Bild fehlt noch

Mit verschachtelten Listen würde er dann wie folgt repräsentiert:

Suchbaum verschachtelte Listen

Um Binärbäume in dieser Form konstruieren zu können ist es sinnvoll zunächst einen Satz Hilfsfunktionen zu definieren, die uns helfen, solche Bäume zu konstruieren.

def node(l,v,r) :
    return [l,v,r]

def empty() :
    return []

Unter Verwendung dieser Funktionen können wir obigen Suchbaum konstruieren mittels

t = node(node(empty(),2,empty()),5,node(empty(),10,empty())

Da man mit diesen Funktionen also recht elegant Datenstrukturen konstruieren kann, nennt man solche Funktionen auch Smartkonstruktoren. Wie wir später sehen werden, verstecken Sie auch gewissermaßen die Implementierung, was dann auch durch passende Selektoren zum Selektieren der Kindbäume bzw. des Wertes und Testfunktionen zum Unterscheiden der beiden Knotentypen, elegant ergänzt werden kann:

# Selektoren
def left(l) :
    return l[0]

def right(l) :
    return l[2]

def value(l) :
    return l[1]

# Testfunktion
def is_empty(tree) :
    return tree == []

Die Verwendung unserer Hilfsfunktionen erleichtert nun die Realisierung der Funktion zum effizienten Suchen eines Wertes im Suchbaum:

def elem(v,tree) :
    if is_empty(tree) :
        return False
    elif v < value(tree) :
        return elem(v,left(tree))
    elif v > value(tree) :
        return elem(v,right(tree))
    else :
        return True # hier gilt v == value(tree)

Durch die Hilfsfunktionen sehen wir in der Implementierung der Funktion elem gar nicht mehr, wie genau wir den Suchbaum implementiert haben und produzieren sehr gut lesbaren Code.

Als nächsten Schritt wollen wir eine Prozedur add definieren, welche einen Wert zu einem Suchbaum hinzufügt. Unsere Implementierung wird dies mutierend realisieren, weshalb wir hier von einer Prozedur sprechen. Wir beginnen mit dem Absteigen, analog zur Implementierung von elem. Wir gehen ja davon aus, dass Werte nicht mehrfach in unseren Suchbäumen vorkommen. Sollte der Wert, den wir einfügen wollen also bereits im Baum vorhanden sein, können wir dies mit dem Rückgabewert False anzeigen. Waren wir erfolgreich liefert unsere Funktion `True+:

def add(v,tree) :
    if is_empty(tree) :
        ??? # Einfuegen des neuen Knotens
        return True
    elif v < value(tree) :
        return add(v,left(tree))
    elif v > value(tree) :
        return add(v,right(tree))
    else :
        return False # hier gilt v == value(tree)

An der Stelle ??? ist uns nicht klar, wie wir den neuen Knoten node(empty(),v,empty()) einfügen können. Der übergeordnete Knoten verweist auf die leere Liste, an die die Variable tree nun gebunden ist. In unserer Implementierung müssen wir diese Liste zu der Liste node(empty(),v,empty()) mutieren, damit der übergeordnete Knoten auf unseren neuen Knoten verweist.

Hierzu erweitern wir unsere Hilfsfunktionen um eine spezielle Mutationsfunktion

def empty_to_value(tree,v) :
    if tree==[] :
      tree.extend([empty(),v,empty()])

Hierbei ist die Funktion extend eine mutierende Methode der list Klasse, d.h. das vorhandene Listenobjekt bleibt erhalten, aber wird verändert (mutiert). Mit dieser Funktion ist es dann möglich unsere Definition fertig zu stellen:

def add(v,tree) :
    if is_empty(tree) :
       empty_to_value(tree,v)
       return True
    elif v < value(tree) :
        return add(v,left(tree))
    elif v > value(tree) :
        return add(v,right(tree))
    else :
        return False # hier gilt v == value(tree)

Dieser Einfügeschritt sähe dann für das Einfügen des Wertes 7 in den Suchbaum von oben wie folgt aus:

Einfügen bei verschachtelten Listen

Bei allen Implementierungen (also auch mit Dictionaries, siehe Übung) ist es wichtig, dass das Einfügen eines neuen Wertes unbedingt als Mutation der bereits vorhandenen Objekte/Einträge geschieht, da der neue Eintrag sonst nicht mit seinem Elternknoten verbunden werden kann. Wenn man neue Einträge/Objekte verwenden will, muss man die Rekursion bereits eine Ebene höher beenden und den linken/rechten Kindknoten ersetzen. Dies ist aber in der Regel sehr viel aufwendiger, so dass es besser ist, leere Blätter zu verwenden, welche man in nicht-leere Knoten mutieren kann.

Wir haben nun einige Funktionen definiert, welche ein potentieller Nutzer unserer kleinen Bibliothek verwenden könnte. Hierbei ist es aber nur sinnvoll, dass ein Benutzer die Funktionen elem und add verwendet. Außerdem könnte er noch empty zur Konstruktion eines leeren Suchbaums verwenden. Von einer Verwendung der Funktion node sollte ein Benutzer aber absehen, da man mit ihr auch ungültige Suchbäume konstruieren kann. Wir verwenden die Funktion node lediglich, innerhalb unserer eigenen Definition. Deshalb ist es sinnvoll eine klare Benutzerschnittstelle zur Verfügung zu stellen und hierzu ein Synonym für die Funktion empty zu definieren, welches für den Benutzer unserer Bibliothek gedacht ist:

# Konstruktor fuer den Benutzer
def empty_search_tree() :
  return empty()

Damit stehen dem Benutzer nun drei Funktionen empty_search_tree, elem und add zur Verfügung. In den Übungen kommt noch delete hinzu.

Das Abstraktionskonzept hinter dieser Aufteilung werden wir später noch bei der Betrachtung abstrakter Datentypen vertiefen.

Zum Abschluss des Kapitels beginnen wir noch mit einer Implementierung der Suchbäume mit Klassen. Klassen geben uns die Möglichkeit Objekte mit Zustand zu definieren. Die einzelnen Komponenten unserer Listen (linkes Kind, Wert und rechtes Kind) werden dabei Attribute des zugehörigen Objekts der Klasse. Außerdem verwenden wir noch ein weiteres boolesches Attribut empty, welche uns zusätzlich anzeigt, ob der jeweilige Knoten leer ist (entspricht empty) oder nicht (node).

class SearchTree:

    def __init__(self):
        self.empty = True
        self.value = None
        self.left = None
        self.right = None

    def elem(self, value):
      ...

    def add(self, value):
      ...

Der Konstruktor entspricht hier dem Anlegen eines leeren Suchbaums, also der Funktion empty. Die Attribute left und right werden dann später auch andere Objekte der Klasse SearchTree enthalten, wodurch die Baumstruktur repräsentiert wird. Verändert man diese Attribute entspricht dies genau der Mutation der leeren Liste in eine nichtleere Liste mit Hilfe der Funktion empty_to_value. Die Methoden elem und add werden dann in den Übungen realisiert.