Das Problem
Das Ordnen und Durchsuchen von grossen Datenmengen sind Aufgaben, die in der Informatik häufig auftreten und schnell ausgeführt werden sollten. Wer will beispielsweise eine halbe Minute warten, bis Facebook beim Login den Benutzernamen in der Datenbank mit Millionen von Benutzern gefunden und mit dem eingegebenen Passwort verglichen hat? Genau dafür braucht es Algorithmen, die Daten geschickt abspeichern und so schnell wiederfinden können. Eine Lösung für diese Aufgaben sind sogenannte Treaps. Der Name setzt sich zusammen aus den Wörtern Tree und Heap und beschreibt die Idee ziemlich genau. Das Konzept der Treaps soll hier aufbauend erklärt werden:
Man versetze sich in die Lage eines (vergleichsweise kleinen) Social Networks, das eine Million Benutzer-IDs (Zahlen) abspeichern und schnell wiederfinden soll. Die offensichtlichste Lösung dafür ist wohl eine Liste. Beim Login geht das System die ganze Liste durch, bis die Benutzer-ID gefunden wurde. Im schlimmsten Fall müssen so also eine Million Zahlen verglichen werden. Wächst das Social Network weiter, so steigt auch die Zeit, die das System braucht, um die passende Benutzer-ID zu finden – und zwar linear. Bei einer Milliarde Benutzer müssen im schlimmsten Fall eine Milliarde Zahlen verglichen werden. Der Menschenverstand genügt um zu sehen, dass so das System irgendwann ziemlich langsam wird. Eine bessere Lösung muss her.
Binäre Suchbäume
Eine Lösung liefern sogenannte binäre Suchbäume (trees). Diese bestehen aus Knoten (nodes) und Verästelungen. Jeder Knoten besitzt eine Zahl (key) und maximal zwei ausgehende Äste (pointers) auf weitere Knoten. Beginnend mit einem obersten Knoten (root) entsteht so gegen unten ein „Baum“ mit immer mehr Verästelungen. Die untersten Knoten besitzen keine ausgehenden Äste mehr, sie werden auch Blätter (leaves) genannt.
Die Idee von binären Suchbäumen ist nun, den Baum so anzuordnen, dass bei jedem Knoten der linke ausgehende Ast auf einen Unterbaum mit kleineren Zahlen als die Zahl des Knotens und der rechte auf einen Unterbaum mit grösseren Zahlen als die Zahl des Knotens zeigt. So entsteht ein besonderer Baum.
Will das System nun eine Zahl in diesem Baum suchen, so beginnt es beim obersten Knoten des Baumes. Mit einem Zahlenvergleich wird überprüft, ob die Zahl des Knotens grösser bzw. kleiner als die gesuchte Zahl ist. Entsprechend folgt es dem linken bzw. rechten Ast des Knotens. Dies wird solange weitergeführt, bis entweder der Knoten mit der richtigen Zahl gefunden wurde, oder der Ast, dem weiter gefolgt werden sollte, nicht mehr vorhanden ist. Im ersten Fall hat das System die Zahl gefunden, im zweiten Fall befindet sich die gesuchte Zahl nicht in der Menge. Das Hinzufügen von Zahlen in die Menge funktioniert sehr ähnlich. Befindet sich die Zahl noch nicht in der Menge, so folgt das System wiederum den entsprechenden Ästen und fügt schliesslich an der fehlenden Stelle einen neuen Knoten und den verbindenden Ast ein. Das Entfernen von Zahlen ist etwas komplizierter, kann aber vom System ebenfalls schnell ausgeführt werden. Ist der Knoten mit der zu löschenden Zahl gefunden, so kann dieser nicht einfach gelöscht werden, da so die verbindenden Ästen zu eventuellen Unterbäumen dieses Knotens fehlen würden. Folglich muss der zu löschende Knoten zuerst durch Rotationen, welche die Suchbaum-Eigenschaften des Baumes erhalten, zu einem Blatt gemacht werden (mehr dazu später). Da Blätter keine Äste zu Unterbäumen besitzen, kann der Knoten dann gelöscht werden. So weit das Konzept. Warum sollte das Abspeichern in dieser Form aber nun so viel besser als die Umsetzung mit der Liste sein?
Man stelle sich einen perfekten Baum vor: Jeder Knoten – bis auf die Blätter ganz unten – besitzt genau zwei Äste auf Unterbäume. Zählt man nun die Knoten der verschiedenen Ebenen ausgehend vom obersten Knoten, so stellt man exponentielles Wachstum fest: 1, 2, 4, 8, 16, 32, … Die Anzahl der Knoten – und somit auch die Anzahl der Zahlen, die im Baum gespeichert werden können – nimmt sehr schnell zu. Für die Operationen wie das Finden, Hinzufügen oder Löschen von Zahlen ist aber nur die Höhe des Baumes von Bedeutung. Bei 7 Zahlen braucht das System höchstens 3 Zahlenvergleiche, dann ist die Zahl gefunden. Die Anzahl der benötigten Operationen wächst folglich nur wie der Logarithmus der Anzahl Zahlen in der Menge. Bei einer Million Zahlen sind also nur log₂1’000’000 ≅ 20 Operationen nötig. Bei einer Milliarde genügen log₂1’000’000’000 ≅ 27. Das zeigt die Effektivität von Suchbäumen.
“Entartete” Bäume
Ein Problem gibt es aber noch: Wir haben hier von einem „perfekten“ Baum gesprochen. Was garantiert, dass der Baum wirklich „perfekt“ wird? Fügt man beispielsweise die Zahlen in geordneter Reihenfolge dem Baum zu, so entsteht ein entarteter Baum, der eigentlich wieder das Analoge zur besprochenen Liste darstellt. Das Problem des binären Suchbaumes ist also, dass der Baum bestehend aus den gleichen Zahlen auf verschiedene Weisen aufgebaut werden kann. Im schlimmsten Fall liefert er so gegenüber der Liste gar keinen Vorteil mehr. Dies sollte verhindert werden. Genau deshalb braucht es das Konzept des Heaps. Ein Heap ist ein Baum, bei dem jeder Knoten eine Priorität besitzt. Derjenige Knoten mit der höchsten Priorität befindet sich zuoberst. Alle Unterbäume müssen Knoten kleinerer Priorität aufweisen.
Treaps
Der Treap verbindet die Konzepte des Suchbaumes und des Heaps: Jeder Knoten besitzt eine Zahl (key), eine zufällige Priorität (priority) und maximal zwei ausgehende Äste (pointers). Wiederum müssen alle Knoten des linken Unterbaumes eines Knoten eine kleinere Zahl aufweisen und diejenigen im rechten Unterbaum eine grössere. Dabei muss aber auch die Heap-Eigenschaft erfüllt werden: Alle Knoten in den Unterbäumen eines Knotens müssen eine kleinere Priorität aufweisen als der Knoten selber. Somit wird der Treap eindeutig: Zuoberst befindet sich der Knoten mit der grössten Priorität. Der linke Ast zeigt auf denjenigen Knoten, der im Unterbaum der Knoten mit kleineren Zahlen die grösste Priorität besitzt. Analog zeigt der rechte Ast auf denjenigen Knoten, der im Unterbaum der Knoten mit grösseren Zahlen die grösste Priorität besitzt. Dies wird so weitergeführt und der ganze Baum kann eindeutig aufgebaut werden (mit vollständiger Induktion beweisbar). Die zufällige Wahl der Prioritäten „garantiert“ unter den Gesetzen der Wahrscheinlichkeit einen annehmbar „perfekten“ Baum.
Das Auffinden von Zahlen im Treap funktioniert gleich wie zuvor. Das Hinzufügen von Zahlen wird allerdings etwas komplizierter: Wie zuvor fügt man einen neuen Knoten an der benötigten Stelle an, da dieser aber nun eine zufällige Zahl als Priorität besitzt, könnte eventuell die Heap-Eigenschaft verletzt sein (wenn die Priorität grösser ist als diejenige des Knotens darüber).
In diesem Fall müssen Rotationen durchgeführt werden, welche die Suchbaum-Eigenschaften erhalten. Diese sind unten dargestellt:
Ist die Priorität des rechten Knotens zu gross, so wird eine Linksrotation durchgeführt, ist umgekehrt diejenige des linken zu gross, so wird gegen rechts rotiert. Man sieht leicht, dass dabei die Suchbaum-Eigenschaft erhalten bleibt. Das Löschen von Zahlen kann ebenfalls mit diesen Rotationen umgesetzt werden. Dabei setzt man die Priorität des zu löschenden Knoten auf -1 (kleiner als alle möglichen Prioritäten) und führt so lange Rotationen durch, bis die Heap-Eigenschaft wieder erfüllt ist. Nun ist der zu löschende Knoten zwingend ein Blatt des Treaps und kann somit entfernt werden.
Ich habe das Konzept des Treaps in der Programmiersprache C++ als Klasse umgesetzt. Der Quellcode ist am Ende dieses Beitrages zu finden. Die besprochenen Funktionen (Suchen, Hinzufügen, Löschen) und noch weitere sind als Memberfunktionen der Klasse Treap umgesetzt. Ich habe die Funktionen getestet, falls der Code aber dennoch Fehler enthalten sollte, wäre ich an Feedback interessiert.
Quellen
Quellcode Treap (C++): treap.cpp
Quelle Beitragsbild: Wikipedia
Quelle: Vorlesung Informatik für Mathematiker und Physiker, ETH
