Zigzag
Relevante Bilder
Relevante Artikel
Splay-BaumIn der Informatik ist ein Splay-Baum ein spezieller Typ eines binären Suchbaums. Der Splay-Baum ist eine selbst-organisierende Datenstruktur mit der Besonderheit, dass die Organisation der gespeicherten Elemente sich potentiell nicht nur bei Modifikationen ändert, sondern auch bei bloßen Anfragen. Die angefragten Elemente werden in die Nähe der Wurzel „gespült“, so dass sie bei einer alsbaldigen erneuten Suche schneller gefunden werden. Alle wichtigen Operationen wie Einfügen, Suchen und Löschen werden (amortisiert) effizient ausgeführt. Für eine gegebene Anfragesequenz verhält sich der Splay-Baum bezüglich der asymptotischen Laufzeit aller Anfragen äquivalent zu einer optimalen statischen Datenstruktur für diese Sequenz. Diese Eigenschaft bezeichnet man als „statische Optimalität“. Es wird vermutet, dass die asymptotische Laufzeit der Anfragesequenz auch äquivalent zu der einer optimalen dynamischen Datenstruktur ist. Diese Vermutung ist als „dynamische Optimalität“ bekannt und gilt als eines der bekanntesten offenen Probleme auf dem Gebiet der Datenstrukturen. .. weiterlesen