Seit spreizen Baum eine Art von unausgeglichen binärer Suchbaum ist (brilliant.org/wiki/splay-tree), kann es nicht eine Höhe von höchstens O (log (n)) garantieren. Daher würde ich denken, dass es keine Worst-Case-Suchzeit von O (log (n)) garantieren kann.Splay Baum Worst Case Suche Zeit
Aber nach bigocheatsheet.com:
Splay Baum worst case Suchzeit O (log (n)) ???
Sie sind richtig; Die Kosten einer Suche in einem Splay-Baum können Θ (n) für einen unausgeglichenen Baum erreichen. Spickzettel
Viele Ressourcen wie die Big-O entweder machen vereinfachenden Annahmen oder einfach nur sachlich falsche Daten in ihnen. Es ist unklar, ob sie hier nur falsch waren, oder ob sie amortisiert schlimmsten Fall, etc.
Es ist immer am besten zu wissen, die Interna der Datenstrukturen, mit denen Sie arbeiten, so dass Sie verstehen, wo die Laufzeiten herkommen .
Die Wikipedia-Seite macht eindeutig die korrekte Aussage, dass _amortized_ Kosten des Zugriffs O (log n) ist, obwohl jeder einzelne Zugriff O (n) sein kann. Amortisierte Grenzen sind üblich. Die dynamisch wachsenden 'ArrayList's in vielen Sprachen haben O (1) Einfügekosten amortisiert, aber jede einzelne Einfügung kann O (n) Zeit benötigen, weil das gesamte Array in einen neuen, größeren Speicherblock kopiert werden muss. – Gene