= Splay tree
{wiki}
A <splay tree> is a <binary search tree> whose access operations use <splaying> to move a selected key to the root through <tree rotations>. It stores no explicit balance or height information. A single access can take linear time, while the standard operations have logarithmic <amortized time complexity>. The distinction matters: <amortized analysis> bounds the total cost of an operation sequence, not the worst cost of every individual operation.<Self-Adjusting Binary Search Trees by Daniel Sleator and Robert Tarjan>[Author-hosted abstract: representation, operations and amortized logarithmic bound]{ref}
Back to article page
