Ein Treap ist eine hybride Datenstruktur, die die Eigenschaften von Binärbäumen und Heaps kombiniert. In einem Treap wird jeder Knoten durch einen Schlüssel und eine zufällig zugewiesene Priorität definiert. Die Schlüssel werden so angeordnet, dass die Eigenschaften eines Binärsuchbaums (BST) erfüllt sind: Für jeden Knoten ist der Schlüssel des linken Kindes kleiner und der Schlüssel des rechten Kindes größer. Gleichzeitig wird die Priorität so angeordnet, dass die Eigenschaften eines Max-Heap erfüllt sind: Die Priorität eines Knotens ist immer größer oder gleich der Prioritäten seiner Kinder.
Diese Struktur ermöglicht eine effiziente Durchführung von Operationen wie Einfügen, Löschen und Suchen in durchschnittlicher Zeitkomplexität von . Ein großer Vorteil von Treaps ist, dass sie durch die zufällige Priorität eine ausgeglichene Struktur garantieren, was die Worst-Case-Leistung verbessert. Die Implementierung eines Treaps ist einfach und benötigt nur grundlegende Kenntnisse über Baumstrukturen und Heaps.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.