Ein Splay Tree ist eine selbstbalancierende Datenstruktur, die auf dem Konzept von binären Suchbäumen basiert. Der Hauptunterschied zu herkömmlichen binären Suchbäumen ist die Verwendung einer speziellen Rotationsoperation, die als Splay bezeichnet wird. Diese Operation wird angewendet, um das zuletzt zugegriffene Element an die Wurzel des Baums zu bringen, was die Zugriffszeit für häufig verwendete Elemente optimiert.
Die Grundidee hinter Splay Trees ist, dass Elemente, die häufig abgerufen werden, in der Nähe der Wurzel gehalten werden, was den Zugriff auf diese Elemente im Durchschnitt schneller macht. Die Zeitkomplexität für das Einfügen, Löschen und Suchen ist amortisiert , wobei die Anzahl der Elemente im Baum ist. Ein Splay Tree benötigt jedoch im Worst Case Zeit, wenn der Baum sehr unausgewogen ist. Trotz dieser Worst-Case-Szenarien sind Splay Trees aufgrund ihrer Effizienz bei wiederholten Zugriffen in vielen Anwendungen nützlich.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.