Suchbäume – Akademischer Tag 6

Nachdem es beim letzten akademischen Tag um Hashmaps, einer Struktur zum Lösen des sog. Suchproblems, ging, wird auch dieser Artikel von einer Technik handeln, mit der dieses Problem gelöst werden kann. Dieses Mal wird der Ansatz jedoch auf der Graphentheorie basieren, d.h. wir werden einige Graphen mit besonderen Strukturen kennenlernen, mit denen man das Suchproblem möglichst schnell lösen kann. Bei diesen Graphen wird es sich, wie bereits im Titel angedeutet, um Bäume handeln.

Zuerst möchte ich die Definitions eines gerichteten Baums ins Gedächtnis rufen, damit keine Missverständnisse auftreten: Ein gerichteter Baum, dessen Kantenrichtung zu den Blättern zeigt, ist ein Graph, bei dem es für jeden Knoten x genau einen Pfad von der Wurzel zu x gibt. Bereits aus der Definition ergibt sich eine Eigenschaft, die bei der Suche hilft: Wenn zu jedem Knoten nur ein Pfad existiert, dann kann man nach einem Traversierungsschritt die Knoten, die nicht in derselben Richtung liegen, nicht mehr erreichen (ohne einen Schritt zurückzugehen), womit der Suchraum bei jedem Schritt auf ein Minimum reduziert wird. Optimalerweise wird der Baum derart strukturiert, dass man bei der Traversierung des Baums sofort den richtigen Weg geht, sodass man bei einer Baumhöhe h insgesamt O(h) Schritte zum Suchen eines Schlüssels benötigt, womit der o.g. Vorteil zum Tragen kommt. Eine weitere hilfreiche Eigenschaft ist die Kreisfreiheit, die sich leicht aus der Definition eines Baums folgern lässt. Durch diese Kreisfreiheit kann man die verschiedenen Operationen auf Bäumen sehr einfach rekursiv implementieren, ohne Endlosschleifen zu provozieren, was vor allem Organisationsaufwand spart.

Der Unterschied zwischen Bäumen und Suchbäumen besteht vor allem in ihrer Struktur, denn Suchbäume sind derart strukturiert, dass sich die drei Operationen insert, find und delete effizient auf ihnen implementieren lassen. Bei den gängigsten Arten von Suchbäumen wird die Struktur anhand einer Ordnung auf den Schlüsseln festgelegt. Meist handelt es sich dabei um eine sog. Totalordnung, die wir nachfolgend mit ≤ bezeichnen. Ein Beispiel für eine solche Totalordnung ist die ≤-Relation auf den natürlichen Zahlen. Nimmt man also die Menge der natürlichen Zahlen als Schlüsselmenge, so muss man nur noch den ≤-Vergleichsoperator der jeweiligen Programmiersprache benutzen und schon basiert der Baum auf einer Totalordnung. Benötigt wird eine solche Ordnung, um anhand des gesuchten Schlüssels und des Schlüssels des aktuell besuchten Knotens entscheiden zu können, wo die Suche fortgesetzt werden muss. Als Beispiel wähle ich den binären Suchbaum, der beim nächsten akademischen Tag unter die Lupe genommen wird:

1. Ist x ≤ y und y ≤ x, d.h. x = y, dann ist die Suche beendet.
2. Ist x ≤ y, wird die Suche im linken Teilbaum fortgesetzt.
3. Ist y ≤ x, wird die Suche im rechten Teilbaum fortgesetzt.

Da dies ein Artikel für den akademischen Tag ist, geben wir uns nicht mit dem Nennen von Begriffen zufrieden, sondern erläutern, was eine Totalordnung ist, damit wir Suchbäume nicht nur für natürlich aussehende Schlüsselmengen wie Zahlen verwenden können, sondern auch für komplexere Schlüssel.  Die lexikographische Ordnung von Zeichenketten wäre ein weiteres Beispiel, aber auch Arrays könnten als Schlüsselmengen verwendet werden, sofern man eine Totalordnung dafür angibt. Damit man weiß, ob man eine Totalordnung gefunden hat, definieren wir eine Totalordnung.

Für eine Totalordnung ≤ auf einer beliebigen Menge M gelten folgende Gesetze:

• ≤ ist reflexiv :⇔ ∀ x ∈ M: x ≤ x
  • Jedes Element ist kleiner-gleich sich selbst.
• ≤ ist antisymmetrisch :⇔ ∀ x,y ∈ M: x ≤ y und y ≤ x ⇒ y = x
  • Bsp.: Wenn 42 ≤ y und y ≤ 42, dann ist folglich 42 = y.
