Quelltext der Seite Treap

In der [[Informatik]] ist ein '''Treap''' (gebildet aus ''binary search Tree'', Binärer Suchbaum + ''[[Heap (Datenstruktur)|Heap]]'', wörtlich Haufen, Halde) ein [[binärer Suchbaum]]. Jeder Knoten ''x'' besteht aus zwei Elementen:

* x.key (Element)
* x.priority (Priorität)

Treaps wurden im Jahr 1989 von [[Cecilia R. Aragon]] und [[Raimund G. Seidel]] ([[Universität des Saarlandes]]) erfunden. Eine alternative Bezeichnung ist '''Balde''' (gebildet aus Baum und Halde). 

== Elemente ==

Sie erfüllen die Eigenschaften des binären Suchbaums (Binary search Tree).
Das bedeutet:

* Die Elemente y im linken Teilbaum von x erfüllen: key(y) < key(x)
* Die Elemente y im rechten Teilbaum von x erfüllen: key(y) > key(x)

== Prioritäten ==

Prioritäten erfüllen die Eigenschaften des [[Heap (Datenstruktur)|Heaps]].
Das bedeutet:

* Alle Prioritäten sind verschieden (Zufallszahlen)
* Die Wurzel hat die kleinste Priorität (oberstes Element)
* Wenn y ein Kind von x ist, dann gilt: prio(y) > prio(x)

== Suche nach einem Element ==

Die Suche erfolgt wie in einem binären Suchbaum. Der zu suchende Wert ''k'' wird mit dem Wert der Wurzel verglichen. Ist ''k'' größer, vergleicht man den Wert mit dem nächsten Knoten im rechten Teilbaum, wenn kleiner, dann im linken. Zu erwartende [[Zeitkomplexität|Laufzeit]]: <math>\mathcal{O}(\log n)</math>

== Einfügen eines Elementes ==

Um ein Element ''e'' in einen Treap einzufügen, erstellt man einen neuen Knoten ''x'', speichert das Element ''e'' in ''x.key'' und wählt eine zufällige Priorität für ''x.priority''. Nun fügt man den Knoten mittels ''x.key'' gemäß den Eigenschaften des Binären Suchbaums in den Treap ein. Da durch den neuen Knoten nun die Heap-Eigenschaft verletzt sein könnte, rotiert man den Knoten nun solange hinauf, bis die Heap-Bedingung wieder erfüllt ist.

Zu erwartende Laufzeit: <math>\mathcal{O}(\log n)</math>.
Die zu erwartende Tiefe ist logarithmisch.
Die Anzahl der zu erwartenden Rotationen ist 2.

== Entfernen eines Elementes ==

* Man sucht die Position des zu entfernenden Knotens ''x'' im Baum
* Man wechselt die Priorität auf ''+∞'' (unendlich)
* Man rotiert den zu entfernenden Knoten zu der Seite hin, wo die größere Priorität ist, bis die Heap-Bedingung erfüllt ist, also insbesondere, bis das zu löschende Element ein Blatt ist.
* Das Element ist jetzt ein Blatt und kann gelöscht werden

Zu erwartende Laufzeit: <math>\mathcal{O}(\log n)</math>.
Die zu erwartende Tiefe ist logarithmisch.
Die Anzahl zu erwartender Rotationen ist 2.

== Kleinstes / größtes Element finden ==

Da die Elemente in einem Treap in der Ordnung eines normalen Binären Suchbaums gespeichert sind, ist das kleinste Element ganz links unten, und das größte Element ganz rechts unten zu finden. Somit muss man, um das kleinste Element zu finden, immer in den linken Teilbaum absteigen, und um das größte Element zu finden immer in den rechten Teilbaum absteigen.

Zu erwartende Laufzeit: <math>\mathcal{O}(\log n)</math>, da die zu erwartende Tiefe logarithmisch ist.

== Alle Elemente auflisten ==

* Gibt alle Elemente in aufsteigender Reihenfolge aus
* Wird durch den in-order Durchlauf durchgeführt (zwischen den zwei Teilbäumen)

Laufzeit ist <math>\mathcal{O}(n)</math>.

== Literatur ==
* {{BibISBN|3486275151}}

== Weblinks ==
* [http://www-tcs.cs.uni-sb.de/Papers/rst.ps Wissenschaftliches Dokument über Treaps von Raimund Seidel] (englisch)
* [http://faculty.washington.edu/aragon/treaps.html Linkliste zum Thema Treaps von Cecilia R. Aragon]

[[Kategorie:Suchbaum]]