 Splay tree

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.^[ref]