• ≤ ist transitiv :⇔ ∀ x,y,z ∈ M: x ≤ y und y ≤ z ⇒ x ≤ z
  • Bsp.: Wenn 1 ≤ 2 und 2 ≤ 3, dann ist folglich 1 ≤ 3.
• ≤ ist total :⇔ ∀ x,y ∈ M: x ≤ y oder y ≤ x
  • Alle Elemente sind miteinander vergleichbar.
  • Bsp.: 21 ≤ 42 oder 42 ≤ 21.

Nehmen wir an, eines dieser Gesetze würde nicht gelten, dann gäbe es an verschiedenen Stellen solcher Suchbäume Probleme:

• ≤ ist nicht reflexiv: Da x ≤ x und x ≤ x nicht gelten, kann x = x nicht gefolgert werden, weshalb man  nicht erkennen würde, wenn man den gesuchten Schlüssel gefunden hat.
• ≤ ist nicht antisymmetrisch: Da sich x = y nicht aus x ≤ y und y ≤ x folgern ließe, wüsste man nicht, ob man den gesuchten Schlüssel gefunden hat oder in welchen Teilbaum man weitersuchen muss.
• ≤ ist nicht total: Es gibt ein Paar x, y für das weder x ≤ y noch y ≤ x gilt. Man kann also weder entscheiden, ob der gesuchte Schlüssel gefunden wurde, noch in welchem Teilbaum man weitersuchen muss.
• ≤ ist nicht transitiv: Sei x ≤ y und y ≤ z, aber es gelte nicht x ≤ z. Dann ist ≤ entweder nicht total oder es gilt stattdessen z ≤ x. Da ≤ jedoch total sein soll, betrachten wir den Fall  z ≤ x. D.h. es würde gelten x ≤ y ≤ z ≥ x, bedeuten würde, dass x im rechten und im linken Teilbaum vom Baum mit der Wurzel z zu finden sein könnte. Vor allem beim Umstrukturierungen des Baums, beispielsweise durch Löschen oder Rotation, könnte das zu Fehlern führen.

Es gibt einige bekannte Suchbäume, die ich nachfolgend nennen und kurz beschreiben möchte:

• Binärer Suchbaum: Basiert auf der Eigenschaft, dass alle Schlüssel des linken Teilbaums kleiner als der Schlüssel der Wurzel sind und alle Schlüssel des rechten Teilbaums größer als der o.g. Schlüssel sind.
• AVL-Baum: Erweitert den binären Suchbaum um Rotationen, die ggf. beim Einfügen oder Löschen von Elementen durchgeführt werden, damit
• Rot-Schwarz-Baum: Bei diesem Baum hat jeder Knoten eine Farbe (rot oder schwarz) für die einige Regeln gelten, durch die sichergestellt wird, dass man O(log n) Schritte zum Finden eines beliebigen Schlüssels benötigt.
• B-Baum: Im Gegensatz zu den bereits genannten Bäumen ist dieser Baum nicht binär, d.h. er kann mehr als zwei Kindknoten haben, wodurch er flacher ist. In jedem Knoten befinden sich weitere Informationen, anhand derer er feststellen kann, welcher Knoten als nächstes besucht werden muss.
• Präfixbaum: Hierbei handelt es sich um einen speziellen Suchbaum, bei dem der Schlüssel in Einzelteile zerlegt wird, um daraus die Struktur des Baums zu bestimmen. Bei  Schlüsseln, die nur aus Ziffern bestehen, hätte der Baum einen Verzweigungsgrad von 10, da eine Zahl in seine Bestandteile (Ziffern) zerlegt wird. Das Suchen nach einer n-stelligen Zahl würde dann n Schritte im Baum benötigen.

Im Vergleich zu Hashmaps sind Bäume meist langsamer, aber dafür wird der Platz besser ausgenutzt und sie sind robuster, wenn es sich um Ausnahmefälle handelt. Natürlich lassen sich beide Techniken miteinander kombinieren, aber im Endeffekt kommt es auf den Anwendungsfall an, ob Bäume oder Hashmaps zu bevorzugen sind. Beispielsweise sind Hashmaps in Datenbanken quasi nicht nutzbar, da die Datenmengen häufig größer sind als der Arbeitsspeicher Platz bietet. Da die meisten Daten deshalb auf der Festplatte gespeichert werden müssen, kommt der B-Baum zum Einsatz, der durch seine geringe Höhe ein Minimum an Festplattenzugriff garantiert.